五、 希尔排序法 【不稳定的】 /*
* 希尔排序，n

 

为数组的个数 */

void ShellSort( int arr[], int n ) {
int temp,pos;
int d = n; //

 

增量初值 do{

d = d/3 + 1 ;
for(int i= d; i<n; i++ ) {
temp = arr[i]; pos = i-d;
while( pos>=0 && temp < arr[pos] ) { arr[ pos + d ] = arr[pos]; pos -= d; }
arr[ pos + d ] = temp; }
} while( d > 1 ); }
//实现增量为 d 的插入排序
三种高级排序算法

 

 

一、 快速排序 辅助空间复杂度为 O（1  

 

） 【不稳定的】 void QuickSort( int *a,int left, int 

right) {
int i,j,middle,temp; i = left; j = right;
middle = a[ (left+right)/2 ]; do {
while( a[i]<middle && i<right ) //

 

从左扫描大于中值的数 i++;

while( a[j]>middle && j>left ) //

 

从右扫描小于中值的数 j--;

if( i<=j ) //

 

找到了一对值 {

temp = a[i]; a[i] = a[j];
}
a[j] = temp; i++; j--; }
} while ( i<j ); //如果两边的下标交错，就停止(完成一次) //当左半边有值（left<j）,递归左

 

半边 if( left < j )
QuickSort( a, left, j);
//当右半边有值（right>i）,

 

递归右半边 if( i < right )

QuickSort( a, i, right);
它的工作看起来象一个二叉树。首先我们选择一个中间值 middle，程序中我们使用数组中
间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后

——

交换）。然后对两边分别使用这个过程（最容易的方法

递归）。注意，由于数据的随

机性，对 middle 的选择并不会影响该算法的效率。
注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于
参考值，就需要进行交换。最终得到的结果是，j 左边的值都小于参考值，而 i 右边的值都
大于参考值，j 和 i 之间的值都等于参考值。对 j 左边和 i 右边的分别使用递归，就可以完
成最终的排序。
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最
理想的情况
1.数组的大小是 2 的幂，这样分下去始终可以被 2 整除。假设为 2 的 k 次方，即 k=log2(n)。

 

2.

 

每次我们选择的值刚好是中间值，这样，数组才可以被等分。第一层递归，循环 n 次，

第二层循环 2*(n/2)......
所 以 共 有 n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n   所 以 算 法 复 杂 度 为
O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的 middle 都是最小值或最大值，