圖解簡單選擇排序

如果需要查看排版好看的請搜索微信公眾號放開我我還能學

簡單選擇排序

有如下數組，我們需要對它從小到大排序，步驟如下：

1. 在數組中找到最小值，然後與第一個位置交換。
2. 除去第一個位置在數組中繼續找最小值，與第二個位置交換，以此類推，直到末尾。

下圖展示了整個交換的過程：

選擇排序代碼：

<code>public static void sort(Comparable[] arr) {    int n = arr.length;    for (int i = 0; i < n; i++) {        // 尋找[i, n)區間裡的最小值的索引        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;}/<code>

優化

我們通過類似對撞指針的思路，維護兩個指針，這兩個指針分別指向最大值和最小值。

步驟如下：

1. 我們讓left指針指向數組的起始位置（最小值），right指針指向數組的末尾位置（最大值）。
2. 在left < right的前提下，保證left指向的元素 < right指向的元素，不滿足則交換。
3. 在每一輪循環(left+1, right)中，遍歷所有元素，如果有元素小於最小值，則更新最小值的位置；否則如果有元素大於最大值，則更新最大值的位置。
4. 一輪循環結束，讓最小值和left指向的元素交換，讓最大值和right指向的元素交換。
5. 讓left指針和right指針所構成的區間減小，即left++, right--。

下圖展示了整個交換的過程：

優化的選擇排序代碼：

<code>// 在每一輪中, 可以同時找到當前未處理元素的最大值和最小值public static void sort(Comparable[] arr) {    int left = 0, right = arr.length - 1;    while (left < right) {        int minIndex = left;        int maxIndex = right;        // 在每一輪查找時, 要保證arr[minIndex] <= arr[maxIndex]        if (arr[minIndex].compareTo(arr[maxIndex]) > 0) {            swap(arr, minIndex, maxIndex);        }        for (int i = left + 1; i < right; i++) {            if (arr[i].compareTo(arr[minIndex]) < 0) {                minIndex = i;            } else if (arr[i].compareTo(arr[maxIndex]) > 0) {                maxIndex = i;            }        }        swap(arr, left, minIndex);        swap(arr, right, maxIndex);        left++;        right--;    }}private static void swap(Object[] arr, int i, int j) {    Object t = arr[i];    arr[i] = arr[j];    arr[j] = t;}/<code>

閱讀更多 放開我我還能學 的文章

關鍵字: 圖解 swap minIndex