C语言——归并排序

<>C语言——归并排序

归并排序用到了分治思想，借助递归的方式对一串数字进行排序，整个过程分为分开和合并两个过程。其实归并排序的思想并不难理解，但是用代码实现它却并不容易，我们要写两个函数去分别实现这个过程，一个函数用来专门分开合并，另一个函数则描述了每一次排序的过程。
我们来看一个例子：
a[]={1,3,5,7,2,4,6,8};

对于这个数组，利用归并的思想排序，就是把它分成两个部分，从中间截开，分成两组数：1，3，5，7和2，4，6，8；我们可以发现两组数都是从小到大排序的，我们可以定义两个变量一个指向前一串数的第一个数字，另一个变量指向第二组数的第一个变量，分别比较这两个数，将小的那个放进一个新数组，然后变量往后移，逐个比较，最终就有了一个新数组，这个新数组就是排序好的数组。

但是如果分成两组数之后，两边的数字并不是有序的该怎么办？这时候说明把数组分开一次不够，就要继续再分，如果还不是有序的？再分，直到把它们分为一个一个的数，然后再用归并的思想把它们重新排回原来的数组，整个数组就变得有序了。
在这里可能不太好理解，我们可以看一下下面的图片，或许就好理解很多。

接下来我们来看代码，首先我们来看第一个函数，第一个函数的作用就是把数组从中间切开再合并。
void merge_sort(int a[],int left,int right){ if(left<right){ int mid = (left +
right) / 2;//从中间截开 merge_sort(a,left, mid);//把左边沿中间截开 merge_sort(a, mid + 1,
right);//把右边沿中间截开 merge(a, left, right, mid);//合并 } }
接下来这个函数是合并的过程。
void merge(int a[],int left,int right,int mid) { int s[100];//一个新数组用来存储排序好的数组
int i = left, j = mid + 1;//两个变量分别指向左边和右边两组数的第一个数 int sor = left; while (i <=
mid&& j <= right) { if (a[i] < a[j]) {//归并的过程 s[sor++] = a[i++]; } else { s[sor
++] = a[j++]; } } while (i <= mid) s[sor++] = a[i++];
//当一组数已经全部排进去之后，再将另外一组数的全部数字都排进去 while (j <= right) s[sor++] = a[j++]; sor =
left; while (sor <= right) {//把排好序的新数组全部放回原数组里 a[sor] = s[sor]; sor++; } }
我们在主函数运行一下这个代码。
#include <stdio.h> void merge_sort(int a[],int left,int right){ if(left<right){
int mid = (left + right) / 2; merge_sort(a,left, mid); merge_sort(a, mid + 1,
right); merge(a, left, right, mid); } } void merge(int a[],int left,int right,
int mid) { int s[100]; int i = left, j = mid + 1; int sor = left; while (i <=
mid&& j <= right) { if (a[i] < a[j]) { s[sor++] = a[i++]; } else { s[sor++] = a[
j++]; } } while (i <= mid) s[sor++] = a[i++]; while (j <= right) s[sor++] = a[j
++]; sor = left; while (sor <= right) { a[sor] = s[sor]; sor++; } } int main() {
int a[]={3,9,5,4,64,4,5,9,8,9}; int i; merge_sort(a, 0, 9); for(i = 0; i < 10; i
++) { printf("%d ", a[i]); } return 0; }
运行结果：

• « 上一篇：数组的使用（调用）
• » 下一篇：MySQL存储引擎