code. compile. run. debug. share.
Source Code
Language
#include <stdio.h>
int temp_array[]; //临时数组
void print(int*,int,int);
void merge(int*,int,int,int,int);
void mergeSort(int*,int,int);
int main ()
{
int arr[] = {9,7,6,10,123,100,8,-1,0,6,-20,90,00,-110,31};
size_t n = sizeof (arr) / sizeof (int); //获取数组的长度
//初始化数组，数组的长度为n，这里需要分配和排序数组一样的长度即可。
//因为在归并过程中，可能用到的最大长度也就是n.
memset (temp_array, 0, n * sizeof (int));
//进行归并排序
mergeSort (&arr, 0, n-1);
print(&arr,0,n);
return 0;
}
void mergeSort (int *arr, int begin, int end)
{
if (begin >= end)
return;
//获取中间元素的下标
int middle = (begin + end) / 2;
int left_begin = begin;
int left_end = middle;
int right_begin = middle + 1;
int right_end = end;
//对左边进行排序
mergeSort (arr, left_begin, left_end);
//对右边进行排序
mergeSort (arr, right_begin, right_end);
//将左右两边排好序的序列汇总成一个序列
merge (arr, left_begin, left_end, right_begin, right_end);
}
void merge (int *arr, int left_begin, int left_end, int right_begin, int right_end)
{
size_t index = 0;
//得到左边排好序的范围
int left_index = left_begin;
int left_index_max = left_end;
//得到右边排好序的范围
int right_index = right_begin;
int right_index_max = right_end;
//将两个范围的数据，按照升序，汇总到temp_array变量中。
//左边和右边肯定有一边先退出条件，而另一边剩下的数据，是已经排好序的，
//因此只需要将剩下的数据追加到temp_array即可。
//比如：[1,4,5] 和 [1,3,7,8]
while (left_index <= left_index_max && right_index <= right_index_max)
{
int left_val = arr[left_index];
int right_val = arr[right_index];
if (left_val < right_val)
{
temp_array[index++] = left_val;
++left_index;
}
else
{
temp_array[index++] = right_val;
++right_index;
}
}
//比如: [1,4,5] 和 [1,3,7,8]
//经过上面的合并，左边的数组先退出，这时候temp_array=[1,1,3,4,5]
//右边还剩下[7,8], 只需要附加到temp_array末尾即可[1,1,3,4,5,7,8]
if (left_index > left_index_max) //左边先退出条件，将右边的数据追加到temp_array
while (right_index <= right_index_max)
temp_array[index++] = arr[right_index++];
else //右边先退出条件, 将左边的数据追加到temp_array
while (left_index <= left_index_max)
temp_array[index++] = arr[left_index++];
//此时temp_array中的数据是排好了序的
//最后将临时数组temp_array[0,right_end]中的数据，复制到arr中
int arr_index = left_begin;
int arr_index_max = right_end;
size_t temp_index = 0;
while (arr_index <= arr_index_max)
arr[arr_index++] = temp_array[temp_index++];
}
void print(int *arr, int start, int end)
{
for(int index=start; index < end; ++index)
printf("%d ",arr[index]);
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|