插入排序
复杂度
最优 O(N)
最差 O(N^2)
平均 O(N^2)
空间 O(1)
稳定排序
思路
插排的思路是保证遍历到每个元素时，该元素前面的序列都是有序的。
基于这个前提，我们将遍历到的新元素和它前面的序列相比对，然后将这个元素插入到适当的位置，使得这个包含新元素的序列也是有序的。
虽然外层遍历只要O(N)时间，但是因为找到新元素的适当位置后要将之后的所有元素后移，所以最差时间是O(N^2）。
public class InsertionSort<T extends Comparable> {
public T[] sort(T[] a){
T[] array=a;
T tmp;
for(int i = 1; i<a.length; i++){
tmp=array[i];
int j;
// 从后向前找到插入新元素的适当位置，比新元素大的都后移一位
for(j=i;j>0;j--){
if(array[j-1].compareTo(tmp)<0) break;
array[j]=array[j-1];
}
// 较大的元素都后移了一位，这里只要插入这个新元素，则新序列还是有序的
array[j]=tmp;
}
return array;
}
}
希尔排序
复杂度
最优 O(N)
最差 O(N^2)
空间 O(1)
不稳定排序
思路
插排的一个优化是希尔排序，在原本的插入排序中，我们选择以一个一个往后看等待插入的元素。
然而插入排序有这么一个性质，即如果序列有序程度越高，则时间复杂度越低。
所以希尔排序利用了这个性质，先通过较大的步长进行一次插入排序（不再是一个一个往后找待插元素，而是隔一个或者隔n/2个元素来找），
这样每次子插排都能将序列变得更有序一点，而且因为步长一开始很大，所以要遍历的数少，时间复杂度也很低。后来步长变小了，要遍历的数
变多了，但数组也更有序了，时间复杂度也降低了。当然n/2^i这个步长序列不是最好的，最好的步长序列能使最差复杂度降低至O(N(logN)^2)
public class Shellsort {
public static <T extends Comparable<? super T>> T[] sort(T[] a) {
int j = 0;
// 从n/2开始选择步长，每轮插排后减少步长，直到步长为1是最后一次
for (int gap = a.length / 2; gap > 0; gap /= 2) {
T tmp = null;
// 步长为gap的插入排序
for(int i = gap; i<a.length; i++){
tmp = a[i];
// 找到合适的插入点
for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){
a[j]=a[j-gap];
}
a[j]=tmp;
}
}
return a;
}
}
选择排序
复杂度
最优 O(N^2)
最差 O(N^2)
平均 O(N^2)
空间 O(1)
不稳定排序
思路
选排的思路和插排相反，插排是搜索有序序列找到合适的位置，选排则是搜索剩余的无序序列选择出其中最大（或最小）的，并将这个被选择的数放到无序序列的首部。
需要注意的是。将这个数放到首部时，用的是交换的方法。因为无论如何都要遍历完子序列，所以时间复杂度至少是O(N^2)
public class SelectionSort<T extends Comparable> {
public T[] sort(T[] array) {
T[] a = array;
T tmp;
int minIndex;
for (int i = 0; i < a.length; i++) {
minIndex = i;
// 在剩余无序序列中找到一个最小的
for (int j = i; j < a.length; j++) {
if (a[minIndex].compareTo(a[j]) > 0)
minIndex = j;
}
// 将这个最小的交换到无序序列的首部
if (minIndex != i) {
tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
return a;
}
}
归并排序
复杂度
最优 O(NlogN)
最差 O(NlogN)
平均 O(NlogN)
空间 O(N)
稳定排序
思路
归并排序是典型的分治法。基本思路是将一个较长数组一分为二，我们将它的左右两半部分分别排好序，然后将这有序的两部分合并起来，这样较长数组也是有序的了。
因为两半部分都是有序的，所以合并只需要同时遍历一下两半部分，看谁较小（大）就把谁先塞进数组就可以了。根据这个思路，我们不停的二分、二分，这样二分到
尽头肯定只有一个数的数组，那它肯定是有序的，然后我们将两个只有一个数的数组合并，只要比较下这两个数就行了。这样就返回了一个有两个数的有序数组，然后
再一直合并、合并、直到合并出整个数组。不过，在合并两个子数组时，要先用一个临时数组存放，否则会修改两个子数组的数据（因为两个子数组实际上是原数组的
两个子部分）。
public class Mergesort<T extends Comparable<? super T>> {
private static <T extends Comparable<? super T>> T[] sort(T[] array, T[] tmp, int left, int right){
if(left<right){
// 计算二分中点位置
int center = (left+right)/2;
// 将左半部分排序
sort(array,tmp,left,center);
// 将右半部分排序
sort(array,tmp,center+1,right);
// 将左右两半部分合并
merge(array,tmp,left,center+1,right);
}
return array;
}
public static <T extends Comparable<? super T>> T[] sort(T[] a){
T[] tmp = (T[]) new Comparable[a.length];
return sort(a,tmp,0,a.length-1);
}
private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd){
int leftEnd=rightPos-1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos +1;
// 将两个有序数组的元素比较大小后合并成一个数组，存入一个临时数组中
while(leftPos<=leftEnd && rightPos<=rightEnd){
if(a[leftPos].compareTo(a[rightPos])<0)
tmpArray[tmpPos++]=a[leftPos++];
else
tmpArray[tmpPos++]=a[rightPos++];
}
// 如果左半部分没有合并完（说明右半部分的数较小），将其合并进去
while(leftPos<=leftEnd){
tmpArray[tmpPos++]=a[leftPos++];
}
// 如果右半部分没有合并完（说明左半部分的数较小），将其合并进去
while(rightPos<=rightEnd){
tmpArray[tmpPos++]=a[rightPos++];
}
// 将这个临时数组拷贝回原数组
for(int i = 0;i<numElements;i++,rightEnd--){
a[rightEnd]=tmpArray[rightEnd];
}
}
}
快速排序
复杂度
最优 O(NlogN)
最差 O(N^2)
平均 O(NlogN)
空间 O(logN)
不稳定排序
思路
快速排序也是分治的思想，它先选取一个枢纽值pivot，将整个数组按照枢纽值的大小重新排列，比枢纽值小的放在左边，比枢纽值大的放在右边。
然后，我们再分别对这左半部分和右半部分进行同样的操作，这里半个部分不一定有半个数组的元素，要看具体有多少元素大于或小于枢纽值。
一般情况下我们都选择子数组的第一个值作为枢纽，简化实现。最好还是能写个随机选择枢纽值的函数。最差的情况下，每次选到的枢纽值都是
最小（最大）的，所以每次分割出来的子数组都只比当前整个数组小1的长度，就会导致O(N^2)的复杂度。
public class Quicksort {
public <T extends Comparable<? super T>> T[] sort(T[] a){
return sort(a,0,a.length);
}
private <T extends Comparable<? super T>> T[] sort(T[] a, int left, int right){
if(left==right-1) return null;
//Partition into two part first
int k=partition(a,left,right);
//Recurse on front part
sort(a,left,k);
//Recurse on rear part
sort(a,k,right);
return a;
}
private <T extends Comparable<? super T>> int partition(T[] a, int left, int right){
T p = a[left];
int i = left, j =right;
// 先找到右边第一个小于枢纽值的数
do{
j--;
}while(a[j].compareTo(p)>0 && j>i);
//Swap a[i] and a[j] to partition
while(i<j){
// 将右边那个小于枢纽值的数和左边那个大于枢纽值的数交换（第一次交换的是枢纽值本身）
swap(a,i,j);
// 找到下一对可以交换的元素
do{
i++;
}while(a[i].compareTo(p)<0);
do{
j--;
}while(a[j].compareTo(p)>0);
}
//Elements before j+1 are partitioned, so we need to partition next part start from j+1
return j+1;
}
private <T extends Comparable<? super T>> void swap(T[] a, int i, int j){
T tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}
}
外部排序
例题:
假设我们有1TB的数据需要排序，但是只有一台1GB内存的机器，请问如何排序？
思路
外部排序基于归并排序的理念，以该题为例，为了计算方便我们假设TB/GB/MB是以1000换算的，而且内存也有1.001G空间：
将1TB数据分1000次读入内存中，每次对1GB的数据进行排序，每次排序完将其作为一个区块结果存入磁盘中。
在内存中划分1000个通道，每个通道读入每个区块前1MB的数据，可知每个1MB都是有序的。
对这1000个有序的1MB数据进行归并。将结果存入一个1MB的缓存当中，每当这1MB缓存满的时候，将这1MB缓存存入磁盘并清空。
每当任何一个1MB通道空时，我们将对应区块的下1MB数据读入这个通道。
持续执行步骤3直到所有区块的数据都被读完，这时候磁盘中就是1TB有序的数据了。