排序算法之——快速排序分析

引言

本篇的主題是快速排序，它可能是應用最廣泛的算法了。它的平均運作時間是，最壞情形性能為，但隻需做一點改進就可以使最壞情形很難出現。

public static void sort(List<Integer> items) {
     if (items.size() > 1) {
         List<Integer> smaller = new ArrayList<>();
         List<Integer> same = new ArrayList<>();
         List<Integer> larger = new ArrayList<>();
         Integer pivot = items.get(items.size() / 2);//取得哨兵
         for (Integer item : items) {
             if (item < pivot) {
                 smaller.add(item);
             } else if (item > pivot) {
                 larger.add(item);
             } else {
                 same.add(item);
             }
         }
         sort(smaller);//遞歸的對左半部分執行排序
         sort(larger);
         items.clear();//清空items
         //注意add的順序
         items.addAll(smaller);
         items.addAll(same);
         items.addAll(larger);
     }
 }

上面的這種算法應用了快速排序的思想，然而會産生額外的清單。隻是作為一個開胃菜，下面開始解釋快排的思想。

思路

取S中某個元素作為 pivot (哨兵)
通過 pivot 将序列分為兩個子序列其中同時
在子序列分别遞歸地排序後，原序列自然有序
傳回條件：隻剩下單個元素時，本身就是解，遞歸函數達到傳回條件

選取哨兵

本文介紹的方法是首先将待排序序列打亂，防止待排序序列是基本有序的而産生劣質的分隔，進而導緻性能偏向最壞情況()。

将序列打亂之後，選擇第一個元素作為哨兵。

分割政策

分割階段要做的是将所有小元素移到數組的左邊，把大元素移到數組的右邊。小和大是相對于哨兵元素而言的。

還有，如果i和j遇到等于哨兵元素的關鍵字，那麼我們讓i和j都停止。

小數組

對于很小的數組(

array.length <= 20

)，快速排序不如插入排序。因為快排是遞歸分解的，總會遇到小數組情況。

是以，當是小數組時，我們采用插入排序而不是快排。

上面說小于20的數組示小數組，其實5到20之内都可以。我們定義截止範圍(cutoff) 為10。

下面通過執行個體圖解來分析一下快排。為了簡單，我們隻分析第一趟分割過程，并且假設不采用優化操作(打亂數組操作以及小數組轉化為插入排序)。

原始數組如上。

我們選擇第一個元素6作為哨兵節點，同時定義兩個指針

和

，

指向0，

指向數組最後一個元素再下一個元素(為了友善

--j

操作)。

接下來就開始我們的分割過程，

從右邊往左開始掃描，直到掃描到小于或等于哨兵節點的元素(分割政策：等于的哨兵的元素也停止)。

當

停止後，我們讓

從左往右掃描，直到遇到大于或等于哨兵節點的元素

此時

也停止了，這時需要判斷

是否在

前面(

i<j

)。若滿足，則交換

和

的位置，

再從

的位置開始向左掃描。

重複上述過程，直到

指向9,

指向5。然後交換它們的位置。

繼續

往前移1步，就遇到了元素4，停了下來。轉到

向右走，直到元素9，停了下來。注意，此時

i>j

，并且

指向的是大于哨兵元素的節點。

是以，我們隻需要将

指向的元素和哨兵元素互換位置

這樣，哨兵左邊的元素都不大于它，哨兵右邊的元素都不小于它。

接下來，我們隻需要對左邊的子數組以及右邊的子數組進行同樣的過程，直到隻剩下單個元素時，遞歸傳回(未優化)。

代碼

交換數組元素代碼：

