各种排序的实现与复杂度分析（继续更新）
各种排序的实现与复杂度分析（持续更新）
（表来源：http://blog.****.net/ns_code/article/details/20540069）
稳定性：
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
复杂度
冒泡法： 复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。不说了。
直接插入排序：O(n*n)
希尔排序：算法的复杂度为n的1.2次幂
选择排序：O(n*n)
快速排序：不稳定，平均时间复杂度O(nlogn)，最坏情况时间复杂度为O(n2)。所有内部排序方法中最高好的，大多数情况下总是最好的。空间复杂度主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)
归并排序：log2(n)*n
堆排序：log2(n)*n
|
排序方法 |
最好时间复杂度 |
平均时间复杂度 |
最坏时间复杂度 |
空间复杂度 |
是否稳定 |
|
冒泡排序 |
O(n) |
O(n*n) |
O(n*n) |
O(1) |
稳定 |
|
插入排序 |
O(n) |
O(n*n) |
O(n*n) |
O(1) |
稳定 |
|
选择排序 |
O(n*n) |
O(n*n) |
O(n*n) |
O(1) |
不稳定 |
|
希尔排序 |
O(n) |
不定 |
O(n*n) |
O(1) |
不稳定 |
|
堆排序 |
O(n*logn) |
O(n*logn) |
O(n*logn) |
O(1) |
不稳定 |
|
归并排序 |
O(n*logn) |
O(n*logn) |
O(n*logn) |
O(n) |
稳定 |
|
快速排序 |
O(n*logn) |
O(n*logn) |
O(n*n) |
O(logn) |
不稳定 |
|
计数排序 |
O(n+k) |
O(n+k) |
O(n+k) |
O(k) |
稳定 |
|
基数排序 |
O(d(n+k)) |
O(d(n+k)) |
O(d(n+k)) |
O(k) |
稳定 |
|
桶排序 |
O(n) |
O(n) |
O(n) |
不定 |
取决于桶内 |
算法实现：
首先是快速排序的实现
void quickSort(int A[], int low, int high){
if(low < high){
int i = low, j = high, key = A[i];
while(i < j){
while(i < j && A[j] > key) // 从右向左找第一个小于key的数
--j;
if(i < j)
A[i++] = A[j];
while(i < j && A[i] < key) // 从左向右找第一个大于等于key的数
++i;
if(i < j)
A[j--] = A[i];
}
A[i] = key; //mid
quickSort(A,low,i-1);
quickSort(A,i+1,high);
}
}