幾種排序算法（Java）

文章目錄

• • 0.1算法複雜度表
  • 0.2相關概念
  • 0.3動圖示範
• 1.冒泡排序
• • 1.1算法描述
  • 1.2代碼實作
• 2.選擇排序
• • 2.2代碼實作
• 3.插入排序
• • 3.1算法描述
  • 3.2代碼實作
• 4.歸并排序
• • 4.1算法描述
  • 4.2算法分析
  • 4.3代碼實作
• 5.快速排序
• • 5.1算法描述
  • 5.3算法分析
  • 5.4代碼實作
• 6.桶排序
• • 1.算法描述
  • 2.算法分析
  • 3.代碼實作
• 7.基數排序
• • 1.算法描述
  • 2.算法分析
  • 3.代碼實作
• 8.堆排序
• • 1.算法描述
  • 2.算法分析
  • 3.代碼實作

0.1算法複雜度表

0.2相關概念

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面。

不穩定：如果a原本在b的前面，而a=b，排序之後 a 可能會出現在 b 的後面。

關于穩定性的意義：

如果我問你：排序算法的「穩定性」有何意義？你怎麼回答？

0.3動圖示範

十大經典算法（動圖示範）

1.冒泡排序

排序時相鄰兩對元素進行比較，從第一對進行到最後一對，較大的元素交換到後方，因為大數像氣泡一樣從前往後移動，是以叫冒泡排序。

1.1算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• 針對所有的元素重複以上的步驟，除了最後一個（最後一個數已經是上一次排序後最大的數）；
• 重複步驟1~3，直到排序完成。

1.2代碼實作

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對比
                var temp = arr[j+1];        // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
           

2.選擇排序

在每次排序後，在未排序元素中選出最小的元素，将它放在已排序元素的後邊。一開始全是未排序元素，每次循環将一個最小元素放在前方，是以每次循環開始時前i個元素以排序。

選擇排序是較穩定的排序，無論參數怎樣改變，時間複雜度都是O(n^2)，不像其他排序算法一樣有好壞情況（歸并排序等也具有此特性）。

2.2代碼實作

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數
                minIndex = j;                 // 将最小數的索引儲存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
} 
           

3.插入排序

通過建構已排序序列，對于未排序的元素，将其從已排序序列的尾部向前掃描，将其插入到對應的序列進而不斷擴大已排序序列。

3.1算法描述

1.從第一個元素開始，該元素可以認為已經被排序；

2.取出下一個元素，在已經排序的元素序列中從後向前掃描；

3.如果該元素（已排序）大于新元素，将該元素移到下一位置；

4.重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到該位置後；

6.重複步驟2~5。

3.2代碼實作

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
           

4.歸并排序

該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

4.1算法描述

1.把長度為n的輸入序列分成兩個長度為n/2的子序列；

2.對這兩個子序列分别采用歸并排序；

3.将兩個排序好的子序列合并成一個最終的排序序列。

通過遞歸不斷進行此過程，遞歸到最後隻剩下兩個元素間或者一個元素的歸并。

4.2算法分析

分治思想的使用在于sort方法通過遞歸實作了将原數組的分解，merge算法通過被sort在遞歸中一次次調用又将數組 排序後合了起來。

merge方法設計的時候是按照一個數組mid的左右兩部分是排好序的的情況設計的，因為merge在sort中被遞歸調用，在遞歸的最後最深處左右兩個數（或一個數）可以看作是已排好序的，然後遞歸一直傳回的數組左右兩邊就都是排好序的了。

sort()方法在設計的時候引入了mid，進而實作将數組分成兩個的情況。

對于時間複雜度：O(nlogn)，代表的是執行了logn次n，因為遞歸每次都将數組分成兩半，是以要執行logn次，每次都要進行merge而merge的複雜度是n，是以執行logn次n，即為nlogn。

代碼具體講解：馬士兵說：歸并排序，java對象排序的預設算法

以及：馬士兵說：歸并排序（二），程式是調出來的，請大家一定要學會修複BUG

4.3代碼實作

作者：優課達
連結：https://zhuanlan.zhihu.com/p/127843825
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

