开发者社区> mia26jtrojklq> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

常用且强大的排序算法——快速排序

简介: 快速排序是交换排序的一种,是由冒泡排序改进而得的。 大家回忆一下,在冒泡排序中,只是简单的对相邻的两个记录进行比较,这是冒泡排序的专属限定,但就是这种限定限制了冒泡排序的能力 它每次交换只能消除一个逆序 那么有没有一种算法,一次比较可以消除多个逆序呢? of course!那就是——快速排序
+关注继续查看

image

快速排序:

快速排序是交换排序的一种,是由冒泡排序改进而得的。

大家回忆一下,在冒泡排序中,只是简单的对相邻的两个记录进行比较,这是冒泡排序的专属限定,但就是这种限定限制了冒泡排序的能力

它每次交换只能消除一个逆序

那么有没有一种算法,一次比较可以消除多个逆序呢?

of course!那就是——快速排序

算法思维:

1.在待排序的n个数中取第一个数(当然可以使任意一个数)作为枢轴

2.用temp来记录这个数

3.进过一趟排序后,把所有小于temp的数交换到前面,把所有大于temp的数交换到后面

4.把以temp为界的左右两边分成两个子表,再对着两个子表进行123这三步,直到每个子表长度为1,排序结束~

图片展示:

image

具体步骤:

1.选定数组的第一个数作为枢轴,用temp来记录它

2.设置两个指针——low和high,分别指向a[0]和a[n-1](数组末尾)

3.先从high的位置向左边开始搜索,找到第一个数值比temp小的数,此时high指向它,将这个数换到low所指向的位置,high停止移动

4.再从low开始向右边开始搜索,找到第一个数值比temp大的数,此时low指向它,将这个数换到high所指向的位置,low停止移动

5.接着进行34的循环,直到low和high重合,将temp的值赋值给low(或者high)

6.345就是一趟排序,对temp的左右两边进行拆分成两个子表,再次进行345,直到数组的每个子表的长度都是1,快速排序结束

核心代码:

找位置部分:

image

快速排序部分:

imagePS:现在,我以下图为例子,进行快速排序的代码测试:image

总代码:

#include<iostream>
using namespace std;
//找位置
int Partition(int a[], int low,int high) {
    int temp = a[low];
    while (low < high) {
        while (low < high && a[high] >= temp)
            high--;
        a[low] = a[high];
        while (low < high && a[low] < temp)
            low++;
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}
//快速排序
void QuickSort(int a[], int low, int high) {
    if (low < high) {//长度要大于一
        //找枢轴
        int mid = Partition(a, low, high);
        //分别递归的搜索左右子表
        QuickSort(a, low, mid - 1);
        QuickSort(a, mid + 1, high);
    }
}
//展示函数
void display(int a[], int n) {
    for (int i = 0; i < n; i++)
        cout << a[i] << "  ";
}
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    QuickSort(a, 0, n - 1);
    display(a, n);
    
    cout << endl;
    system("pause");
    return 0;
}

测试结果:

imagePS:代码无毒,请放心食用~

复杂度分析:

  • 时间复杂度:

最好情况:O(nlog₂n)

最坏情况:O(n²)

平均情况:O(nlog₂n)

  • 空间复杂度:

快速排序是递归的,执行时需要有一个栈来存放数据

空间复杂度:O(log₂n)

  • 稳定性:

记录非顺次的移动导致排序方法是不稳定的

  • 特点:

1.排序的过程由于需要定位,所以适用于顺序存储结构,不适用于链式存储结构

2.当n较大时,在平均情况下,快速排序是所有内部排序中速度最快的一种

PS:这就是快速排序的全部内容了,点个赞再走吧~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法之快速排序
快速排序(Quick Sort)
21 0
排序算法:快速排序
排序算法:快速排序
26 0
【算法】快速排序
【算法】快速排序
17 0
算法-快速排序
快速排序是广泛使用的排序算法,它在平均情况下进行n log n比较,以对 n 个元素的数组进行排序。该算法遵循分而治之的方法。分而治之是一种将算法分解为子问题,然后解决子问题,并将结果组合在一起以解决原始问题的技术。
28 0
【算法】快速排序
【算法】快速排序
29 0
排序算法之快速排序
快速排序      快速排序是在待排序序列中选定一个数(一般以选择第一个数),然后将待排序序列这样处理:以选定的这个数为基准,这个数的左边存放比它小的数,右边存放比它大的数。处理完之后去右边的区间选定一个数继续进行这样的过程,去右边的区间选定一个数继续进行这样的过程。      例如序列{50, 10, 90, 30, 70, 40, 80, 60, 20}。第一趟时,选
951 0
算法之快速排序
快速排序 是1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称为分治法 (Divide-and-Conquer Method)。 分治法的基本思想 :将原问题分解为若干个规模更小但结构与原问题相似的子问题。
737 0
+关注
mia26jtrojklq
擅长C/C++,精通PS、AI、C4D等
137
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载