聲明：該文章為個(gè)人學(xué)習(xí)筆記，非完全原創(chuàng)
總結(jié)一下各種經(jīng)典排序算法，這個(gè)也算面試?？嫉臇|西了，總結(jié)出來方便大家回憶回憶??，今天還要弄項(xiàng)目，先寫到快排，剩下的過幾天再寫。
一、冒泡排序
1.介紹
基于比較的排序算法，最簡單，性能差，即使最好情況時(shí)間復(fù)雜度也是O（n^2），（可以加一個(gè)附加標(biāo)記改進(jìn)算法，j）,原地排序
2.過程
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
3.例題
對(duì)于一個(gè)int數(shù)組，請(qǐng)編寫一個(gè)冒泡排序算法，對(duì)數(shù)組元素排序。
給定一個(gè)int數(shù)組A及數(shù)組的大小n，請(qǐng)返回排序后的數(shù)組。
測(cè)試樣例：
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
代碼（改良算法，增加了一個(gè)標(biāo)記，當(dāng)發(fā)現(xiàn)序列已經(jīng)是有序的時(shí)直接跳出循環(huán)）：
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.介紹
常用于數(shù)值大鍵值小的小文件。優(yōu)點(diǎn)是容易實(shí)現(xiàn)，不需要額外空間。
2.過程
尋找序列中最小值-》交換-》對(duì)所有元素重復(fù)
最好最壞平均時(shí)間復(fù)雜度都是O（n^2）
由于在CPU中交換比比較所需時(shí)間多，選擇排序比較多，但和冒泡排序比，交換次數(shù)少，所以更快。不穩(wěn)定性（相同鍵值的數(shù)據(jù)可能順序會(huì)變）
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.介紹
一種簡單有效的比較排序算法。
優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，數(shù)據(jù)量少時(shí)效率高，雖然最壞情況時(shí)間復(fù)雜度也是O（n^2），但實(shí)際運(yùn)行效率優(yōu)于前兩者（平均比較n2/2，交換n2/4次，最壞情況加倍），穩(wěn)定性，原地（額外空間O（1）），即時(shí)。適合數(shù)據(jù)幾乎都已經(jīng)排序或輸入規(guī)模較小時(shí)使用。最好情況O（n），對(duì)于部分有序的輸入來說幾乎就是線性排序（如果每個(gè)元素調(diào)整距離最大為k，即可令序列有序，且k相對(duì)序列長度很小，此時(shí)可認(rèn)為幾乎有序，此時(shí)時(shí)間復(fù)雜度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;
}
}
上述三個(gè)算法都是O（n^2）級(jí)別算法，下面介紹O（n*logn）級(jí)別算法
四、歸并排序
時(shí)間復(fù)雜度最好最壞平均都是O（nlogn），但是空間復(fù)雜度O（n），穩(wěn)定。網(wǎng)上有文章說可以把空間復(fù)雜度優(yōu)化到O（1），但是會(huì)犧牲時(shí)間效率。其實(shí)算法優(yōu)化也是一種時(shí)間和空間的權(quán)衡，用空間換時(shí)間或用時(shí)間換空間。
歸并排序使用分治思想，是建立在歸并操作（merge）上的一種有效的排序算法。注意下面代碼中歸并操作的做法，有一些題可能不是歸并排序，但是利用歸并操作的這個(gè)思想可以很好的解決。
大致過程如下：
將待排序序列R[0...n-1]看成是n個(gè)長度為1的有序序列，將相鄰的有序表成對(duì)歸并，得到n/2個(gè)長度為2的有序表；將這些有序序列再次歸并，得到n/4個(gè)長度為4的有序序列；如此反復(fù)進(jìn)行下去，最后得到一個(gè)長度為n的有序序列。即先把數(shù)組分解成n個(gè)小序列，再兩兩組合（二路歸并），要求組合后的新序列在序列內(nèi)有序。
與快排相似，也是通過遞歸實(shí)現(xiàn)。不過是先遞歸（分解），再歸并（組合）。歸并過程為：
我們每次從兩個(gè)列表開頭元素選取較小的一個(gè)，直到某一個(gè)列表到達(dá)底部，再將另一個(gè)剩下部分順序取出?？创a更好理解。下面上代碼：
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
sort(A,0,n-1);
return A;
}
//分割數(shù)組
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];
}
}
五、快排
基于比較的著名排序算法，是分治的一個(gè)實(shí)例，計(jì)算復(fù)雜度需要用分治法主定理。
1.算法：
a，如果數(shù)組中僅有一個(gè)元素或沒有元素需要排序，則返回（遞歸返回條件）
b，選擇一個(gè)元素作樞軸（pivot），把數(shù)組分為，小于pivot的元素，大于的兩部分（劃分）
c，對(duì)兩部分遞歸調(diào)用該算法。（遞歸）
2.性能
時(shí)間復(fù)雜度與上面的相比最好，平均O（nlogn）；最壞O（n2）（發(fā)生在數(shù)組已排序且選最后一個(gè)元素作樞軸的情況）?？臻g復(fù)雜度O（logn）~O（n2），因?yàn)槭沁f歸算法，需要利用?？臻g保存。不穩(wěn)定（可舉例證明）。
3.樞軸的選擇和優(yōu)化
a、若選擇數(shù)組最左邊或最右邊的元素作樞軸，可能由于非均衡劃分導(dǎo)致快排最壞情況發(fā)生，所以不好。
b、隨機(jī)選擇樞軸元素可以保證每個(gè)元素被選中概率相等，確保劃分在平均情況下均衡，防止最壞情況發(fā)生。
c、隨機(jī)選樞軸只是令劃分在平均情況下均衡。換句話說就是減小了最壞情況發(fā)生的概率，但實(shí)際上最壞情況時(shí)間復(fù)雜度還是O（n2）。我們可以想到如果能每次選所有元素的中位數(shù)作為樞軸，就能保證每次劃分都是均衡的。但顯然這樣做是不可能的，因?yàn)閷ふ覕?shù)組所有元素的中位數(shù)的時(shí)間開銷太大了。一個(gè)常用的方法是從數(shù)組中隨機(jī)選擇3個(gè)元素，取其中位數(shù)作為樞軸。
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提出而得名。是個(gè)不穩(wěn)定算法（不理解的話可以舉個(gè)例子）。
該算法本質(zhì)上就是一個(gè)泛化的插入排序，可以視作直接插入排序的改良。因?yàn)椴迦肱判蛟谛蛄袔缀跤行驎r(shí)效率很高，希爾排序通過先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的。
希爾排序最好情況時(shí)間復(fù)雜度為O（n），平均和最壞情況復(fù)雜度取決于步長序列（增量序列）的選擇。希爾排序最重要的也是步長選擇這一步。
Donald Shell 最初建議步長選擇為n/2，并且對(duì)步長取半直到步長達(dá)到 1。雖然這樣取可以比O(n^2)類的算法（插入排序）更好，但這樣仍然有減少平均時(shí)間和最差時(shí)間的余地。 可能希爾排序最重要的地方在于當(dāng)用較小步長排序后，以前用的較大步長仍然是有序的。
| 步長序列 | 最壞情況時(shí)間復(fù)雜度 |
| ------------- |:-------------:| -----:|
| n/(2^i) | O(n2) |
| 2i*3i | O(nlog2n) |
已知的最好步長序列由Marcin Ciura設(shè)計(jì)（1，4，10，23，57，132，301，701，1750，…） 這項(xiàng)研究也表明“比較在希爾排序中是最主要的操作，而不是交換。”用這樣步長序列的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。
另一個(gè)在大數(shù)組中表現(xiàn)優(yōu)異的步長序列是(斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分割比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列)：（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;
}
}