public static void mergeSort(int[] array) {
	if (array == null || array.length <= 1) {
		return;
	}

	sort(array, 0, array.length - 1);
}

private static void sort(int[] array, int left, int right) {
	if (left == right) {
		return;
	}
	int mid = left + ((right - left) >> 1);
	// 對左側子序列進行遞歸排序
	sort(array, left, mid);
	// 對右側子序列進行遞歸排序
	sort(array, mid + 1, right);
	// 合并
	merge(array, left, mid, right);
}

private static void merge(int[] array, int left, int mid, int right) {
	int[] temp = new int[right - left + 1];
	int i = 0;
	int p1 = left;
	int p2 = mid + 1;
	// 比較左右兩部分的元素，哪個小，把那個元素填入temp中
	while (p1 <= mid && p2 <= right) {
		temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
	}
	// 上面的循環退出後，把剩餘的元素依次填入到temp中
	// 以下兩個while隻有一個會執行
	while (p1 <= mid) {
		temp[i++] = array[p1++];
	}
	while (p2 <= right) {
		temp[i++] = array[p2++];
	}
	// 把最終的排序的結果複制給原數組
	for (i = 0; i < temp.length; i++) {
		array[left + i] = temp[i];
	}
}
           

5.快速排序

通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

5.1算法描述

1.從數列中挑出一個元素，稱為 “基準”（pivot）；

2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；

3.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

5.3算法分析

這裡假設首先将數組的第一個元素當做基準數，定義兩個指針i和j，j從尾往前找比基準數小的數，找到了就停下；i從頭往後找比基準數大的數，找到了就停下。當兩個指針都停下後，交換i和j位置上的值，然後繼續移動i和j直到二者相遇。相遇後就交換基準數和相遇位置上的數，進而做到基準數左邊的數都比他小，右邊的數都比他大。然後遞歸即可。

代碼具體講解：java快速排序講解

5.4代碼實作

