排序算法——快速排序

一、快速排序

1.1.快速排序简介

快速排序是一种效率极高的算法，主要思想就是找一个基准值，把整个序列分为左区间，和右区间，左区间小于基准值，右区间大于基准值。不断的对区间进行排序，直到序列有序。

1.2.快速排序思路

💡💡思路：

• 第一种：

  1. 选择基准值，一般该基准值为x = q[(l +r) >> 1] (为了避免有序的情况下，子问题规模依旧较大的问题)
  2. 把待排序列分为两个区间，一区间小于该基准值，另一区间大于该基准值。
  3. 递归的对两个区间进行快速排序，直到区间为空或者只有一个元素。
• 第二种：

1. 第1轮快速排序。首先在数列中找一个数作为基准数q(是用来参照的数，起哨兵作用)。为了方便，选择左边第一个数作为基准数。每次右指针r先移动(这点很重要)。初始状态下，基准数q在左边第1位，我们的目标是将基准数q挪到中间某个位置，以这个位置为分界点，分别对数列左边和右边的数进行排序。
2. 设左右指针，左指针left设在左边第一位，右指针right设在右边第一位
3. 右指针right向左移，找到小于基准值q的数，（注意一定是右指针先移动），之后左指针left向右移，找到大于基准值q的数。然后，两指针指向的数值进行交换
4. 右指针right继续左移，找到小于基准值q的数，此时左右指针相遇，第一轮排序结束。
5. 下面就是无限缩小区间，递归的对两个区间进行快速排序，一般都是用迭代。直到数组有序

1.3.时间复杂度

快速排序每次交换都是跳跃式的，因此比较快。快速排序法的效率与原始数据排列有关，因此属于不稳定的排序法。在最坏情况下，可能是相邻的两个数进行了交换

• 在最坏状态下：需要做O(n2)次比较，但这种状态并不常见。
• 在平均状态下，快速排序n个元素要做O(nlogn)次比较，其时间复杂度为O(nlogn)。事实上，快速排序明显比其他复杂度为O(nlogn)的算法要更快，因此它的内部循环效率很高。

1.4.空间复杂度

• 最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
• 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

因为快排用到了递归操作，需要的空间和递归次数有关系。

1.5.代码实现

C++代码：

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if (l >= r) return;
     // 分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        // 判断
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    // 递归处理子问题
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

Python代码：

def quickSort(num, left, right):   
        # 只有一个元素则结束递归            
        if left >= right:                           
            return 
        # 左边第1个元素作为基准数                     
        flag = left   
        # 循环比较，从第2个元素开始                     
        for i in range(left+1, right+1):           
            if num[flag]>num[i]     
                # 元素存入临时变量         
                tmp = num[i]   
                # 删除元素，后面的元素索引减1             
                del num[i]    
                # 将元素插入指定元素前面1个位置，指定元素向后移位              
                num.insert(flag,tmp)          
                flag += 1 
    # 将基准数左边部分递归排序                  
    quickSort(num, left, flag - 1)      
    # 将基准数右边部分递归排序             
    quickSort(num, flag + 1, right)               
num=[3,6,4,2,11,10,5]                
quickSort(num,0,6)                     
print(num)       


# 结果                         
>>>[2,3,4,5,6,10,11]                        

1.6.优缺点

优点：

平均性能好，O(nlog2n)

缺点：

不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。