经典排序（一）
声明：该文章为个人学习笔记，非完全原创
总结一下各种经典排序算法，这个也算面试常考的东西了，总结出来方便大家回忆回忆😁，今天还要弄项目，先写到快排，剩下的过几天再写。
一、冒泡排序
1.介绍
基于比较的排序算法，最简单，性能差，即使最好情况时间复杂度也是O（n^2），（可以加一个附加标记改进算法，j）,原地排序
2.过程
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3.例题
对于一个int数组，请编写一个冒泡排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
代码（改良算法，增加了一个标记，当发现序列已经是有序的时直接跳出循环）：
import java.util.*;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
// write code here
int temp;
int tag=0;
for(int i =n;i>1;i--){
for(int j = 0;j<i-1;j++){
if(A[j]>A[j+1]){
tag=1;
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
if(tag==0)
break;
tag=0;
}
return A;
}
}
二、选择排序
1.介绍
常用于数值大键值小的小文件。优点是容易实现，不需要额外空间。
2.过程
寻找序列中最小值-》交换-》对所有元素重复
最好最坏平均时间复杂度都是O（n^2）
由于在CPU中交换比比较所需时间多，选择排序比较多，但和冒泡排序比，交换次数少，所以更快。不稳定性（相同键值的数据可能顺序会变）
3.代码
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
int tmp=A[j];
A[j] = A[j+1];
A[j+1] =tmp;
}
}
return A;
}
}
三、插入排序
1.介绍
一种简单有效的比较排序算法。
优点：实现简单，数据量少时效率高，虽然最坏情况时间复杂度也是O（n^2），但实际运行效率优于前两者（平均比较n²/2，交换n²/4次，最坏情况加倍），稳定性，原地（额外空间O（1）），即时。适合数据几乎都已经排序或输入规模较小时使用。最好情况O（n），对于部分有序的输入来说几乎就是线性排序（如果每个元素调整距离最大为k，即可令序列有序，且k相对序列长度很小，此时可认为几乎有序，此时时间复杂度O（kn））。
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
int i, j, temp;
for(i = 1; i < n; i++){
temp = A[i];
for(j = i; j > 0 && A[j - 1] > temp; j-- ){
A[j] = A[j - 1];
}
A[j] = temp;
}
return A;
}
}
上述三个算法都是O（n^2）级别算法，下面介绍O（n*logn）级别算法
四、归并排序
时间复杂度最好最坏平均都是O（nlogn），但是空间复杂度O（n），稳定。网上有文章说可以把空间复杂度优化到O（1），但是会牺牲时间效率。其实算法优化也是一种时间和空间的权衡，用空间换时间或用时间换空间。
归并排序使用分治思想，是建立在归并操作（merge）上的一种有效的排序算法。注意下面代码中归并操作的做法，有一些题可能不是归并排序，但是利用归并操作的这个思想可以很好的解决。
大致过程如下：
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。即先把数组分解成n个小序列，再两两组合（二路归并），要求组合后的新序列在序列内有序。
与快排相似，也是通过递归实现。不过是先递归（分解），再归并（组合）。归并过程为：
我们每次从两个列表开头元素选取较小的一个，直到某一个列表到达底部，再将另一个剩下部分顺序取出。看代码更好理解。下面上代码：
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
sort(A,0,n-1);
return A;
}
//分割数组
public void sort(int[] A,int l,int r){
if(l<r){
int mid;
mid=(l+r)/2;
sort(A,l,mid);
sort(A,mid+1,r);
merge(A,l,mid,r);
}
}
//归并
public void merge(int[] A,int l, int mid, int r){
int i=l;
int j=mid+1;
int k=l;
int t;
int[] temp = new int[A.length];
while(i<=mid&&j<=r){
if(A[i]<=A[j])
temp[k++]=A[i++];
else
temp[k++]=A[j++];
}
while(i<=mid){
temp[k++]=A[i++];
}
while(j<=r)
temp[k++]=A[j++];
for(t=l;t<=r;t++)
A[t]=temp[t];
}
}
五、快排
基于比较的著名排序算法，是分治的一个实例，计算复杂度需要用分治法主定理。
1.算法：
a，如果数组中仅有一个元素或没有元素需要排序，则返回（递归返回条件）
b，选择一个元素作枢轴（pivot），把数组分为，小于pivot的元素，大于的两部分（划分）
c，对两部分递归调用该算法。（递归）
2.性能
时间复杂度与上面的相比最好，平均O（nlogn）；最坏O（n²）（发生在数组已排序且选最后一个元素作枢轴的情况）。空间复杂度O（logn）~O（n²），因为是递归算法，需要利用栈空间保存。不稳定（可举例证明）。
3.枢轴的选择和优化
a、若选择数组最左边或最右边的元素作枢轴，可能由于非均衡划分导致快排最坏情况发生，所以不好。
b、随机选择枢轴元素可以保证每个元素被选中概率相等，确保划分在平均情况下均衡，防止最坏情况发生。
c、随机选枢轴只是令划分在平均情况下均衡。换句话说就是减小了最坏情况发生的概率，但实际上最坏情况时间复杂度还是O（n²）。我们可以想到如果能每次选所有元素的中位数作为枢轴，就能保证每次划分都是均衡的。但显然这样做是不可能的，因为寻找数组所有元素的中位数的时间开销太大了。一个常用的方法是从数组中随机选择3个元素，取其中位数作为枢轴。
4.代码
import java.util.*;
public class QuickSort {
public int[] quickSort(int[] A, int n) {
// write code here
sort(A,0,n-1);
return A;
}
void sort(int[] A,int l,int r){
int pivot;
if(l<r){
pivot=partition(A,l,r);
sort(A,l,pivot-1);
sort(A,pivot+1,r);
}
}
int partition(int[] A,int l,int r){
int i=l;
int j=r;
int t=l-1;
Random rand= new Random();
int p=l+rand.nextInt(r-l+1);
swap(A,r,p);
for(;i<r;i++){
if(A[i]<A[p]){
swap(A,i,++t);
}
}
swap(A,r,++t);
return t;
}
void swap(int[] A,int a,int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
}
六、希尔排序
希尔排序，又叫缩小增量排序（看到后面你就知道为什么这么叫了），由Donnald Shell提出而得名。是个不稳定算法（不理解的话可以举个例子）。
该算法本质上就是一个泛化的插入排序，可以视作直接插入排序的改良。因为插入排序在序列几乎有序时效率很高，希尔排序通过先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。
希尔排序最好情况时间复杂度为O（n），平均和最坏情况复杂度取决于步长序列（增量序列）的选择。希尔排序最重要的也是步长选择这一步。
Donald Shell 最初建议步长选择为n/2，并且对步长取半直到步长达到 1。虽然这样取可以比O(n^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。 可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。
| 步长序列 | 最坏情况时间复杂度 |
| ------------- |:-------------:| -----:|
| n/(2^i) | O(n²) |
| 2i*3i | O(nlog²n) |
已知的最好步长序列由Marcin Ciura设计（1，4，10，23，57，132，301，701，1750，…） 这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）
代码(步长选择n/(2^i))：
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] A, int n) {
int h,i,j,temp;
for(h=n/2;h>=1;h=h/2){
for(i=h;i<n;i++){
temp=A[i];
j=i;
for(;j>=h&&A[j-h]>temp;){
A[j]=A[j-h];
j=j-h;
}
A[j]=temp;
}
}
return A;
}
}