public static void quickSort(int[] arr, int left, int rigth) {
    if(left>rigth) {
        return;
    }

	//這裡是将left和right間的随機數作為基數，否則的話最壞情況下遞歸樹将退化為連結清單，時間複雜度是O(n)，可加可不加
    if (right > left) { //擷取随機數作為基數，left和right相等的時候不用
        int randomIndex = left+(int) (Math.random()*(right-left+1));
        swap(nums, left, randomIndex);
    }
    
    int base = arr[left];//定義儲存基準數
    int i = left;//定義變量i指向最左邊
    int j = rigth;//定義變量j指向最右邊
    while(i != j ) { //i和j不相遇時，在循環中繼續檢索
        while(arr[j] >= base && i<j) {
            j--;//j從右往左移動
        }
        while(arr[i] <= base && i<j) {
            i++;//i從左往右移動
        }
   
        //代碼走到這，i和j都停下了，這時候交換i和j位置的元素
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //代碼走到這跳出循環，說明i和j相等了，交換相遇位置和基準數的數值
    arr[left] = arr[i];
    arr[i] = base;
    //這裡基準數左邊的數字都比它小，右邊的數字都比他大
    //排基準數的左邊
    quickSort(arr, left, i - 1);
    //排基準數的右邊
    quickSort(arr, j+1, rigth);
 }
           

6.桶排序

1.算法描述

1.将待排序的序列分到若幹個桶中，每個桶内的元素再進行個别排序。

2.時間複雜度最好可能是線性O(n)，桶排序不是基于比較的排序

2.算法分析

桶排序的算法時間複雜度有兩部分組成：

1.周遊處理每個元素，O(n)時間下周遊一遍每個元素

2.每個桶内再次排序的時間複雜度總和

如果桶内元素配置設定較為均勻假設每個桶内部使用的排序算法為快速排序，那麼每個桶内的時間複雜度為(n/m) log(n/m)。有m個桶，那麼時間複雜度為m * (n/m)log(n/m)=n (log n-log m).是以最終桶排序的時間複雜度為：O(n)+O(n(log n- log m))

=

O(n+n(log n -log m)) 其中m為桶的個數。我們有時也會寫成O(n+c),其中c=n*(log n -log m);

使用時要注意：

注意元素分布盡量均勻，桶的個數也需要經過設計。

3.代碼實作

作者：bigsai
連結：https://zhuanlan.zhihu.com/p/164992268
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

import java.util.ArrayList;
import java.util.List;
//微信公衆号：bigsai
public class test3 {
    public static void main(String[] args) {
        int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
        List[] buckets=new ArrayList[5];
        for(int i=0;i<buckets.length;i++)//初始化
        {
            buckets[i]=new ArrayList<Integer>();
        }
        for(int i=0;i<a.length;i++)//将待排序序列放入對應桶中
        {
            int index=a[i]/10;//對應的桶号
            buckets[index].add(a[i]);
        }
        for(int i=0;i<buckets.length;i++)//每個桶内進行排序(使用系統自帶快排)
        {
            buckets[i].sort(null);
            for(int j=0;j<buckets[i].size();j++)//順便列印輸出
            {
                System.out.print(buckets[i].get(j)+" ");
            }
        }   
    }
}
           

7.基數排序

1.算法描述

将所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。

基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

2.算法分析

第一步

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時将它們配置設定至編号0到9的桶子中：

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

第二步

接下來将這些桶子中的數值重新串接起來，成為以下的數列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再進行一次配置設定，這次是根據十位數來配置設定：

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

第三步

接下來将這些桶子中的數值重新串接起來，成為以下的數列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。

LSD的基數排序适用于位數小的數列，如果位數多的話，使用MSD的效率會比較好。MSD的方式與LSD相反，是由高位數為基底開始進行配置設定，但在配置設定之後并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，将每個桶子中的數值按照下一數位的值配置設定到“子桶”中。在進行完最低位數的配置設定後再合并回單一的數組中。

3.代碼實作

public void maximumGap(int[] nums) {
        int n = nums.length;
        long exp = 1;//從低位到高位
        int[] buf = new int[n];//排序後的數存在buf中
        int maxVal = Arrays.stream(nums).max().getAsInt();
        // int最大有10位數也就是十億以上，是以可能會循環10次以上
        while (maxVal >= exp) {
            int[] cnt = new int[10];//記錄每個數應該放置在buf中的位置
            for (int i = 0; i < n; i++) {// 這裡是O(n)
                int digit = (nums[i] / (int) exp) % 10;
                cnt[digit]++;
            }
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i - 1];//全部加完之後就得到位置資訊了。digit越大排的越往後
            }
            for (int i = n - 1; i >= 0; i--) {// 這裡是O(n)
                int digit = (nums[i] / (int) exp) % 10;
                buf[cnt[digit] - 1] = nums[i];//根據位置資訊放置數
                cnt[digit]--;
            }
            System.arraycopy(buf, 0, nums, 0, n);// 這裡是O(n)，數字分别是開始的位置、開始的位置和長度
            exp *= 10;
        }
    }
           

8.堆排序

1.算法描述

圖解排序算法(三)之堆排序

堆排序是利用堆這種資料結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。首先簡單了解下堆結構。

堆

　　堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆

堆排序的基本思想是：

　 将待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反複執行，便能得到一個有序序列了

2.算法分析

a.将無需序列建構成一個堆，根據升序降序需求選擇大頂堆或小頂堆;

b.将堆頂元素與末尾元素交換，将最大元素"沉"到數組末端;

c.重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與目前末尾元素，反複執行調整+交換步驟，直到整個序列有序。

3.代碼實作

public static void sort(int []arr){
        //1.建構大頂堆
        for(int i=arr.length/2-1;i>=0;i--){
            //從第一個非葉子結點從下至上，從右至左調整結構
            adjustHeap(arr,i,arr.length);
        }
        //2.調整堆結構+交換堆頂元素與末尾元素，因為要排序是以将最大的依次放在最後
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆頂元素與末尾元素進行交換
            adjustHeap(arr,0,j);//重新對堆進行調整
        }
    }

    /**
     * 調整大頂堆（僅是調整過程，建立在大頂堆已建構的基礎上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出目前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//從i結點的左子結點開始，也就是2i+1處開始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子結點小于右子結點，k指向右子結點
                k++;
            }
            if(arr[k] >temp){//如果子節點大于父節點，将子節點值賦給父節點（不用進行交換）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最終的位置
    }

    /**
     * 交換元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }