排序算法之快速排序

系统管理员 2022-01-22 10:29 266阅读 0赞

快速排序是冒泡排序的改进版，也是最好的一种内排序，也是作为程序员必须掌握的一种排序方法。

快速排序的基本思想是

> 1、先从数列中取出一个数作为基准数

> 2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

> 3、再对左右区间重复第二步，直到各区间只有一个数

所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。

下面再看看示图理解下吧：

![280754329387398.png][]

### **下面是快速排序的C++代码：** ###

//
    // Created by liushihao on 19-6-5.
    //
    #include "iostream"
    using namespace std;
    
    typedef int KeyType;
    typedef struct
    {
        KeyType key;
        int data;
    }RecType;
    
    int partition(RecType R[], int s,int t)
    {
        int i=s,j=t;
        RecType tmp=R[i];
        while(i<j)
        {
            while(j>i && R[j].key>=tmp.key)
                j--;
            R[i]=R[j];
            while(i<j && R[i].key<=tmp.key)
                i++;
            R[j]=R[i];
        }
        R[i]=tmp;
        return i;
    }
    
    void QuickSort(RecType R[], int s, int t)
    {
        int i;
        if(s<t)
        {
            i=partition(R, s, t);
            QuickSort(R, s, i-1);
            QuickSort(R, i+1, t);
        }
    }
    
    int main()
    {
        int n;
        cin>>n;
        RecType R[n];
        for(int i=0;i<n;i++)
        {
            cin>>R[i].key;
        }
        for(int i=0;i<n;i++)
        {
            cout<<R[i].key<<" ";
        }
        QuickSort(R, 0, n-1);
        cout<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<R[i].key<<" ";
        }
        return 0;
    }

[280754329387398.png]: /images/20220122/73bfc8edf76c419a9ada11dbc541db03.png

发表评论取消回复

表情：

评论列表（有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法之快速排序

快速排序是一种基于分治思想的排序算法。它的基本思想是通过一趟排序将待排数据分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再分别对这两部分继续进行排序，重

谁践踏了优雅/ 2024年03月23日 07:09/ 0 赞/ 70 阅读

相关排序算法之快速排序

\[交换排序-快速排序\] 1.算法思想：选择一个元素作为基准，先从右向左遍历数组寻找比基准小的数a，然后从左向右寻找比基准大的数b，交换a和b的值，当左右会面

叁歲伎倆/ 2022年12月29日 14:25/ 0 赞/ 145 阅读

相关排序算法之快速排序

> 快速排序。 > 从数组中取出一个基准数，遍历数组中的每个元素，与基准数比较大小，将小于基准数的元素放在其左侧，大于基准数的元素放在其右侧， >

小咪咪/ 2022年11月03日 04:11/ 0 赞/ 185 阅读

相关排序算法之_快速排序

排序算法之-快速排序 package com.weidd.best.sort; / @program: SortDemo

水深无声/ 2022年10月30日 13:21/ 0 赞/ 181 阅读

相关排序算法之快速排序

同样的先上这张图 ![Center][] 下面分析交换排序之快速排序：快速排序的思想是先选择一个基准元素（一般取第一个元素），然后对剩下的元素作两端遍历，左边找

Dear 丶/ 2022年09月25日 15:24/ 0 赞/ 214 阅读

相关排序算法之快速排序

快速排序的基本思想是：通过一趟排序将要排序的[数据分割][Link 1]成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行

爱被打了一巴掌/ 2022年08月06日 13:22/ 0 赞/ 200 阅读

相关排序算法之快速排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

朴灿烈づ我的快乐病毒、/ 2022年06月16日 08:41/ 0 赞/ 256 阅读

相关排序算法之快速排序

package com.lin.sort; / @author 作者林尤庆 @version 创建时间：2016-8-12 下午02

蔚落/ 2022年06月09日 06:49/ 0 赞/ 222 阅读

相关排序算法之快速排序

快速排序是冒泡排序的改进版，也是最好的一种内排序，也是作为程序员必须掌握的一种排序方法。快速排序的基本思想是 > 1、先从数列中取出一个数作为基准数 > 2、分区过程，

系统管理员/ 2022年01月22日 10:29/ 0 赞/ 267 阅读

相关排序算法之快速排序

快速排序是一种高效的排序算法，它采用分而治之的思想，把大的拆分成小的，小的再拆分为更小的。其原理是：对于给定的数组，通过一趟排序之后，将原序列分为两部分，其中前一部分的所

秒速五厘米/ 2021年09月18日 04:24/ 0 赞/ 373 阅读