比较型排序算法总结

增量排序(shell 排序)：该算法的复杂度要略小于插入排序算法，但是也基本上认为是亚O(N^2)。实现的基本过程如下，选择一个较大的增量gap，一般选择为数组长度的一般作为起始的增量。然后从当前增量作为起始下标开始访问，比较a[i]和a[i-gap],如果a[i] a[0]，这是已经处理过的。如果a[i] >

时间复杂度的测试，首先测试有序数组的排序操作，测试代码和算法效果如下所示：

#define LEN 100000

int main()
{
int i = 0;
int a[LEN];
int b[LEN];
int c[LEN];
int d[LEN];
int e[LEN];
clock_t _start, _end;
double times = 0;

srand((int)time(0));

for(i = 0; i < LEN; ++ i)
{
a[i] = i;
b[i] = a[i];
c[i] = a[i];
d[i] = a[i];
e[i] = a[i];
}

_start = clock();
TQuickSort(a,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The QuickSort took %fs",times);
_start = clock();
QuickSort(b,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The Changed QuickSort took %fs",times);
#if 10
_start = clock();
MergeSort(c,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The MergeSort took %fs",times);

_start = clock();
InsertionSort(d,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The InsertionSort took %fs",times);

_start = clock();
heapSort(e,LEN);
_end = clock();
times = (double)(_end - _start)/CLOCKS_PER_SEC;
printf("The heapSort took %fs",times);
#endif
return 0;
}

结果如下：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 12.850000s
The Changed QuickSort took 0.000000s
The MergeSort took 0.030000s
The InsertionSort took 0.000000s
The heapSort took 0.020000s

从上面的实验结果可知，当为有序数组时，快速排序的速度并不快，甚至是最慢的。插入排序反而是最快的方式。同时我们可以发现采用上面的改进的快速排序算法排序速度很快，并不像传统的算法那么费时间。
测试采用随机数产生的数组进行排序时的实验效果：

[gong@Gong-Computer sort]$ ./quickSort
The QuickSort took 0.020000s
The Changed QuickSort took 0.010000s
The MergeSort took 0.030000s
The InsertionSort took 15.240000s
The heapSort took 0.020000s

从上面的结果可知，对于非有序的数组，快速排序的效果是非常好的，但是插入排序就非常的差劲啦。