数据结构与算法之美-快速排序

QuickSort - 快速排序

核心：快速排序是采用分治思想的典型应用。

• 基本思想：

1. 从要排序数组中下标从 p 到 r 之间的一组数据，任意一个数据作为 pivot（分区点/基准值）。
2. 将所有比基准值小的排在基准前面，所有比基准值大的排在基准的后面；在这个分区退出之后，该基准就处于数列的中间位置。
3. 递归地把“基准值前面的子数列”和“基准值后面的子数列”进行排序。

分区点

• 先写出快速排序的递推公式：

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

终止条件：
p >= r

• 我们将递推公式转化为递归代码。写出伪代码，你可以翻译成你熟悉的任何语言。

// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

时间复杂度

• 最优时间复杂度：
• 最坏时间复杂度：
• 稳定性：不稳定

1. Python代码实现

class Solution(object):

    def quickSort(self, numbers, l, r):
        if l >= r:
            return
        
        pivot = numbers[r]
        left, right = l, r - 1

        while left <= right:
            while left <= right and numbers[left] < pivot:
                left += 1
            while left <= right and numbers[right] >= pivot:
                right -= 1
            if left > right:
                break
            # swap numbers[left] with numbers[right] while left <= right
            numbers[left], numbers[right] = numbers[right], numbers[left]

        # swap the smaller with pivot
        numbers[left], numbers[r] = numbers[r], numbers[left]

        self.quickSort(numbers, l, left - 1)
        self.quickSort(numbers, left + 1, r)

if __name__ == "__main__":
    numbers = [1, 2, 3, 2, 2, 2, 5, 4, 2]
    solution = Solution()
    solution.quickSort(numbers, 0, len(numbers) - 1)
    print("快速排序：", numbers)

# 结果
快速排序： [1, 2, 2, 2, 2, 2, 3, 4, 5]

2. Java代码实现

import java.util.Arrays;

public class QuickSort {

    // 基于快排的思想
    public static void quickSort(int[] numbers, int l, int r) {
        // 递归终止条件
        if(l >= r) {
            return;
        }
        int pivot = numbers[r];
        int left = l;
        int right = r - 1;
        while(left <= right) {
            while(left <= right && numbers[left] < pivot) {
                left++;
            }
            while(left <= right && numbers[right] >= pivot) {
                right--;
            }
            if(left > right) {
                break;
            }
            // swap numbers[left] with numbers[right] while left <= right
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }
        // swap the smaller with pivot
        numbers[r] = numbers[left];
        numbers[left] = pivot;

        quickSort(numbers, l, left - 1);
        quickSort(numbers, left + 1, r);
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        quickSort(numbers, 0, numbers.length - 1);
        System.out.println("快速排序：" + Arrays.toString(numbers));
    }

}

// 结果
快速排序：[1, 2, 2, 2, 2, 2, 3, 4, 5]

3. C++代码实现

#include <iostream>

class Solution
{
public:

    // 基于快排的思想
    void quickSort(int* numbers, int l, int r) {
        // 递归终止条件
        if(l >= r) {
            return;
        }
        int pivot = numbers[r];
        int left = l;
        int right = r - 1;
        while(left <= right) {
            while(left <= right && numbers[left] < pivot) {
                left++;
            }
            while(left <= right && numbers[right] >= pivot) {
                right--;
            }
            if(left > right) {
                break;
            }
            // swap numbers[left] with numbers[right] while left <= right
            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }
        // swap the smaller with pivot
        numbers[r] = numbers[left];
        numbers[left] = pivot;

        
        quickSort(numbers, l, left - 1);
        quickSort(numbers, left + 1, r);

    }

};

// 数组打印模板
template<typename T>
void PrintArray(const T input_array[], const unsigned int array_size) {
    for(int i = 0; i < array_size; i++) {
        std::cout << input_array[i];
        if(i < array_size - 1){
            std::cout << ' ';
        }
    }
    std::cout << std::endl;
}

int main() {
    int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    Solution solution;
    solution.quickSort(numbers, 0, 8);
    std::cout << "快速排序：";
    PrintArray(numbers, 9);
    return 0;
}

// 结果
快速排序：1 2 2 2 2 2 3 4 5

4. Go代码实现

package main

import "fmt"

func quickSort(numbers []int, l int, r int) {
    // 递归终止条件
    if l >= r {
        return
    }
    // 分区值
    pivot := numbers[r]
    left := l
    right := r - 1

    for left <= right {
        for left <= right && numbers[left] < pivot {
            left++
        }
        for left <= right && numbers[right] >= pivot {
            right--
        }
        if left > right {
            break
        }
        numbers[left], numbers[right] = numbers[right], numbers[left]
    }

    numbers[left], numbers[r] = numbers[r], numbers[left]
    quickSort(numbers, l, left - 1)
    quickSort(numbers, left + 1, r)
}

func main() {
    numbers := []int{1, 2, 3, 2, 2, 2, 5, 4, 2}
    quickSort(numbers, 0, 8)
    fmt.Println("快速排序：", numbers)
}

// 结果
快速排序： [1 2 2 2 2 2 3 4 5]

参考文献

1. 《数据结构与算法之美》