#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void input(int* to);//生成随机数组
void mysort(int* from, int len, int* to);//只有这个是重要的
void output(int* from);//只有打印功能
void swap(int* n1, int* n2);
int main()
{
srand((int)time(NULL));
int origin[100] = {}, sorted[100] = {};
input(origin);
printf("原数组：");
output(origin);
printf("\n排序后：");
mysort(origin, 100, sorted);
output(sorted);
return 0;
}
void input(int* to)
{
int i, count, stop, index;
for (i = 0; i < 100; i++)
{
stop = rand() % (100-i);
count = index = 0;
while (1)
{
if (*(to + index) == 0) count++;
if (count > stop) break;
index++;
}
*(to + index) = (i + 1) % 100;
}
}
void output(int* from)
{
int i;
for (i = 0; i < 100; i++) printf("%d ", *(from + i));
}
void swap(int* n1, int* n2)
{
int temp = *n1;
*n1 = *n2;
*n2 = temp;
}
void mysort(int* from, int len, int* to)
{
//1.判断是否需要分段（1元，2元，更多则分段）
//2.如需要分段：
//2-1.确保一部分中每个元素都比另一部分中所有元素大
//2-2.对每一部分排序（递归）
//2-3.将两部分合并
//3.如不二分：排序
if (len == 1) *to = *from;
else if (len == 2)
if (*from > *(from + 1))
{
*to = *(from+1);
*(to+1) = *from;
}
else
{
*to = *from;
*(to+1) = *(from+1);
}
else
{
int halflen = len/2;
int temp1[halflen], temp2[halflen], i,j;
for (i = 0; i < halflen; i++) temp1[i] = *(from + i);//将from分为两半
for (i = 0; i < len - halflen; i++) temp2[i] = *(from + halflen + i);
for (i = 0; i < len - halflen; i++)//确保temp2中每个元素都比temp1中所有元素大
for (j = 0; j < halflen; j++)
if (temp2[i] < temp1[j])
swap(&temp2[i], &temp1[j]);
mysort(temp1, halflen, to); mysort(temp2, len - halflen, to+halflen);//每部分排序和合并都在递归里了
}
}
