- 一、选择排序
- 二、插入排序
- 三、希尔排序
- 四、归并排序
- 五、快速排序：
- 六、堆排序
算法描述：
首先找到数组中最小的元素，再将它与数组的第一个元素交换位置；再在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。它在不断的选择剩余元素中最小者，因此叫做选择排序。
优缺点：
1.运行时间和输入无关，为了找出最小的元素遍历一遍数组并不能为下一次遍历提供什么信息。一个排好序的数组所需的运行时间和随机顺序的数组运行时间一样长。
2.数据移动是最少的。选择排序用了N次交换，这与数组的大小是线性关系，其他算法都不具备这一特点（大部分都是线性对数或平方级别）
实现过程：
每次要找出剩余未排序的元素中最小的，要找N-1次，每次循环都是拿剩下未排序的第一个元素，去和其余的未排序的元素作比较，遍历其余未排序的元素，找到最小值的索引，将它与未排序的第一个元素交换。
public static void sort(Comparable[] a){
int n= a.length;
for(int i = 0; i < n - 1; i++){
//将a[i]与a[i+1..n-1]中最小的元素交换
int min = i; //最小元素的索引
for(int j = i + 1; j < n; j++){
if(less(a[j],a[i]))
min = j;
}
exch(a,i,min);
}
}
二、插入排序
算法描述：
与整理扑克牌相似，将每一张牌插入到其他已经有序的牌的适当位置。为了给插入的元素腾空间，需要将其余所有元素在插入之前都向右移动一位。当前索引的左边都是有序的，但它们的最终位置还不确定，为了给更小的元素腾空间，它们可能被移动，当索引达到数组的右端时，排序就完成了。
优缺点：
所需时间取决于元素的初始顺序，如果数组已经接近有序，或者部分有序，那么速度将会很快，但如果是逆序，大规模乱序，将会很慢，因为它只会交换相邻的元素，元素只能一点一点地进行移动。
实现过程：
类比摸牌的过程，从第二张牌开始进行插入，依次与前面已经排好序的牌进行比较，找到合适的插入位置
如下图所示：前面5位已经排好序，此时i = 5，a[i] = 4,然后令当前值j = i,用当前值与前一位比较，当前的值更小则交换位置，当前的值更大则停止
1 2 5 6 7 4 j = i= 5，a[j]与a[j-1]进行比较，当前值更小则进行交换
1 2 5 6 4 7 j = 4, a[j]与a[j-1]进行比较，当前值更小则进行交换
1 2 5 4 6 7 j = 3, a[j]与a[j-1]进行比较，当前值更小则进行交换
1 2 4 5 6 7 j = 2, a[j]与a[j-1]进行比较，当前值更大，停止。
public static void sort(Comparable[] a){
int n= a.length;
for(int i = 1; i < n; i++){
for(int j = i; j > 0 && less(a[j],a[j-1]); j--){
exch(a,j,j-1);
}
}
}
三、希尔排序
算法描述：
希尔排序相当于插入排序的改进，插入排序每次只能交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度，交换不相邻的元素以对数组的局部进行排序，并最终通过插入排序将局部有序的数组排序。思想：使数组中任意间隔为h的元素都是有序的，这样的数组被称为h有序数组。实现：对于每个h，用插入排序将h个子数组独立地排序。
优缺点：
显著提高了排序的速度，特别是在大规模数据上。
实现过程：
确定以1结尾的h序列，找到h的最大值，用插入排序将数组变为h有序。前h个元素相当于插入排序中的第一张牌，故从第h+1张牌开始进行插入，后面的每个元素都与前面依次相隔h的元素进行比较，当前元素更小就交换位置，否则不动。找到的正确位置。完成后将h缩小再次重复，直到h=1即完成排序。
public static void Shell(Comparable[] a){
int h = 1;
int n = a.length;
while(h < n/3){
h = 3 * h + 1;
}
while(h >= 1){
//将数组变为h有序
for(int i = h; i < n;i++){
//将a[i]插入到a[i-h],a[i-2h],a[i-3h]...之中
for(int j = i; j >=h && less(a[j],a[j-h]); j-=h){
exch(a,j,j-h);
}
}
h = h/3;
}
}
四、归并排序
先递归地将数组从中间分为两个子数组，直到不能再分后进行子数组的归并，每次取两个子数组中第一个元素更小的。
算法描述：
要将一个数组排序，可以先（递归地）将它分为两半分别排序，然后将结果归并起来。
优缺点：
任意长度为N的数组排序所需时间和NlogN成正比；缺点是所需的额外空间和N成正比。
实现过程：
自顶向下：对一个大数组排序，先分为两个子数组，将左边排序，再将右边排序，以此递归，再归并结果。
自底向上：先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到我们将整个数组归并到一起。首先我们进行两两归并（把每个元素想象成长度为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组）······最后一次归并第二个子数组可能比第一个小，但对merge()方法不是问题。
核心：原地归并的方法：它会将两个已经有序的子数组a[lo…mid]和a[mid+1…hi]归并成一个有序的数组并将结果存放在a[lo…hi]中。先将整个数组放入辅助数组中，每次比较两个子数组的第一个元素，将更小的元素放入数组
//归并
public static void merge(Comparable[] a, int lo, int mid, int hi){
int i = lo;
int j = mid + 1;
//将a[lo...hi]复制到辅助数组aux[lo...hi]中。
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = i; k <= hi; k++) {
if(i > mid) {
a[k] = aux[j++];
}else if (j > hi){
a[k] = aux[i++];
}else if(less(aux[i],aux[j])){
a[k] = aux[i++];
}else
a[k] = aux[j++];
}
}
//自顶向下
public static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a, int lo, int hi){
if(hi<=lo) return;
int mid = lo + (hi - lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
//自底向上
public static void sort1(Comparable[] a){
//进行logN次两两排序
int n = a.length;
aux = new Comparable[n];
for (int sz = 1; sz < n; sz =sz + sz ) {
for (int lo = 0; lo < n-sz; lo += sz + sz){
merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,n-1));
}
}
}
五、快速排序：
先切分，再递归两个子数组排序。切分：左右两端两个指针与切分元素比较并互换，直至相遇。
算法描述：
快速排序是一种分治的排序算法，它将数组分成两个子数组，将两部分独立地排序。当两个子数组都有序时整个数组也就有序了。与归并排序相比，快速排序的递归调用发生在处理整个数组之后。
优缺点：
它是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间与NlogN成正比。缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。和归并排序对比，快排可以理解成先治再分，归并可以理解成先分再治。
实现过程：
核心是如何实现对数组的切分。先取一个切分元素，可以取数组中间位置的值，也可以就取数组的第一个元素。要实现切分元素的左边全部是小于切分元素的元素，右边全部是大于切分元素的元素。可以在数组的两端定义一个指针，左边的指针向右移动，每次找大于切分元素停下来，右边指针向左移动，每次找到小于切分元素停下来，若右指针仍然在左指针的右边，则交换两个指针所指的元素，若右指针在左指针左边则说明已经完成切分，退出循环。最后将切分元素放到正确的位置。
递归实现：
public class quickSort {
public static void sort(Comparable[] a){
//。。这里应该先将数据随机打乱
sort(a,0,a.length-1);
}
//方式一：切分元素取数组元素的第一个元素
public static void sort(Comparable[] a, int lo, int hi){
if(hi<=lo) return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
public static int partition(Comparable[] a, int lo, int hi){
int i = lo, j = hi + 1;
Comparable v = a[lo]; //切分元素取数组的第一个元素
while(true){
while(less(a[++i], v)) if(i==hi) break;
while(less(v, a[--j])) if(j==lo) break;
//易错
if(i >= j) break;
exch(a, i, j);
}
//此时j指向一个比v小的元素，且j的右边全是比v大的元素
exch(a, lo, j);
return j; //a[lo...j-1] <= a[j] <= a[j+1...hi]达成
}
//方式二：切分元素取数组中间位置的元素
public static void quicksort(Comparable[] a, int start, int end){
if(start >= end) return;
int left = start, right = end;
Comparable pivot = a[start + (end - start)/2];
while (left <= right){
while(less(a[left],pivot) && left <= right)
left++;
while (less(pivot,a[right]) && right >= left)
right--;
if(left <= right){
exch(a,left,right);
left++;
right--;
}
}
quicksort(a,start,right);
quicksort(a,left,end);
}
}
六、堆排序
构建堆，修复堆
描述：用优先队列实现的排序算法。将所有元素插入到一个查找最大元素的优先队列，然后重复调用删除最大元素的操作来将它们按顺序删去。
优缺点：时间复杂度NlogN，空间复杂度1,。
实现过程：堆排序分为两个阶段，构造堆和修复堆。构造堆的目标是产生一个堆有序的结果。可以对数组从右至左用sink()函数构造子堆，开始时我们只需要扫描数组一半的元素，因为可以跳过大小为1的子堆，即叶子结点不用调用sink()。修复堆的过程是每次都先交换堆顶的元素和最后一个元素，并让堆的大小减1，再对第一个元素调用sink()下沉合理位置修复堆。循环操作直到堆的大小等于1时退出循环。
核心：sink()函数，将结点下沉到合适的位置。当结点没有子结点或者结点已经处于正确的位置时，循环退出。循环时每次找出该结点的两个子结点中的较大者，与之进行比较，若该结点更小，则互换位置，若该结点更大，说明该结点处于正确的位置上，循环结束。
public class HeapSort {
private void exch(Comparable[] a, int i, int j){
Comparable t = a[i-1];
a[i-1] = a[j-1];
a[j-1] = t;
}
private boolean less(Comparable[] a, int i, int j){
return a[i-1].compareTo(a[j-1]) < 0;
}
private void sink(Comparable[] a, int k, int N){
while(2*k <= N){ //首先要求存在子结点
int j = 2*k;
if(j < N && less(a,j,j + 1)){
j++;
}
//若小于子结点中的较大者，则与之交换，否则说明该结点比两个子结点都要大，位于正确位置，循环退出
if(less(a, k, j)){
exch(a, k, j);
k = j;
}else break;
}
}
public void sort(Comparable[] a){
int N = a.length;
//1.构造堆,从右至左调用sink
for(int k = N/2; k >= 1; k--){
sink(a, k, N);
}
//2.循环删除最大元素，并调用sink修复堆
while(N > 1){
exch(a, 1, N--);
sink(a, 1, N);
}
}
}
