算法时空 算法

算法时空第17-18讲 快速排序

快速排序

Posted by Twany on July 28, 2019
快速排序，利用了分治法的思想，是一种就地算法。

最坏复杂度为 o(n^2)，期望情况下为 o(nlogn)，取决于枢纽元的选择

思路——指针交换法

我们以一次快速排序为例 其中，n就是我们选取的枢纽元，n左侧的数小于等于n，右侧的大于n。这样我们再递归排序左右两侧元素即可。

难点：

  • 枢纽元的确立，如果我们选取边界的话，可能会遇到以下情况： 此时就会产生最坏复杂度。极其不利
  • 左右元素的确立，我们必须要保证左边的元素小于等于n，右侧的大于n。那么该怎么做呢？

划分方法

以一次排序为例：

  1. 我们选取左侧元素为枢纽元
  2. 设立两个指针，分别指向最左侧和最右侧元素
  3. 首先把最右侧指针对应元素和枢纽元对比，若大于，指针右移；小于则停止移动，移动权交由左侧指针
  4. 左侧指针进行比较，若小于枢纽元，指针右移；若大于，指针停止移动
  5. 此时，左右指针均已停止移动，交换两指针对应元素。指针继续移动
  6. 直至左右指针重合
  7. 交换枢纽元和重合元素

至此，一次排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    //划分方法
    private static int partition(int[] arr, int leftIndex, int rightIndex) {
        //枢纽点
        int pivot = arr[leftIndex];
        int left = leftIndex; //为什么不能是 leftIndex+1 ？
        int right = rightIndex;

        while(left != right){
            //判断右侧部分    ②
            while(left<right && pivot < arr[right]){
                right--;
            }
            //判断左侧部分    ①
            while (left<right && arr[left] <= pivot){  //短路表达式
                left++;
            }


            if( left > right){
                break;
            }

            //此时，①和②都已经停止循环，这说明它们均遇到了不满足条件的数值，所以我们需要进行交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        //枢纽值和重合点交换
        int temp = arr[left];
        arr[left] = arr[leftIndex];
        arr[leftIndex] = temp;

        //left即为left和right的重合点
        return left;
    }

上述代码有两点极其需要注意的地方：

  • 最开始的枢纽点、左右端点的赋值。最开始，我是图省事值赋值给pivot，结果一直出错，应该是引用问题。
  • 判断左右部分，为什么要先判断右侧部分呢？（尚未解决）

总代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public static void  main(String[] args) {
    int[] arr = {4,9,5,8,6,9,2,11,6,32,49,21,7};

    quickSort(arr, 0, arr.length-1);

    System.out.println(Arrays.toString(arr)); //输出 [2, 4, 5, 6, 6, 7, 8, 9, 9, 11, 21, 32, 49]
}

private static void quickSort(int[] arr, int left, int right){

    //当要排序的数组长度小于等于1时，返回
    if(left >= right){
        return;
    }
    //获得枢纽元
    int pivot = partition(arr, left, right);

    //根据枢纽元对左右两侧排序
    quickSort(arr, left, pivot-1);  //注意此处索引 -1 ，因为枢纽元位置已确定
    quickSort(arr, pivot+1, right);
}

//划分方法
private static int partition(int[] arr, int leftIndex, int rightIndex) {
    //枢纽点
    int pivot = arr[leftIndex];
    int left = leftIndex;
    int right = rightIndex;

    while(left != right){
        while(left<right && pivot < arr[right]){
            right--;
        }
        while (left<right && arr[left] <= pivot){  //短路表达式
            left++;
        }

        if( left > right){
            break;
        }

        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
    int temp = arr[left];
    arr[left] = arr[leftIndex];
    arr[leftIndex] = temp;

    return left;
}

思路——挖坑法

挖坑法比较简单，不易出错

详细可参考：漫画：什么是快速排序？

CATALOG