} }
4.缩小增量排序(希尔排序)
由希尔在1959年提出，又称希尔排序。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d 优点：快，数据移动少； 缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。 初始：d＝5 49 38 65 97 76 13 27 49 55 44 一趟结果 13 27 49 55 44 49 38 65 97 76 d=3 |----------------------|----------------------|---------------------| 二趟结果 13 44 49 38 27 49 55 65 97 76 d=1 三趟结果 13 27 38 44 49 49 55 65 76 97 #include using namespace std; #define MAX 16 void shell_sort(int *x, int n) { inth, j, k, t; for(h=n/2;h>0; h=h/2) /*控制增量*/ { for(j=h; j { t= *(x+j); for(k=j-h; (k>=0 && t<*(x+k)); k-=h) { *(x+k+h)= *(x+k); } *(x+k+h)= t; } } } void main() { int*p, i, a[MAX]; p= a; cout<<\ for(i=0; i cin>>*p++; p=a; shell_sort(p,MAX); for(p=a, i=0; i cout<<*p++< cout< 5.快速排序 快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。 优点：极快，数据移动少； 缺点：不稳定。 分段插入排序 void QuickSort(int *pData, int left, intright) { int i, j; int middle,iTemp; i = left; j = right; middle =pData[(left + right) / 2]; //求中间值 do { while((pData < middle) && (i < right)) //从左扫描大于中值的数 i++; while((pData[j] > middle) && (j > left)) //从右扫描小于中值的数 j--; if (i <=j) //找到了一对值 { //交换 iTemp =pData; pData =pData[j]; pData[j] =iTemp; i++; j--; } } while (i<= j) ; //如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left QuickSort(pData,left,j); //当右边部分有值(right>i)，递归右半边 if(right>i) QuickSort(pData,i,right); } 6.归并排序算法 合并排序（MERGESORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。 例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 [49] [38] [65] [97] [76] [13] [27] 第一次合并之后 [38 49] [65 97] [13 76] [27] 第二次合并之后 [38 49 65 97] [13 27 76] 第三次合并之后 [13 27 38 49 65 76 97] 合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。 其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n) 归并排序： #include void merge(int a[],int p,int q,int r)