归并排序
归并排序
将数据拆分,排序,在进行合并代码
#include <stdio.h>
#include <stdlib.h>
#define N 7
//输出数组
void show_arr(int *p, int len)
{
for (int i = 0; i < len; i++)
{
printf("%4d", p[i]);
}
printf("\n");
}
//合并
void merge(int *p, int start, int mid, int end)
{
int *p_temp = calloc(end - start + 1, sizeof(int));
int left_start = start;
int left_end = mid;
int right_start = mid + 1;
int right_end = end;
int index = 0;
for (index = 0; left_start <= left_end && right_start <= right_end; index++)
{
//比较大小
if (p[left_start] <= p[right_start])
{
p_temp[index] = p[left_start];
left_start++;
}
else
{
p_temp[index] = p[right_start];
right_start++;
}
}
//如果左边有剩余
if (left_start <= left_end)
{
for (int i = left_start; i <= left_end; i++)
{
p_temp[index] = p[i];
index++; //移动
}
}
//如果右边有剩余
if (right_start <= right_end)
{
for (int i = right_start; i <= right_end; i++)
{
p_temp[index] = p[i];
index++; //移动
}
}
printf("p_temp:");
show_arr(p_temp, end - start + 1);
//排完序,拷贝
for (int i = 0; i < end - start + 1; i++)
{
p[start + i] = p_temp[i];
}
if (p_temp != NULL)
{
free(p_temp);
}
}
//分解
void merge_sort(int *p, int start, int end)
{
int mid = 0;
if (start < end) //递归条件
{
mid = (start + end) / 2;
merge_sort(p, start, mid); //切割分段
merge_sort(p, mid + 1, end);
merge(p, start, mid, end);
}
}
int main(int argc, char *argv[])
{
int arr[N] = { 23,10,60,80,38,8,1 };
printf("排序前: ");
show_arr(arr, N);
printf("\n");
merge_sort(arr, 0, N - 1);
printf("\n");
printf("排序后:");
show_arr(arr, N);
system("pause");
return 0;
}效果
秋风
2016-08-21