private static <E> void swap(E[] array, int i, int j) {
    if (i == j) return;
    E tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

洗牌打亂數組代碼：

/**
 * 打亂數組a中的元素
 * <p>
 * 從0到i之間生成一個随機數，然後交換i與這個随機數的位置
 * @param a
 */
private static void shuffle(Object[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int r = uniform(i + 1);//從0到i之間生成一個随機數，然後交換i與這個随機數的位置
        swap(a, i, r);
    }
}

/**
 * 傳回[0,n)之間的整數
 *
 * @param n
 * @return
 */
private static int uniform(int n) {
    return (int) (Math.random() * n);
}

經典版本

public static <E extends Comparable<? super E>> void quickSort(E[] a) {
     shuffle(a);//洗牌
     quickSort(a, 0, a.length - 1);//注意傳入的是a.length - 1
}

/**
 * @param a
 * @param left
 * @param right 指向待排序子數組末端元素
 * @param <E>
 */
private static <E extends Comparable<? super E>> void quickSort(E[] a, int left, int right) {
    if (left < right) {//條件不能是 left <= right

        int i = left, j = right + 1;//左邊第一個元素作為哨兵節點:a[left]  j為right + 1是為了--j的寫法
        while (true) {
            /**
             * 此算法先從左往右還是從右往左都沒關系!
             */
            //從右邊往左開始掃描，直到掃描到小于或等于哨兵節點的元素
            while (a[--j].compareTo(a[left]) > 0) {
                /*if (j == left) { //該端點檢查是多餘的，因為哨兵在左端，當j指向哨兵時不會大于哨兵自己，循環也就跳出了
                    break;
                }*/
            }
            // 從左往右掃描，直到遇到大于或等于哨兵節點的元素 若條件是left <= right a[++i]會報索引越界異常
            while (a[++i].compareTo(a[left]) < 0) {
                if (i == right) {//端點檢查
                    break;
                }
            }

            if (i < j) {
                //交換元素，繼續掃描
                swap(a, i, j);
            } else {
                //i、j交錯則退出最外層的while循環
                break;
            }
        }
        //哨兵節點放入此位置即可 此時a[j]左邊的元素都比它要小，右邊的要大
        //該算法以下隻能用j而不是i ,因為i最後會掃描到比哨兵大的元素而停止，不能用比哨兵大的元素和left交換位置，而j是比哨兵小的元素
        //System.out.println("a[j=" + j + "] = " + a[j] + ",a[i=" + i + "]=" + a[i]);
        swap(a, j, left);
        //j元素已經就位了
        quickSort(a, left, j - 1);
        quickSort(a, j + 1, right);
    }
}

優化版本

主要是針對小數組采用直接插入排序：

private static <E extends Comparable<? super E>> void insertionSort(E[] a, int left, int right) {
    int j;
    for (int i = left + 1; i <= right; i++) { //注意i的初始值以及i的判斷條件
        E tmp = a[i];//對于位置i，先把i位置對應的值儲存起來，然後把i挖空
        for (j = i; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
            a[j] = a[j - 1];//若發現i對應的值小于某個位置的值，則将該位置的值往後移動一位；
        }
        a[j] = tmp;//最後将tmp填入空位
    }
}

關于插入排序可以看部落格插入排序分析

/**
 * 對于很小的數組(比如元素個數小于10)，快速排序不如插入排序
 */
private static final int CUTOFF = 10;

/**
 * @param a
 * @param left
 * @param right 指向帶排序子數組末端元素
 * @param <E>
 */
private static <E extends Comparable<? super E>> void quickSort(E[] a, int left, int right) {
    if (left + CUTOFF <= right) {//判斷是否為小數組

        int i = left, j = right + 1;//左邊第一個元素作為哨兵節點:a[left] j為right + 1是為了--j的寫法
        while (true) {
            /**
             * 此算法先從左往右還是從右往左都沒關系!
             */
            //從右邊往左開始掃描，直到掃描到小于或等于哨兵節點的元素
            while (a[--j].compareTo(a[left]) > 0) {
                /*if (j == left) { //該端點檢查是多餘的，因為哨兵在左端，當j指向哨兵時不會大于哨兵自己，循環也就跳出了
                    break;
                }*/
            }
            // 從左往右掃描，直到遇到大于或等于哨兵節點的元素
            while (a[++i].compareTo(a[left]) < 0) {
                if (i == right) {//端點檢查
                    break;
                }
            }

            if (i < j) {
                swap(a, i, j);
            } else {
                break;
            }
        }
        //哨兵節點放入此位置即可 此時a[j]左邊的元素都比它要小，右邊的要大
        //該算法以下隻能用j而不是i ,因為i最後會掃描到比哨兵大的元素而停止，不能用比哨兵大的元素和left交換位置，而j是比哨兵小的元素
        System.out.println("a[j=" + j + "] = " + a[j] + ",a[i=" + i + "]=" + a[i]);
        swap(a, j, left);
        quickSort(a, left, j - 1);
        quickSort(a, j + 1, right);
    } else {
        //小數組直接用插入排序
        insertionSort(a, left, right);
    }
}

測試代碼

檢查有序性代碼

private static <E extends Comparable<? super E>> void checkSorted(E[] a) {
    if (a.length == 1) return;

    for (int i = 0; i <= a.length - 2; i++) {
        if (a[i].compareTo(a[i + 1]) > 0) {
            System.out.println("a[" + i + "]=" + a[i] + " larger than a[" + (i + 1) + "]=" + a[i + 1]);
            throw new IllegalStateException("Not ordered.");
        }
    }
}

對随機數組進行排序：

private static void sortRandArray() {
    Random rand = new Random();
    Integer[] array = rand.ints(1000, 1, 300000).boxed()
            .collect(Collectors.toList()).toArray(new Integer[]{});
    System.out.println(Arrays.toString(array));
    quickSort(array);
    System.out.println(Arrays.toString(array));
    checkSorted(array);
}

對有序數組進行排序：

private static void sortFixedArray() {
    Integer[] array = IntStream
                        .range(1,100)
                        .boxed()
                        //.sorted(Collections.reverseOrder())  //解除掉這個注釋就是逆序數組
                        .toArray(Integer[]::new);
    System.out.println(Arrays.toString(array));
    quickSort(array);
    checkSorted(array);
    System.out.println(Arrays.toString(array));
}

測試：

public static void main(String[] args) {
    sortFixedArray();//同時測試了順序數組和逆序數組
    for (int i = 0; i < 10; i++) {
        sortRandArray();
    }
}

經過測試，快排代碼沒有問題。請放心使用，若有問題，請留言指出。

選擇問題

思路

首先得到哨兵節點的索引 j
如果 j > k 說明一定在小于哨兵節點的左邊子數組中，是以急需在左邊查找
否則如果 j < k 則在右邊查找
否則 j == k 則直接傳回

代碼

/**
 * 找到第k小的元素
 * @param a
 * @param k 從0開始 0表示第1小的元素，1表示第2小的元素
 * @param <E>
 * @return
 */
public static <E extends Comparable<? super E>> E quickSelect(E[] a, int k) {
    if (k < 0 || k > a.length - 1) {
        throw new IllegalStateException("invalid k");
    }
    shuffle(a);
    int left = 0, right = a.length - 1;
    while (left < right) {
        int j = partition(a, left, right);//左邊的比a[j]小，右邊的比a[j]大
        if (j > k) {
            right = j - 1;//在左邊找
        } else if (j < k) {
            left = j + 1;//在右邊找
        } else {
            //j == k
            return a[k];
        }
    }
    //當left == right == k時
    return a[k];
}

/**
 * 抽取擷取哨兵節點過程
 *
 * @param a
 * @param left
 * @param right
 * @return 哨兵節點的位置
 */
private static <E extends Comparable<? super E>> int partition(E[] a, int left, int right) {
    int i = left, j = right + 1;//左邊第一個元素作為哨兵節點:a[left] j為right + 1是為了--j的寫法
    E pivot = a[left];
    while (true) {
        while (a[--j].compareTo(pivot) > 0) {
        }
        // 從左往右掃描，直到遇到大于或等于哨兵節點的元素 若條件是left <= right a[++i]會報索引越界異常
        while (a[++i].compareTo(pivot) < 0) {
            if (i == right) {//端點檢查
                break;
            }
        }

        if (i < j) {
            swap(a, i, j);
        } else {
            break;
        }
    }
    swap(a, j, left);
    return j;
}

排序算法之——快速排序分析

引言

思路

選取哨兵

分割政策

小數組

代碼

經典版本

優化版本

測試代碼

選擇問題

思路

代碼

繼續閱讀

選擇 React 是商業問題而不是技術問題

算法複習筆記（四）減治法

還是有網友問我有關于iPhoen14系列的選擇問題，我這裡再與大家簡單地聊一聊。[黑線]首先，考慮iPhone14基礎版

20系槍族，我的幾句閑言碎語！20系列總體來說還是跟随政策下的拿來主義，貌似設計理念跟上了國際潮流，實際上還是稍有落後，

電動機的選擇（1）電動機容量的選擇要為某一台生産機械選配電動機，首先需要考慮電動機的容量。如果電動機的容量選大了，雖然能

這也太酷了吧‼️這才是實體的正确打開方式✨😤這個人真是有800個心眼子，服了服了🤺文案也就圖一樂，主要的還是高中實體啦🍭

DNF：龍7、異常5、全15，15%出血，如何選擇？一位粉絲私信，“喜獲2塊恩特左槽，遇到了選擇問題，龍7、異常5、全1

無線區域網路接入選擇關鍵技術研究無線區域網路（WLAN）具有速度快、成本低和接入靈活等特點，目前已得到廣泛的應用。在許多人員

從張雪峰被攻擊談談專業選擇問題

python快速排序過程圖解，形象描述快速排序過程快速排序過程圖解