CrabSaberV is here
0%

快速排序

发表于 更新于 分类于

排序算法——快速排序

这些比较基础的知识要时常回顾一下。

思想

快速排序是冒泡排序的一个改进算法，采用了分治的思想。

其主要思想是将序列进行分割成左右两个部分，左侧数全部小于右侧数，接着不断对每个序列进行同样的分割处理，最终使得整个序列有序。

实现思路：

  1. 一般从序列左边第一个元素作为基准数取出来。
  2. 维护左和右两个指针，由于基准数是左指针下的数被取出来，所以先是右指针向左移动遍历。
  3. 右侧指针向左移动，当指针所指的数小于基准数，则可以认为右侧指针下的数应该前往左侧，而基准数base应该属于右指针的位置。所以将右指针的数填给左指针的位置。
  4. 接着左指针开始向右侧移动，同理当左指针数大于基准数时，将左指针的数填给右指针的位置，后续又从右指针位置继续向左移动。
  5. 重复一样行为，直到左右两个指针相遇，则该位置就是基准数的最终位置。此时该位置的左侧都是小于base的数，右侧都是大于base的数。
  6. 接着以base分割两个序列。对两个序列进行同样处理。
  7. 最终情况是数组不能在被分割，此时整个序列就已经有序了。

这其中从一个序列分割出两个序列的过程就是一次快速排序操作。

代码

前提：
确保数组不为空，QuickSort()将是快速排序算法的方法

1
2
3
4
public int[] SortArray(int[] nums) {
    QuickSort(nums,0,nums.Length-1);
    return nums;
}

递归方案

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
    
// 快速排序
private void QuickSort(int[] nums,int start,int end){
    if(start >= end){
        return;
    }
    int mid = DoSort(nums,start,end);
    // 分治
    QuickSort(nums,start,mid-1); // 左侧
    QuickSort(nums,mid + 1,end); // 右侧
}

// 一次排序，返回得到基准数的最终位置（指针相遇位置）
private int DoSort(int[] nums,int left,int right){
    int b = nums[left]; // 基准数
    while(left < right){
        while(left < right && nums[right] >= b){
            right--;
        }
        nums[left] = nums[right];
        // 左
        while(left < right && nums[left] <= b ){
            left++;
        }
        nums[right] = nums[left];
    }

    // 基准数的最终归宿位置
    nums[left] = b; 

    return left;
}

迭代方案

递归的写法很简单，而且也容易理解。不过记住一个重点往往递归都能通过栈结构来实现迭代。因为递归的本质就是栈的逻辑。栈结构要记录的是每次递归会改变的数据。

迭代方法相比迭代不会因为数据过大导致方法栈溢出（递归会保留上一个递归的数据参数）。但是需要分配堆内存来管理数据。

由于DoSort()方法是通用的，所以下面代码就不写了，只写QuickSort()方法。

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
private void QuickSort(int[] nums,int start,int end){

    // 非递归可以通过栈来存储边界下标
    Stack<int> stack = new Stack<int>();

    // 入栈顺序是先左后右，那么出栈时要注意，先出栈的是右。
    stack.Push(start);
    stack.Push(end);

    while(stack.Count > 0){
        // 出栈先出的右
        int r = stack.Pop();
        int l = stack.Pop();

        int mid = DoSort(nums,l,r);
        // 控制栈输入，如果边界和mid相遇，则表示不能再分治了
        if(l < mid - 1){
            stack.Push(l);
            stack.Push(mid-1);
        }
        if(r > mid + 1 ){
            stack.Push(mid+1);
            stack.Push(r);
        }
            
    }
}

稳定性

这里稳定性说的是数据中重复元素的相对位置。因为快速排序是跳跃式排序，可能会使得重复元素的相对顺序发生改变。

假如排序的不是单纯的数，而是某个数据结构，排序依据是某个id，那么可能最终顺序后的重复元素间的顺序不是排序前的顺序了。

复杂度分析

快速排序的平均时间复杂度是O(nlogn)。

极端情况比如数据本身就是有序的，那么复杂对会变为O(n²)，可以想象每此判断后都是每次都是少一个数的比较，那么次数就是 $$ \sum_{n-1}^{i=1}n-i = n-1+n-2+….+1 = \frac{n(n-1)}{2}$$ 结果就是O(n^2)。

空间复杂度

基本是递归造成的栈空间使用，最好情况树的深度为 log2n
空间复杂度为：O(logn)