5、 希尔排序法   【不稳定的】

/*
*

希尔排序，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] ) {

//

实现增量为d的插入排序

arr[ pos + d ] = arr[pos];
pos -= d;

}
arr[ pos + d ] = temp;

}

} while( d > 1 );

}

三种高级排序算法

1、

快速排序

   辅助空间复杂度为 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 )  

//

找到了一对值