數據結構 8 基礎排序演算法詳解、快速排序的實現、了解分治法

快速排序

快速排序與冒泡排序一樣，同樣是屬於交換排序 叫做快速排序也是有原因的。因為它採用了分治法的概念

image.png

其中最重要的一個概念就是 基準元素

冒泡排序每一輪將一個最大的元素挑選出並移動到右側。

分治法思想

在每一輪當中。通過確定基準元素，將元素分為兩部分，分別大於小於基準元素。而後的一輪中。還是通過原來的方式，在這兩輪中繼續找尋基準元素，直至不可再細分為止。

image.png

最重要的兩個地方：

基準元素的選擇 pivot

基準元素的確認一般是選擇當前數列的第一個元素,但這種方法確實不太靠譜，一般情況會通過隨機選擇的方式選擇一個基準元素。這樣一來，也能避免某些特殊數列 導致的時間複雜O(N^2);

通過隨機選擇的方式，可以將時間複雜度調整至O(Nlogn);

元素的移動

通過隨機的方式選擇元素後，接下來就是元素的移動

移動就是將元素分別移動到基準元素兩側，左側比基準元素小，右邊則比基準元素大。

這裡有兩種元素的移動方式：

  1. 挖坑法
  2. 指針交換法

挖坑法

擬定一個無序數列｛4,7,6,5,3,2,9,1｝要求將這個數列從小到大依次排列，我們採用挖坑法進行實現。

image.png

挖坑法最重要的地點在於：指定左右指針（left,right）基準元素下標index。基準元素Pivot.

假設我們通過隨機法選擇基準元素Pivot = 4 它的下標index=1表示一個坑,並且選擇了左右的指針left/right。

image.png

1、從右邊指針right開始 和基準元素進行比較。若右指針元素大於基準元素，則指針向下移動一位。若小於則將這個元素填入坑裡面。將坑的位置記錄下來。

此時我們的右邊指針元素1<4 則將右邊指針元素1 填入首位的坑index
裡面。這個時候因為1已經跑到首位去了。所以當前的位置就又成為了一個新的坑，接下來要操作左邊指針left 將左邊指針移動一位。如下圖所示

image.png

2、開始操作左指針left

通過比較7>4 則移動元素，將7移動到坑裡面。移動完後，原位置又變成一個新的坑。下面需要操作右邊指針，將右邊指針移動一位。如下圖所示

image.png

3、按照這樣的思路。再次進行操作右邊邊指針。

通過比較9>4 則右邊的元素已經大於基準元素。則無需移動位置。將右邊指針移動一位即可。繼續進行比較。如下圖所示

image.png

當前右邊指針2<4 則將2填入到坑裡面。原位置變成一個坑。左邊指針移動一位，交換指針。如下圖所示

image.png

4、繼續操作左邊指針。

元素6>4 將元素6移動坑的位置。6位置再次成為一個坑，右邊指針移動一位。如下圖所示

image.png

元素3<4 則將3元素移動到坑的位置。原位置變成坑，左邊指針移動一位。如下圖所示

image.png

開始操作左邊指針 5>4 將5元素移動到坑的位置。右邊指針移動一位。發生指針重合。如下圖所示

image.png

將基準元素移動到重合位置。交換結束。如下圖所示

image.png

交換總結

  1. 左右指針發生元素填坑後才進行交換指針操作（從左指針交換到右指針）
  2. 左邊指針的元素值大於基準元素則填坑。否則只做移動。
  3. 右邊指針的元素值小於基準元素則填坑。否則只做移動。
  4. 發生填坑後，將另一個指針位置移動一位。
  5. 指針重合則結束，將基準元素填充到重合位置。

程式碼示例

