本文目录
什么是快速排序
基本思想是:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入最终位置后,整个数据区间被此记录分割成两子区间。所有关键字比该记录关键字小的放置在前子区间中,所有比它大的放置在后子区间中,并把该记录排在这两个子区间的中间,这个过程称为一趟快速排序.
之后对所有的两个子区间分别重复上述过程,直至每个子区间内只有一个记录为止。简而言之,每趟排序使表的第一个元素入终位,将数据区间一分为二,对于子区间按递归方式继续这种划分,直至划分的子区间长为1。
快速排序
快速排序(Quicksort),计算机科学词汇,适用领域Pascal,c++等语言,是对冒泡排序算法的一种改进。
1、首先设定一个分界值,通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
3、然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
排序演示
假设一开始序列{xi}是:5,3,7,6,4,1,0,2,9,10,8。
此时,ref=5,i=1,j=11,从后往前找,第一个比5小的数是x8=2,因此序列为:2,3,7,6,4,1,0,5,9,10,8。
此时i=1,j=8,从前往后找,第一个比5大的数是x3=7,因此序列为:2,3,5,6,4,1,0,7,9,10,8。
此时,i=3,j=8,从第8位往前找,第一个比5小的数是x7=0,因此:2,3,0,6,4,1,5,7,9,10,8。
此时,i=3,j=7,从第3位往后找,第一个比5大的数是x4=6,因此:2,3,0,5,4,1,6,7,9,10,8。
此时,i=4,j=7,从第7位往前找,第一个比5小的数是x6=1,因此:2,3,0,1,4,5,6,7,9,10,8。
此时,i=4,j=6,从第4位往后找,直到第6位才有比5大的数,这时,i=j=6,ref成为一条分界线,它之前的数都比它小,之后的数都比它大,对于前后两部分数,可以采用同样的方法来排序。
快速排序的原理是什么
先
数据序列
选
元素,并
序列
所
比该元素
元素都放
右边或左边,再
左右两边
别用同
处
直
每
待处理
序列
度
1,
处理结束
前
序区R[1..H]
任取
数据元素作
比较
“基准“(
妨记
X)
用
基准
前
序区划
左右两
较
序区:R[1..I-1]
R[I+1..H]
且左边
序
区
数据元素均
于等于基准元素
右边
序
区
数据元素均
于等于基准元素
基准X则位于
终排序
位置
即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)
R[1..I-1]
R[I+1..H]均非空
别
进行
述
划
程
直至所
序
区
数据元素均已排序
止
快速排序
基本思想
基于
治策略
于输入
序列L[p..r]
规模足够
则直接进行排序(比
用前述
冒泡、选择、插入排序均
)
否则
三步处理:
解(Divide):
待排序列L[p..r]划
两
非空
序列L[p..q]
L[q+1..r]
使L[p..q]
任
元素
值
于L[q+1..r]
任
元素
值
具体
通
途径实现:
序列L[p..r]
选择数据元素L[q]
经比较
移
L[q]
处于L[p..r]
间
适
位置
使
数据元素L[q]
值
于L[q+1..r]
任
元素
值
递归求解(Conquer):通
递归调用快速排序算
别
L[p..q]
L[q+1..r]进行排序
合并(Merge):由于
解
两
序列
排序
进行
所
L[p..q]
L[q+1..r]都排
序
需要执行任何计算L[p..r]
已排
序
即自
合并
解决流程
符合
治
基本步骤
快速排序
治
经典应用实例
快速排序的原理 详细点 谢谢
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A;
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将值为key的项与A[j]交换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将值为key的项与A[i]交换;
5)重复第3步
6)重复第3、4、5步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
快速排序方法的简单解释
快排的思想是(假设都是从小到大排列):
选一个值作为“轴值”,所有小于轴值的都移动到轴值左边,所有大于轴值的都移动到轴值右边。这一步是让数列变得较为有序
然后分别再对轴值的左边、右边分别进行快排,一步一步提高整个数列的有序程度,直到最后完全有序。
轴值的选取有多种方式,这里就假设是选正中间的一个
70,75,82,90,23,16,10,68
选择轴值 90,排列后得到:
70,75,82,23,16,10,68,(90)
括号括起来的我表示是轴值,这里运气不好,轴值选中了一个最大的
下面对轴值左边排序,在选择轴值为23:
16,10,(23),70,75,82,68
再分别对16, 10 和 70,75,82,68进行排序
一般快排在待排序的数字个数较少时,会选取其它排序来进行排列,比如插入排序。这里16,10数字个数已经太少,用插入排序排成10, 16
然后对 70,75,82,68进行排序……
整个排序过程就这样