快速排序

什么是快速排序

快速排序是一种基于分治思想的排序算法，它的基本思想是：（以升序为例）

• 从当前区间的数组中取出一个数作为基准数。（一般选取首部元素）
• 将当前区间内将大于基准数的数全放到它的右边，小于它的数全放到它的左边。
• 再对左右区间重复上一步的操作，直到各区间只有一个数。 （分治思想的体现）

算法演示

首先给出一个待排序的数组\(arr\)

0	1	2	3	4	5	6
10	1	12	3	7	13	0

先确定一个基准值，一般选取首部元素，这里将10作为基准值，即 \(base = 10\)

设置两个指针，\(left\)和\(right\)，\(left\)用于从左往右寻找大于基准值的元素，\(right\)用于从右往左寻找小于基准值的元素

那么由于选取了首部元素，所以先从右往左寻找比基准值小的元素，所以\(right\)指向\(arr[6] = 0\)，接着从左往右寻找大于基准值的元素，\(left\)指向\(arr[2] = 12\)

将\(right\)和\(left\)指向的元素交换，交换后的数组\(arr\)

0	1	2	3	4	5	6
10	1	0	3	7	13	12

\(right\)接着继续从右往左寻找比基准值小的元素，\(right\)指向\(arr[4] = 7\)，\(left\)继续从左往右寻找大于基准值的元素，\(left\)最终和\(right\)相等，俗称“碰头”，此时停止\(left\)继续寻找，把基准值和\(arr[4]\)交换，交换后的数组\(arr\)

0	1	2	3	4	5	6
7	1	0	3	10	13	12

此时，\(left\)和\(right\)都指向\(arr[4] = 10\)，对于\(arr[4]\)左边的元素，都比\(arr[4]\)要小，对于\(arr[4]\)右边的元素，都比\(arr[5]\)要大

此时将数组分为两部分，即

0	1	2	3
7	1	0	3

和

5	6
13	12

对这两部分再进行相同的处理，也就是进行递归，最终当数组只有一个元素时，此时自然是有序的，就结束掉递归

代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std ;
// 打印函数
void Print(int arr[], int n) {
    for (int i = 0;i < n;i++) {
        cout << arr[i] << " " ;
    }
    cout << endl ;
}
void QuickSort(int arr[], int L, int R) {
    // [L, R] 表示的区间内只有一个元素，此时自然不用再排序，当前区间内的元素就是有序的
    if (L >= R) return ;
    // 选取首部元素为基准值
    int base = arr[L] ;
    // left指针指向首部元素，right指向尾部元素
    int left = L ;
    int right = R ;
    while (left != right) {
        // right指针从右往左寻找比基准值小的值
        while (left < right && arr[right] >= base) {
            right -- ;
        }
        // left指针从左往右寻找比基准值大的值
        while (left < right && arr[left] <= base) {
            left ++ ;
        }
        // 将两个指针指向的元素交换
        if (left < right) swap(arr[left], arr[right]) ;
    }
    // left与right“碰头”以后，将指向的元素与基准值交换
    arr[L] = arr[left] ;
    arr[left] = base ;
    QuickSort(arr, L, left - 1) ;
    QuickSort(arr, left + 1, R) ;
}
/*
    这里是另一种实现方式，本质是一样的
    只是把交换操作替换成赋值
*/
void QuickSortOther(int arr[], int L, int R) {
    if (L >= R) return ;
    int base = arr[L] ;
    int left = L ;
    int right = R ;
    while (left < right) {
        while (left < right && arr[right] >= base) {
            right -- ;
        }
        if (left < right) {
            arr[left] = arr[right] ;
        }
        while (left < right && arr[left] <= base) {
            left ++ ;
        }
        if (left < right) {
            arr[right] = arr[left] ;
        }
    }
    arr[left] = base ;
    QuickSortOther(arr, L, left - 1) ;
    QuickSortOther(arr, left + 1, R) ;
}

int main(int argc, char const *argv[]) {
    int n ;
    cin >> n ;
    int* arr = new int[n] ;
    for (int i = 0;i < n;i++) {
        cin >> arr[i] ;
    }
    QuickSort(arr, 0, n - 1) ;
    Print(arr, n) ;
    delete[] arr ;
    return 0;
}

时间复杂度

最好情况是：每次交换处理后正好形成两个相等长度的左右区间

此时的时间复杂度：

\[T(n)=\left\{\begin{matrix} O(1) & n=1\\ 2T(n/2) + O(n)& n > 1 \end{matrix}\right. \]

时间复杂度为\(O(nlogn)\)

最坏情况是：原数组本身就是有序数组，假设当前区间长度为\(n\)，那么此次交换处理后只生成一个区间，且区间长度为\(n - 1\)

此时的时间复杂度：

\[T(n)=\left\{\begin{matrix} O(1) & n=1\\ T(n - 1) + O(n)& n > 1 \end{matrix}\right. \]

时间复杂度为\(O(n^2)\)

平均时间复杂度为\(O(nlogn)\)