本文主要整理了九種經典的內部排序算法饥臂。
1.冒泡排序
原理：
冒泡排序是一種簡單的排序算法樊破。它重復地走訪過要排序的數列缅疟，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來淮菠。走訪數列的工作是重復地進行直到沒有再需要交換男公，也就是說該數列已經排序完成。
步驟：
- 比較相鄰的元素合陵。如果第一個比第二個大枢赔，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作拥知，從開始第一對到結尾的最后一對踏拜。這步做完后，最后的元素會是最大的數低剔。
- 針對所有的元素重復以上的步驟速梗，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟襟齿，直到沒有任何一對數字需要比較姻锁。
冒泡排序.gif
實現：
public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j].compareTo(arr[j+1]) > 0) {
swap(arr,j,j+1);
}
}
}
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
算法優(yōu)化：
優(yōu)化1：某一趟遍歷如果沒有數據交換，則說明已經排好序了猜欺，因此不用再進行迭代了位隶。用一個標記記錄這個狀態(tài)即可。
優(yōu)化2：記錄某次遍歷時最后發(fā)生數據交換的位置开皿，這個位置之后的數據顯然已經有序涧黄，不用再排序了。因此通過記錄最后發(fā)生數據交換的位置就可以確定下次循環(huán)的范圍了赋荆。
2.選擇排序
原理：
選擇排序是一種簡單直觀的排序算法笋妥。
步驟：
- 首先在未排序序列中找到最小（大）元素窄潭，存放到排序序列的起始位置挽鞠。
- 再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾信认。
- 以此類推材义，直到所有元素均排序完畢。
選擇排序.gif
實現：
public static void sort(Comparable[] arr ){
int n=arr.length;
for ( int i=0;i<n;i++){
int minIndex =i;
for ( int j=i+1;j<n;j++){
if (arr[j].compareTo( arr[minIndex])<0){
minIndex=j;
}
swap(arr,i,minIndex);
}
}
}
private static void swap(Object[] arr, int i, int j ){
Object t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
3.插入排序
原理：
插入排序是一種簡單直觀的排序算法嫁赏。它的工作原理是通過構建有序序列其掂，對于未排序數據，在已排序序列中從后向前掃描潦蝇，找到相應位置并插入款熬。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序）攘乒，因而在從后向前掃描過程中贤牛，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間则酝。
步驟：
- 從第一個元素開始殉簸，該元素可以認為已經被排序。
- 取出下一個元素沽讹，在已經排序的元素序列中從后向前掃描般卑。
- 如果該元素（已排序）大于新元素，將該元素移到下一位置爽雄。
- 重復步驟3蝠检，直到找到已排序的元素小于或者等于新元素的位置，將新元素插入到該位置后挚瘟。
- 重復步驟2~5
插入排序.gif
實現：
public static void sort(Comparable[] arr, int l, int r) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = i; j>0; j--) {
if (arr[j].compareTo(arr[j-1])<0){
swap( arr, j , j-1);
}else
break;
}
}
4.希爾排序
原理：
希爾排序叹谁，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本乘盖。希爾排序是非穩(wěn)定排序算法本慕。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]侧漓，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法监氢，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數字布蔗，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）浪腐。
步驟：
- 先取一個正整數 d1(d1 < n)纵揍，把全部記錄分成 d1 個組，所有距離為 d1 的倍數的記錄看成一組议街，然后在各組內進行插入排序泽谨。
- 然后取 d2(d2 < d1)。
- 重復上述分組和排序操作；直到取 di = 1(i >= 1) 位置吧雹，即所有記錄成為一個組骨杂，最后對這個組進行插入排序。一般選 d1 約為 n/2雄卷，d2 為 d1 /2搓蚪， d3 為 d2/2 ，…丁鹉， di = 1妒潭。
希爾排序.gif
實現：
public static void sort(Comparable[] arr){
int n = arr.length;
// 計算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) { //控制按不同組距進行插入排序
// h-sort the array
for (int i = h; i < n; i++) {
// 對 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
Comparable e = arr[i];
int j = i;
for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h)
arr[j] = arr[j-h];
arr[j] = e;
}
h /= 3;
}
}
5.歸并排序
原理：
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用揣钦。
歸并操作(Merge)雳灾，也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作冯凹。歸并排序算法依賴歸并操作谎亩。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內排序谈竿，也可以用于外排序团驱。這里僅對內排序的兩路歸并方法進行討論。
步驟：
迭代法(自底向上)
- 申請空間空凸，使其大小為兩個已經排序序列之和嚎花，該空間用來存放合并后的序列。
- 設定兩個指針呀洲，最初位置分別為兩個已經排序序列的起始位置紊选。
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間道逗，并移動指針到下一位置兵罢。
- 重復步驟3直到某一指針到達序列尾。
- 將另一序列剩下的所有元素直接復制到合并序列尾滓窍。
遞歸法(自頂向下)
- 將序列每相鄰兩個數字進行歸并操作卖词，形成floor(n/2)個序列，排序后每個序列包含兩個元素吏夯。
- 將上述序列再次歸并此蜈，形成floor(n/4)個序列，每個序列包含四個元素
- 重復步驟2噪生，直到所有元素排序完畢
歸并排序.gif
實現：
迭代法
private static void merge(Comparable[] arr, int l, int mid, int r) {
Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
// 初始化裆赵，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已經全部處理完畢
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已經全部處理完畢
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
public static void sort(Comparable[] arr){
int n = arr.length;
for (int sz = 1; sz < n; sz *= 2)
for (int i = 0; i < n - sz; i += sz+sz) //sz+zs將i移到下一個分組
// 對 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 進行歸并
merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1)); //當左后一個一組組長不足sz時將i+sz+sz-1與n-1進行比較
}
遞歸法（自頂向下）
// 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并
private static void merge(Comparable[] arr, int l, int mid, int r){
Comparable[] aux = Arrays.copyOfRange(arr, l,r+1);
// 初始化跺嗽，i指向左半部分的起始索引位置l战授；j指向右半部分起始索引位置mid+1
int i = l , j = mid + 1;
for (int k = l; k <= r ; k++) {
if( i > mid ){ // 如果左半部分元素已經全部處理完畢
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已經全部處理完畢
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
private static void sort( Comparable[] arr , int l, int r){
if (l >= r)
return;
int mid = (l + r) / 2;
sort(arr, l, mid);
sort(arr, mid+1, r);
merge(arr, l, mid, r);
}
6.快速排序
原理：
快速排序页藻，又稱劃分交換排序。在平均狀況下,排序n個項目要Ο(nlogn)次比較植兰。在最壞狀況下則需要Ο(n^2)次比較,但這種狀況并不常見份帐。事實上,快速排序通常明顯比其他Ο(nlogn)算法更快,因為它的內部循環(huán)(inner loop)可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）钉跷。
步驟：
- 從數列中挑出一個元素弥鹦，稱為"基準"（pivot）。
- 重新排序數列爷辙，所有比基準值小的元素擺放在基準前面彬坏，所有比基準值大的元素擺在基準后面（相同的數可以到任一邊）。在這個分區(qū)結束之后膝晾，該基準就處于數列的中間位置栓始。這個稱為分區(qū)（partition）操作。
- 遞歸地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序血当。
快速排序(1).gif
快速排序(2).gif
實現：
private static int partition(Comparable[] arr, int l, int r){
//隨機在arr[l……r]范圍中 選擇一個數值作為標定點pivot幻赚，進行簡單優(yōu)化
swap(arr, l ,(int)( Math.random()*( r - l + 1))+l);
Comparable copy = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for (int i = l+1 ; i <= r; i++) {
if (arr[i].compareTo(copy) < 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
private static void swap(Object[] arr, int i, int j){
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 遞歸使用快速排序,對arr[l...r]的范圍進行排序
private static void sort(Comparable[] arr, int l, int r){
if ( l >= r)
return;
int p = partition(arr, l, r);
sort(arr, l, p-1);
sort(arr, p+1, r);
}
算法優(yōu)化
- 小數組時，切換到插入排序臊旭。對于小數組落恼，快排比插入排序要慢；
- 三路快排离熏，主要是對于有重復元素的情況下佳谦，將數組切分為三部分，分別是小于滋戳，等于和大于切分元素的數組元素钻蔑。
// 三路快排的實現
private static void sort(Comparable[] arr, int l, int r){
Comparable copy = arr[l];
// 對于小規(guī)模數組, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr,l,r);
return;
}
// 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot
swap( arr , l ,(int)(Math.random() * (r - l + 1)) +1);
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while ( i < gt){
if ( arr[i].compareTo(copy)<0 ){
swap(arr,i ,lt+1);
i++;
lt++;
}
else if ( arr[i].compareTo(copy)>0 ){
swap( arr, i, gt-1);
gt--;
}
else {
i++;
}
}
swap( arr , l, lt);
sort( arr, l, lt-1);
sort( arr, gt, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
7.堆排序
原理：
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構奸鸯，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點咪笑。
步驟：
通常堆是通過一維數組來實現的。在數組起始位置為0的情形中：
父節(jié)點i的左子節(jié)點在位置(2i+1);
父節(jié)點i的右子節(jié)點在位置(2i+2);
子節(jié)點i的父節(jié)點在位置floor((i-1)/2)娄涩。
在堆的數據結構中窗怒，堆中的最大值總是位于根節(jié)點(在優(yōu)先隊列中使用堆的話堆中的最小值位于根節(jié)點)。堆中定義以下幾種操作：
最大堆調整（Max_Heapify）：將堆的末端子節(jié)點作調整蓄拣，使得子節(jié)點永遠小于父節(jié)點
創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數據重新排序
堆排序（HeapSort）：移除位在第一個數據的根節(jié)點扬虚，并做最大堆調整的遞歸運算
堆排序.gif
實現：
public class HeapSort {
private HeapSort() {}
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = (n-1-1)/2; i >=0 ; i--) {
shiftDown(arr, n ,i);
}
//依次取出最大元素放在數組最后，對剩下數據重新建立最大堆
for (int i = n-1; i >0 ;i--) {
swap(arr,0, i);
shiftDown(arr, i, 0);
}
}
// 交換堆中索引為i和j的兩個元素
private static void swap(Object[] arr, int i, int j){
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
private static void shiftDown(Comparable[] arr, int n, int k){
while( 2*k+1 < n ){
int j = 2*k+1;
if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
j += 1;
if( arr[k].compareTo(arr[j]) >= 0 )break;
swap( arr, k, j);
k = j;
}
}
8.基數排序
原理：
基數排序是一種非比較型整數排序算法弯蚜，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較剃法。
步驟：
- 將所有待比較數值（正整數）統(tǒng)一為同樣的數位長度碎捺，數位較短的數前面補零。
- 從最低位開始，依次進行一次排序收厨。
- 這樣從最低位排序一直到最高位排序完成以后晋柱，數列就變成一個有序序列。
基數排序.jpg
實現：
public class RadixSort
{
public static void sort(int[] number, int d) //d表示最大的數有多少位
{
intk = 0;
intn = 1;
intm = 1; //控制鍵值排序依據在哪一位
int[][]temp = newint[10][number.length]; //數組的第一維表示可能的余數0-9
int[]order = newint[10]; //數組orderp[i]用來表示該位是i的數的個數
while(m <= d)
{
for(inti = 0; i < number.length; i++)
{
intlsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(inti = 0; i < 10; i++)
{
if(order[i] != 0)
for(intj = 0; j < order[i]; j++)
{
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
public static void main(String[] args)
{
int[]data =
{73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
RadixSort.sort(data, 3);
for(inti = 0; i < data.length; i++)
{
System.out.print(data[i] + "");
}
}
}
9.計數排序
原理：
計數排序（Counting sort）是一種穩(wěn)定的線性時間排序算法诵叁。計數排序使用一個額外的數組C雁竞，其中第i個元素是待排序數組A中值等于i的元素的個數。然后根據數組C來將A中的元素排到正確的位置拧额。
步驟：
- 找出待排序的數組中最大和最小的元素碑诉。
- 統(tǒng)計數組中每個值為i的元素出現的次數，存入數組 C 的第 i 項侥锦。
- 對所有的計數累加（從C中的第一個元素開始进栽，每一項和前一項相加）。
- 反向填充目標數組：將每個元素i放在新數組的第C(i)項恭垦，每放一個元素就將C(i)減去1快毛。
計數排序.gif
實現：
public class CountingSort {
public static void main(String[] argv) {
int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
Utils.print(A);
}
public static int[] countingSort(int[] A) {
int[] B = new int[A.length];
// 假設A中的數據a'有，0<=a' && a' < k并且k=100
int k = 100;
countingSort(A, B, k);
return B;
}
private static void countingSort(int[] A, int[] B, int k) {
int[] C = new int[k];
// 計數
for (int j = 0; j < A.length; j++) {
int a = A[j];
C[a] += 1;
}
Utils.print(C);
// 求計數和
for (int i = 1; i < k; i++) {
C[i] = C[i] + C[i - 1];
}
Utils.print(C);
// 整理
for (int j = A.length - 1; j >= 0; j--) {
int a = A[j];
B[C[a] - 1] = a;
C[a] -= 1;
}
}
}
//針對c數組的大小番挺，優(yōu)化過的計數排序
public class CountSort{
public static void main(String []args){
//排序的數組
int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
int b[] = countSort(a);
for(int i : b){
System.out.print(i + " ");
}
System.out.println();
}
public static int[] countSort(int []a){
int b[] = new int[a.length];
int max = a[0], min = a[0];
for(int i : a){
if(i > max){
max = i;
}
if(i < min){
min = i;
}
}
//這里k的大小是要排序的數組中唠帝，元素大小的極值差+1
int k = max - min + 1;
int c[] = new int[k];
for(int i = 0; i < a.length; ++i){
c[a[i]-min] += 1;//優(yōu)化過的地方，減小了數組c的大小
}
for(int i = 1; i < c.length; ++i){
c[i] = c[i] + c[i-1];
}
for(int i = a.length-1; i >= 0; --i){
b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
}
return b;
}
}
各種排序算法比較復雜度比較
各種排序算法比較復雜度比較.png
