排序算法——快速排序

一、快速排序

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)。