归并排序的实现 C语言版
代码如下（我的C语言比较丑陋，将就着看吧）。
其实感觉挺惊讶的是，递归能让算法如此简洁。
归并的思路也比较简单，就是不断merge有序的数组。当然了，数据的有序可不是天生就有的，这儿找到有序数组的法子就是不断地二分数组，直至有序，何时会达到这个状态呢？比较傻的一个答案：等分到数组只一个元素时，就OK了（汗...）,不过这只是初始阶段，之后的各个分支汇合时，有序的可就是一条条的数组了。
#include <stdio.h>#include "tool.c"int main(){ void mergeSort(int array[],int left,int right); int array={1,2,3,6,8,9,5,4,3,2,54}; printf("Befor mergeSort:\n"); printArray(array,11); mergeSort(array,0,10); printf("After mergeSort:\n"); printArray(array,11); getchar(); return 0; /*Result: Befor mergeSort: 1 2 3 6 8 9 5 4 3 2 54 After mergeSort: 1 2 2 3 3 4 5 6 8 9 54 */}/*Recursively call the mergeSort method,and merge the sorted array.*/void mergeSort(int array[],int left,int right){ void merge(int array[],int left,int right); if(right>left){ mergeSort(array,left,(left+right)/2); mergeSort(array,(left+right)/2+1,right); merge(array,left,right); }}/*here,is the key point.merge the sorted array.*/void merge(int array[],int left,int right){ int rStartPoint=(right+left)/2+1; //Length of the left and right arrays. int leftLen=rStartPoint-left; int rightLen=right-rStartPoint+1; //copy the data into leftArray and rightArray,quite stupid here. //and here is the shortage of mergeSort,it needs additional memory space. int leftArr,rightArr; int i,j; for(i=0;i<=leftLen-1;i++){ leftArr=array; } for(j=0;j<=rightLen-1;j++){ rightArr=array; } //insert data into array from two arranged ones. i=0,j=0; int k=left; while(i<=leftLen-1&&j<=rightLen-1){ if(leftArr<rightArr){ array=leftArr; }else{ array=rightArr; } } while(i<=leftLen-1){ array=leftArr; } while(j<=rightLen-1) array=rightArr;}
另外，我之前一直觉得不断地Merge两个数组，是属于效率比较低的做法，不明白怎么这样了居然归并还能是高效排序，后来才注意到一点，这儿不断的连接的数组可都是有序的，有序数组的合并复杂度可以达到O（N）,相当理想了。
再另外，传说单链表的排序可以用归并？不解，待解(已解,参看这里)。
页:
[1]