快速排序

算法思想和步骤

快速排序算法是一种基于交换的高效的排序算法，它采用了分治法的思想：

1、从数列中取出一个数作为基准数（一般把第一个数作为基准数）。 

2、将数组进行划分(partition)，将比基准数大的元素都移至枢轴右边，将小于等于基准数的元素都移至枢轴左边。

3、再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素。

时间复杂度

快速排序的时间复杂度在最坏情况下是O(N²)，平均的时间复杂度是O(N*lgN)。

这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。

因此，快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

空间复杂度

快速排序直接在原数组上排序，空间复杂度为O(1)

快速排序稳定性

快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

python实现

def quick_sort(nums, left, right):
    if left >= right:
        return
    j = partition(nums, left, right)
    if left < j - 1:
        quick_sort(nums, left, j-1)
    if right > j + 1:
        quick_sort(nums, j+1, right)

def partition(nums, left, right):
    tmp = left    #基准轴
    i = left + 1
    j = right
    while i <= j:
        while i <= right and nums[i] <= nums[tmp]:
            i += 1
        while j > left and nums[j] > nums[tmp]:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    if tmp != j:
        nums[tmp], nums[j] = nums[j], nums[tmp]

    return j


if __name__ == '__main__':
    nums = list(map(int, input().strip().split(' ')))
    quick_sort(nums, 0, len(nums)-1)
    print(nums)

C++实现

int partition(int nums[], int left, int right)
{
    int tmp = left;
    int i = left + 1;
    int j = right;
    while(i <= j)
    {
        while(i<=right && nums[i]<=nums[tmp])
            i++;
        while(j>left && nums[j] > nums[tmp])
            j--;
        if(i < j)
            swap(nums[i], nums[j]);
    }
    swap(nums[tmp], nums[j]);
    return j;
}

void quick_sort(int nums[], int left, int right)
{
    if(left >= right)
        return;
    int j = partition(nums, left, right);
    if(j - 1 > left)
        quick_sort(nums, left,j - 1);
    if(j+1 < right)
        quick_sort(nums, j + 1, right);
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int partition(int left, int right, int nums[]) {
    if (left >= right) {
        return left;
    }
    int tmp = left;
    while (left <= right) {
        while(nums[left] <= nums[tmp] && left <= right) {
            left++;
        }
        while(nums[right] > nums[tmp] && right >= left) {
            right--;
        }
        cout << left << " " << right << endl;
        if (left < right) {
            swap(nums[left], nums[right]);
        }
    }
    swap(nums[right], nums[tmp]);
    cout << left << " " << right << endl;
    return right;
}

void quick_sort(int left, int right, int nums[]) {
    if (left >= right) {
        return;
    }
    int j = partition(left, right, nums);
    if (left < j - 1) {
        quick_sort(left, j - 1, nums);
    }
    if (j + 1 < right) {
        quick_sort(j + 1, right, nums);
    }
}

int main() {
    int n;
    cin >> n;
    int nums[n];
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    }
    quick_sort(0, n - 1, nums);
    for(int i=0; i<n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}