快速排序详解

Excel表格快速排序，Ctrl + Shift + F4 #生活技巧# #数码产品使用技巧# #办公软件快捷键#

快速排序（quick sort）
一．简介
快速排序是对冒泡排序和桶排序的一种改进，它解决了冒泡排序时间复杂度达O（N2）的问题，并解决了桶排序浪费空间的问题。它的基本思想是，通过一趟排序将待排序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以用相同的方法分别对这两部分继续排序，以达到整个序列有序。
二．算法描述
假设我们对“49 38 65 97 76 13 27 49 ”这8个数进行排序。首先我们要在这个序列中找一个基准数（一个参照值），这个值的作用是，经过一趟排序（这里用升序来讲），使得基准数右边的数都比基准数左边的数大。为了方便，我们就把这个已知序列的第一个数49当做基准数。然后我们要做的就是把比基准数大的放它右边，比基准数小的放基准数左边，比如经过一趟排序后：13 38 27 49 76 97 65 49。
在初始状态下，基准数49在序列的第一个位置，假设这个基准数为key，我们的目标就是把这个key放到序列中某个位置，并且使得key右边的数都大于左边的数，想一想如何达到这个目标？大家可以回忆一下冒泡排序，当中交换的思想使得序列一步步变得有序。冒泡排序每次都只能和相邻的数比较，这样使得冒泡排序很浪费时间，我们怎么才可以使得交换即方便又省时呢？
为了达到目的：叫两个哨兵分别从初始序列“49 38 65 97 76 13 27 49”两边开始“探测”，假设这两个哨兵是i和j，j从序列最右端开始（而且必须得它先开始），当它“探测”到一个比基准数（49）小的数就停下来，然后i从序列最左端开始“探测”，当它“探测”到一个比基准数大的数就停下来，（前提的保证i，j还没相遇）然后交换这两个位置的值，就像这样：
交换之后，继续上述的“探测”，都“探测”到继续进行交换，直到两个哨兵相遇，此时相遇的位置的值不会比基准数大，（要达到上述的目的）所以这个位置就是基准数应该在的真正位置，所以让相遇位置和基准数位置的数交换，就完成了我们第一趟排序，这时序列被基准数分成了我们想要的两部分：13 38 27 49 76 97 65 49。此时序列可以说是基本有序，之后要让序列完全有序，我们要将基准数分开的这两部分，分别重复第一趟排序的的操作（重新找基准数，两个哨兵探测，交换…）。
图解过程（第一趟后，左右两部分是分开处理的哦~）：

三．算法分析
快速排序之所以比较快，因为它交换是跳跃式的，不像冒泡排序每次交换只能交换相邻的。不过它在最坏的情况下时间复杂度和冒泡排序一样都为O（N2），它的平均时间复杂度为O（NlogN）。
四.C语言代码实现（作为参考~）

#include <stdio.h> int a[105]; void quick_sort(int left, int right) { if(right < left) return; int i = left,j = right,temp,t; temp = a[left]; while( i != j) { while(a[j] >= temp&&i < j) j--; while(a[i] <= temp&&i < j) i++; if(i < j) { t = a[j]; a[j] = a[i]; a[i] = t; } } a[left] = a[i]; a[i] = temp; quick_sort(left,i-1); quick_sort(i+1,right); } int main() { int n; while(~scanf("%d",&n)) { for(int i = 0; i < n; i++) { scanf("%d",&a[i]); } quick_sort(0,n-1); for(int i = 0; i < n; i++) { printf("%d ",a[i]); } printf("\n"); } return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142

网址：快速排序详解 https://www.yuejiaxmz.com/news/view/551366

相关内容

快速排序算法详解
客房怎样快速打扫技巧 快速打扫客房技巧详解
Windows 7桌面整理攻略：快速排序，打造高效桌面工作环境
小程序解决会议室预约，高效提升日程安排！
有序恢复工作生活秩序后，出行应该注意什么？详解→
LIFE ELEMENT 生活元素 暖菜板解冻神器恒温快速化冰食物急速解冻器牛排解冻盘 199元（需用券）
怎样快速清洁微波炉 快速清洁微波炉方法【详解】
如何快速缓解职场压力
重磅！支付宝小程序正式推出，商户可借助即速应用快速开发！
《江南百景图》生姜获得方法详解：快速获取秘诀分享

随便看看