排序总结

近几天复习了一下排序算法，以此总结加深印象。
首先定义两种原子操作：
void exch(T[] array,int i,int j) ：将数组array中的i、j元素互换位置；
boolean less(T a,T b) ：比较元素a,b的大小。

原始数组：array

选择排序：[空间复杂度O（1）、时间复杂度O（N^2）]
循环操作，每次选定剩余数组中最小的元素填充到已排序部分的队尾；算法交换次数总是N，比较次数大约是N²/2。运行时间与输入无关、数据移动是最少的。

插入排序：[空间复杂度O（1）、时间复杂度O（N^2）]
循环操作，将下一位元素插入到已排序数组中的合适位置；平均需要N²/4次交换和N²/4次移动；最坏情况N²/2次交换和N²/2次移动；最好情况下进行N-1次比较和0次移动。运行时间取决于初始元素的顺序。对于部分有序的数组的排序更好。
几种常见的部分有序数组：
1.数组中每个与元素距离它的最终位置都不远；
2.一个有序大数组接一个小数组；
3.数组中只有几个元素的位置不确定；

改进点：将内循环中将较大元素向右移动而不总是交换两个元素；
总体来说，插入排序对于部分有序的数组和小规模数字十分有效；一般情况下，插入排序的效率大概是选择排序的两倍；

希尔排序：[空间复杂度O（1）、时间复杂度O（N^（3/2))]
是对于插入排序的改进；对于大规模乱序数组，由于插入排序只能交换相邻两个元素的位置，如果最小元素恰好在数组尽头，就需要N-1此移动。希儿排序交换不相邻元素以对数组的局部进行排序。
核心思想：任意相隔h的元素都是有序的，序列一般选择h = 3h+1,h初始为1，最大不大于N/3。内部使用插入排序变体：
//希尔排序
int N = test.length;
int h = 1;
while (h<N/3) h = 3h+1;
while (h>=1){
for(int i = h;i<test.length;i++){
for (int j = i;j>=h;j-=h){
compare++;
if(test[j] < test[j-h]){
int temp = test[j];
test[j] = test[j-h];
test[j-h] = temp;
swap++;
}else {
break;
}
}
}
h = h/3;
}

    适用于中等规模的数组。

归并排序：[空间复杂度O（N）、时间复杂度O（NlogN)]
将两个有序小数组归并为大数组，并逐渐合并为大数组；

优化：对于过小的数组使用插入排序