public static void main(String[] args) {

        int[] array = {4, 7, 6, 5, 3, 2, 9, 1};

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

        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array, int start, int end) {

        if (start >= end) {
            return;
        }
	
        int pivotIndex = partition(array, start, end);
	//通過分治法將數列分成兩份，各自再次遞歸
        sort(array, start, pivotIndex - 1);
        sort(array, pivotIndex + 1, end);
    }

    /**
     * @return int
     * @Author MRC
     * @Description 採用分治法 返回基準元素位置
     * @Date 17:52 2020/5/25
     * @Param [arr 被操作的數組, start 分治法起始位置, end 結束位置]
     **/
    private static int partition(int[] arr, int start, int end) {

        //取首位為基準元素。//也是坑的位置
        int pivotIndex = start;
        //基準元素的值
        int pivot = arr[pivotIndex];
        //左邊指針
        int left = start;
        //右邊指針
        int right = end;

        /**
         * 大循環用於判斷總體循環
         * 在左右指針指向同位置後
         * 結束循環
         */
        while (right >= left) {
            /**
             * 右指針
             */
            while (right >= left) {

                if (arr[right] < pivot) {
                    arr[pivotIndex] = arr[right];
                    pivotIndex = right;
                    left++;
                    break;
                }
                right--;
            }
            /**
             * 左指針
             */
            while (right >= left) {

                if (arr[left] > pivot) {
                    arr[pivotIndex] = arr[left];
                    pivotIndex = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[pivotIndex] = pivot;
        return pivotIndex;
    }

指針交換法

指針交換法相比於挖坑法，開局還是和挖坑法一樣，元素的交換次數更少，效率相比於挖坑法有小幅度的提升。我們來了解一下指針交換法的邏輯。

拿到一個數列 {4, 7, 6, 5, 3, 2, 9, 1}
我們定義左指針left 右指針right 以及首位取出的基準元素pivot=4

image.png

交換要點

  1. 從右指針開始循環
  2. 右指針指向的元素大於等於基準元素，則右指針向左移動一位。小於則指針停下。換到左邊指針操作。
  3. 左指著指向的元素小於等於基準元素，則左指針向右移動一位。大於則指針停下、跳出循環。
  4. 左指針停下後開始交換兩個指針位置的元素。開始下次循環。
  5. 指針重合大循環結束。重合位置和基準元素進行交換。

詳細解說

1、第一次循環

右指針指向元素1小於4 則右邊指針不移動 交換到左邊指針，左邊指針指向的元素4小於等於4（基準元素） 將左邊指針移動一位。
當前指針指向元素7>4 指針停下。

image.png

指針停下、開始交換元素。將左右指針位置的元素進行交換

image.png

2、第二次循環

重新到右指針，當前7>4 左移一位。
到達9當前9>4 左移一位。
到達2 當前2<4 右邊指針停下。

image.png

左指針，當前1<4 右移一位。
到達6當前6>4 左邊指針停下。

image.png

交換兩個位置的元素

image.png

3、第三次循環

右邊指針移動到3停下
左邊指針移動到5停下

image.png

開始交換元素。

image.png

4、第四次循環

移動右指針，已經發生指針的重合，則將重合的位置的元素和基準元素進行交換。

image.png

程式碼示例

public static void main(String[] args) {
        int[] array = {4, 7, 6, 5, 3, 2, 9, 1};
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    private static void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(array, start, end);
        sort(array, start, pivotIndex - 1);
        sort(array, pivotIndex + 1, end);
    }

    private static int partition(int[] array, int start, int end) {

        //取首位為基準元素。//也是坑的位置
        int pivotIndex = start;
        //基準元素的值
        int pivot = array[pivotIndex];
        //左邊指針
        int left = start;
        //右邊指針
        int right = end;

        while (right != left) {
            /**
             * 操作右指針
             */
            while (right > left && pivot < array[right]) {
                right--;
            }
            /**
             * 操作左指針
             */
            while (right > left && pivot >= array[left]) {
                left++;
            }
            /**
             * 交換元素
             */
            if (right > left) {
                int item = array[right];
                array[right] = array[left];
                array[left] = item;
            }
        }

        /**
         * 交換指針位置和基準元素
         */
        array[pivotIndex] = array[left];
        array[left] = pivot;
        return left;
    }

小結

通過本節，我們研究了快速排序的兩種實現方式。我們通過遞歸的方式實現分治法。通過挖坑交換元素和指針交換的方式分別實現快速排序。快速排序還是一個很重要的排序方法。通過本節的學習。應該了解到分治法這個重要的思想

程式碼示例

//gitee.com/mrc1999/Data-structure.git

Tags:

VirMach 便宜 VPS

QNews

QNews