七種排序算法的JAVA實作

最近在找工作時很多面試官都會問到排序算法的實作，是以趁着周末有時間就來總結一下七種排序算法實作。

算法的實作我使用的是java語言，其中為了增強算法的可複用性，我使用了泛型這一特性，在排序的數組元

素都要實作Comparable接口，在排序時使用Comparable接口中的方法compareTo來對兩個元素進行比較。

### 一、冒泡排序。

在當初大一時候學習C語言，當時教的兩種排序算法冒泡排序、簡單選擇排序印象都很深刻，應該是我學過的

排序算法中最簡單的了。

冒泡排序的思想：

1.第一次排序時将序列[0 ~ n - 1]中從前往後進行兩個相鄰元素的比較，若前者較大則交換，比較n-1次;

當第一趟排序結束時，序列最大的元素就被交換到位置n-1上，就如同一個氣泡，一步一步往後翻滾，直到

最後一位。

2.重複步驟1，在第i趟時需要翻滾n-i-1次，每趟決定一個元素的位置，一共需要n-1趟。

比如，初始序列: [1, 5, 4, 3, 2]

第1趟: [1, 4, 3, 2 ] 5

第2趟: [1, 3, 2 ] 4, 5

……

public static <T extends Comparable<T>> void bubbleSort(T[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = 0; j < a.length - i - 1; j++) {
            if (a[j].compareTo(a[j + 1]) > 0) {
                T temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}
           

其實優化的冒泡排序應該有第3步，就是在一趟排序中未交換元素則說明子序列已經有序，不在進行下一趟排序；

是以冒泡排序最多執行n-1次。

比如，初始序列：[1, 2, 3, 5, 4]

隻需要一趟排序：[1, 2, 3, 4 ] 5

下面這個是我實作的優化冒泡算法，因為多了指派語句和條件判斷，是以在數組前面序列有序的情況下運作時

間會有優化，但是如果數組元素分布均勻，大小随機則反而效率會低下。

public static <T extends Comparable<T>> void bubbleSortOpt(T[] a) {
    for (int i = 0; i < a.length; i++) {
        boolean isSwap = false;
        for (int j = 0; j < a.length - i - 1; j++) {
            if (a[j].compareTo(a[j + 1]) > 0) {
                T temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                isSwap = true;
            }
        }
        i = isSwap ? i : a.length;
    }
}
           

而下面這個是在我的資料結構課本上的實作，不使用條件判斷跳出循環，解決了效率問題。經過多次測試，下面的排序

算法的運作時間确實比上面兩個要好。

public static <T extends Comparable<T>> void bubbleSortOpti(T[] a) {
    int i = a.length - 1, j, last;
    while (i > 0) {
        last = 0;
        for (j = 0; j < i; j++) {
            if (a[j].compareTo(a[j + 1]) > 0) {
                T temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                last = j;
            }
        }
        i = last;
    }
}
           

優化冒泡排序在已經有序的情況下隻需進行一趟排序，n-1次比較。是以最好情況下的時間複雜度為O(n)，無需移動元素；

最壞情況進行n-1趟排序，第i趟比較n-i次，移動元素3(n-i)次，這樣總的比較次數為(1/2)n(n-1)，移動元素次

數為3n(n-1)/2。最壞情況下時間複雜度為O(n^2)。

### 二、簡單選擇排序。

簡單選擇排序的基本思想：

1.第一趟在初始序列[0 ~ n-1]中找最小值元素，并與位置為0的元素交換位置。

2.第i趟在序列[i-1, n-1]中進行，找到最小值元素與位置為i-1的元素交換位置。

每次決定一個元素的位置，經過n-1趟後使得初始序列有序。

比如，初始序列：[1, 5, 4, 3, 2]

第1趟：1 [5, 4, 3, 2]

第2趟：1 2 [4, 3, 5]

……

public static <T extends Comparable<T>> void selectSort(T[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int k = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[k].compareTo(a[j]) > 0) {
                k = j;
            }
        }
        if (k > i) {
            T temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }
}
           

上面這種方法是标記了最小元素的位置，在一趟排序的最後交換序列首元素和序列最小元素。之前我還寫過一種，在寫

這篇部落格之前我一直以為是冒泡排序，後來才發現是選擇排序。我貼出來對比一下，這種寫法也是每次确定最小元素的

位置但是沒有标記而是在一趟排序時進行多次交換元素，這樣做影響了效率不推薦這樣做。

public static <T extends Comparable<T>> void selectSortE(T[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i].compareTo(a[j]) > 0) {
                T temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}
           

簡單選擇排序和數組序列的初始排列無關，無聊排列如何都必須要執行n-1趟。總的比較次數為n(n-1)/2，

交換元素(n-1)次，移動元素3(n-1)次。最好、最壞和平均時間複雜度都為O(n^2)。

### 三、直接插入排序

直接插入排序的基本思想：

1.向數組序列後面檢索，當檢索到後一個元素小于前一個元素時，記錄下元素。從記錄的元素位置開始往前檢索，同時元素往後移找到比

記錄下元素要小的元素的位置插入。

2.重複1的步驟，經過n-1趟排序後即成為有序序列。

比如，初始序列：[1, 5, 4, 3, 2]

第1趟：[1, (4, 5), 3, 2]

第2趟：[1, (3, 4, 5), 2]

第3趟：[1, (2, 3, 4, 5)]

public static <T extends Comparable<T>> void insertSort(T[] a) {
    for (int i = 1; i < a.length; i++) {
        int j = i;
        T temp = a[i];
        for (; j > 0 && temp.compareTo(a[j - 1]) < 0; j--) {
            a[j] = a[j - 1];
        }
        a[j] = temp;
    }
}
           

直接插叙排序在有序的情況下，總的比較次數是n-1，移動元素次數是2(n-1)，最好情況下時間複雜度就是O(n)。

最壞情況下，一趟最多比較i次，移動元素i+2次，總的比較次數為n(n-1)/2，移動元素次數(n+4)(n-1)/2。最壞情況時間複雜度為O(n^2)。

### 四、快速排序。

快速排序可以說是冒泡排序的進階版本，冒泡排序每次都隻能對相鄰的兩個數進行比較，而快速排序從兩端同時檢索保證每趟排序結束，

基準數左邊的元素都小于基準數，基準數右邊的元素都大于基準數。代碼中是選中序列第一個元素作為基準，對快排來說還有很多優化的方法，

下次有時間的時候再總結一下。

快速排序的思想：

1.先從序列後端往前檢索，找到小于基準數的元素，再從序列前端往後檢索，找到大于基準數的數交換兩個元素位置。直到從後往前和從前往後的指針相遇，

将基準數的位置和相遇位置元素交換結束一趟排序。這樣就劃分出兩個序列，一個序列的元素比基準數都要小，一個序列的元素比基準數都要大。

2.将劃分出的子序列按1的步驟繼續排序，直到子序列隻有一個元素時得到有序序列。

比如，初始序列：[1, 5, 4, 3, 6, 2]

第1趟：[1, (5, 4, 3, 6, 2)]

第2趟：[1, (2, 4, 3), 5, (6)]

第3趟：[1, 2, (4, 3), 5, 6]

第4趟：[1, 2, 3, 4, 5, 6]

public static <T extends Comparable<T>> void quickSort(T[] a) {
    quickSort(a, 0, a.length - 1);
}
public static <T extends Comparable<T>> void quickSort(T[] a, int left, int right) {
    if (left >= right) return;
    T temp = a[left];
    int i = left;
    int j = right;
    while (i < j) {
        while(a[j].compareTo(temp) >= 0 && i < j) j--;
        while(a[i].compareTo(temp) <= 0 && i < j) i++;
        if (i < j) {
            T t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    a[left] = a[j];
    a[j] = temp;
    quickSort(a, left, j - 1);
    quickSort(a, j + 1, right);
}
           

快排最壞情況是每次分割的兩個子序列中有一個為空，機初始序列有序（順序或逆序)，這是快速排序效率最低，時間複雜度為O(n^2)。

快排的平均時間複雜度為O(nlogn)。

在最壞情況下快排需要的附加堆棧存儲空間為O(n)。

### 五、堆排序。

使用資料結構堆來輔助我們排序，如果要構造非遞減序列我們采用大根堆。

大根堆是包含n個結點的完全二叉樹，該樹中每個節點的關鍵字值小于等于其雙親節點的關鍵字值。

堆排序的思想：

1.将初始序列構造成大根堆，從堆中第一個非葉子節點開始調用adjustDown方法将元素向下調整，直到堆頂。

2.第i趟排序将堆頂元素a[0]與堆底元素a[n-i]交換，然後将a[0]向下調整，直到堆中隻剩最後一個元素。

比如，初始序列：[1, 5, 4, 3, 2]

建堆後：[5, 3, 4, 1, 2]

第1趟：[4, 3, 1, 2] 5

第2趟：[3, 1, 2] 4, 5

第3趟：[1, 2] 3, 4, 5

……

public static <T extends Comparable<T>> void heapSort(T[] a) {
    for (int i = (a.length - 2) / 2; i >= 0; i--) {
        adjustDown(a, i, a.length - 1);
    }
    for (int i = a.length - 1; i >= 0; i--) {
        T temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        adjustDown(a, 0, i - 1);
    }
}
public static <T extends Comparable<T>> void adjustDown(T[] a, int r, int j) {
    T temp = a[r];
    int child = 2 * r + 1;
    while (child <= j) {
        if (child < j && a[child].compareTo(a[child + 1]) < 0) child++;
        if (temp.compareTo(a[child]) >= 0) break;
        a[(child - 1) / 2] = a[child];
        child = 2 * child + 1;
    }
    a[(child - 1) / 2] = temp;
}
           

建構堆得時間最多是O(nlogn)，在每趟排序後都要向下調整一次最多花費O(nlogn)，是以堆排序的時間複雜度為O(nlogn)。

不習慣在CSDN使用markdown，有字數限制？

可以到我的網站或簡書上看。

我的部落格

我的簡書