插入排序：
插入排序方法为：遍历、抽牌、较大牌后移、放牌。算法复杂度O（N）。
N个互异数的数组的序偶的总个数N（N-1）/2，平均逆序数为其一半N（N-1）/4。
通过交换相邻元素的任何排序算法都需要Omega(N^2)时间。
//**********
public static > void insertSort(AnyType[] a){
for(int p=1;p
AnyType eject=a[p];
int j;
for(j=p;j>0&&a[j-1].compareTo(eject)>0;j--)
a[j]=a[j-1];
a[j]=eject;
}
}
//**********
希尔排序：
希尔排序通过比较具有一定间隔的元素来工作，各趟比较的距离逐渐缩小，直到比较相邻元素的最后一趟为止。因此希尔排序又称"缩减增量排序"，复杂度O(N^2)。
而Hibbard增量的希尔排序的最坏时间O(N^(3/2))。
//**********
public static > void shellSort(AnyType[] a){
for(int gap=a.length/2;gap>0;gap/=2){
for(intp=gap;p
AnyTypeeject=a[p];
int j;
for(j=p;j>0&&a[j-gap].compareTo(eject)>0;j-=gap)
a[j]=a[j-gap];//此处注意步进为gap而不是1
a[j]=eject;
}
}
}
//**********
堆排序：
数组二叉堆实现的堆排序：建堆buildHeap耗时O（N），弹堆deleteMin耗时O(logN)，总时间O(NlogN)。
堆排序避免拷贝数组耗时O(N)及空间的方法：堆中最后的单元用来存放deleteMin的元素。使用最大堆将得到增排序。
数组二叉堆由下滤perculate、建堆buildHeap、弹堆deleteHeap构成。
[if !supportLists]l [endif]堆排的下滤同快排一样使用半判断循还，区别是堆排并非为了效率，而是需要先处理下滤路径才能做出判断。
下滤三判断：取左子防溢出，比右比防溢出，下滤终止。
[if !supportLists]l [endif]建堆过程就是非叶节点的下滤过程。（叶结点就不必下滤了）
[if !supportLists]l [endif]弹堆过程的取堆根、堆尾补、下滤过程，在堆排序中简化为堆的根尾交换，使堆排序成为了原址排序。
注点1：全部写为静态static函数，不封闭。
注点2：数组中0位置有元素，索引号加1。
注点3：perculateDown(a,end,hole)要注明末元素end用来区分未排数据堆和已排数据。
public static intleftChild(int i) {
return 2 * i+ 1; //索引号从1开始才是左儿子2i，右儿子2i+1
}
public static > void swap(AnyType[] a, int s1,int s2) {
AnyType tmp= a[s1];
a[s1] =a[s2];
a[s2] = tmp;
}
public static > void perculateDown(AnyType[] a,int end, int hole) {
AnyTypeeject = a[hole];
int child;
for (;; hole= child) {
child= leftChild(hole);
if(child > end)
break;
if(child< end && a[child].compareTo(a[child + 1])<0)
child++;//向小儿子走（这里为max堆对应向大儿子走）
if(a[child].compareTo(eject)>0)
a[hole]= a[child];
else
break;
}
a[hole] =eject;
}
public static > void heapSort(AnyType[] a) {
for (int i =a.length / 2; i >= 0; i--)
perculateDown(a,a.length - 1, i);
for (int end= a.length - 1; end > 0;) {
swap(a,0, end--);//交换相当于保存了deleteMin元素并且补上了根节点
perculateDown(a,end, 0);
}
}
归并排序
归并排序为典型的递归算法：分治、解决、合并（两副有序牌合为有序排）、递归底为1个元素不用排。
归并排序的合牌方法：双针拣牌，拷贝余牌，拷回临时数组。
归并排序的递归函数形参为待排数组和始末位置。
归并排序的缺点是非原址排序，算法复杂度O(NlogN+N)。
public static > void mergeSort(
AnyType[] a) {
mergeSort(a, 0, a.length - 1);
}
public static > void mergeSort(
AnyType[] a,int left, int right) {
if (left < right) {
int center =(left + right) / 2;
mergeSort(a,left, center);
mergeSort(a,center + 1, right);
merge(a, left,center, right);
}
}
public static > void merge(
AnyType[] a,int leftStart, int leftEnd, int rightEnd) {
int itemNum = rightEnd -leftStart + 1;
AnyType[] tmp = (AnyType[]) newObject[itemNum];//泛型数组的创建
int leftPos = leftStart;
int rightPos = leftEnd + 1;
int tmpPos = 0;
while (leftPos <= leftEnd&& rightPos <= rightEnd) {
if(a[leftPos].compareTo(a[rightPos]) < 0)
tmp[tmpPos++]= a[leftPos++];
else
tmp[tmpPos++]= a[rightPos++];
}
while (leftPos <= leftEnd) {
tmp[tmpPos++] =a[leftPos++];
}
while (rightPos <= rightEnd) {
tmp[tmpPos++] =a[rightPos++];
}
int copyBackPos = leftStart;
for (int i = 0; i < itemNum;){
a[copyBackPos++]= tmp[i++];
}
}
快速排序：
快速排序算法：
[if !supportLists]1) [endif]三数中值分割定枢纽元（首末元素已分集，枢纽元置末二位），pivot枢纽。
遇等枢纽值不跳，即实现了非二次时间的可能，又配合"三数中值分割"起到了限界的作用。
2) 分集方法为：初始位让针，无条件跳针（先++助交换跳针），非相遇换针，相遇终止。枢纽元与i针交换。
3) 子问题递归，递归子问题left~i-1，i+1~right
4) 递归底用插排
快速排序复杂度O(NlogN)
快速排序算法要点：
[if !supportLists]l [endif]交换数据元素，swap的形参包含数组引用和2个位置指针。
[if !supportLists]l [endif]快速排序的分集方法采用"半判断循还"while(true){代码;if(条件)代码;elsebreak;}，优点是跳针是无条件的，减少了比较次数。
[if !supportLists]l [endif]与枢纽元相等的i,j都不跳针（都停止），这是唯一不花费二次时间的可能。
[if !supportLists]l [endif]N<=20的小数组，快排不如插排，且5个数以下快排不可用。默认递归底cutoff=10。
//**********
public static > void swap(
AnyType[] a,int s1, int s2) {
AnyType tmp = a[s1];
a[s1] = a[s2];
a[s2] = tmp;
}
public static > AnyType median(
AnyType[] a,int left, int right) {
int center = (left + right) / 2;
if (a[left].compareTo(a[center])> 0)
swap(a, left,center);
if (a[left].compareTo(a[right])> 0)
swap(a, left,right);
if (a[center].compareTo(a[right])> 0)
swap(a, center,right);
swap(a, center, right - 1);
return a[right - 1];
}
public static > void quickSort(
AnyType[] a) {
quickSort(a, 0, a.length - 1);
}
public static > void quickSort(
AnyType[] a,int left, int right) {
int cutoff = 10;
if (right - left > cutoff) {
AnyType pivot =median(a, left, right);//重点：递归的函数要用形参，不要误用常量
int i = left;
int j = right -1;
while (true) {
while(a[++i].compareTo(pivot) < 0) {}
while(a[--j].compareTo(pivot) > 0) {}
if(i < j)
swap(a,i, j);
else
break;
}
swap(a,i,right-1);
quickSort(a,left,i-1);
quickSort(a,i+1,right);
} else {// cutoff个数以下用插排
for (int p =left+1; p <=right; p++) {//注意right处有值，因而p<=right
AnyTypeeject = a[p];
intj;
for(j = p; j > left && a[j - 1].compareTo(eject) > 0; j--)
a[j]= a[j - 1];
a[j]= eject;
}
}
}
//**********]
快速选择算法以O(N)时间解决选择问题（N个数中第k个最大值）
[if !supportLists]l [endif]三数中值分割选枢纽元：三数排序、并将枢纽元置末2位。
作用：选枢纽元、预分集两个数、防止出界。
[if !supportLists]l [endif]分集方法（半判断循还）：初始针让位、无条件跳针、非相遇换针、相遇退出。交换针i与枢纽元。
[if !supportLists]l [endif]递归子问题：在大理大、在小理"减大集数减1"地大。
k<=S2元素数递归quikSelect(S2,k)；k=S2元素数+1返回枢纽元；k> S2元素数+1递归quickSelect(S1,k-S2元素数-1)。
[if !supportLists]l [endif]递归底
快选与快排的区别仅是，快选只是单边递归子问题。
快选代码：
biggerNum=right-i;
if(k<=biggerNum)
quickSelect(a,i+1,right,k);
else if(k>right-i+1)
quickSelect(a,left,i-1,k-biggerNum-1);
else
return;
区别：插排前插，选排后选，向上相邻冒泡。复杂度都是O(N^2)。
补充选择排序
选择排序：外内双针，内针向后遍历，遇到更小则交换（共双循还）。
public static void selectSort(int[] a){
for(int i=0;i
for(intj=i+1;j
if(a[i]>a[j])
swap(a[i],a[j]);
}
补充冒泡排序：外层正序遍历，内层逆序遍历，冒泡相邻元素。
public static void bubbleSort(int[] a){
for(int i=0;i
for(intj=a.length;j>=0;j++)
if(a[j-1]>a[j])
swap(a[j-1],a[j]);
}
补充桶排序：。以元素值为桶索引进行装桶，拷回原数组。桶排快于快排却极耗空间，仅适用于小整数。复杂度O(M+N)，M为桶大小。
public static void bucketSort(int[] a,intmaxNumber){
int[] bucket=new int[maxNumber];
for(int i=0;i
bucket[a[i]]=a[i];
int writeBackPos=0;
for(inti=0;i
if(bucket[i]>0)//待排数组不含整数0
a[writeBackPos++]=bucket[i];
}
