内部排序算法:快速排序
基本思想
设当前待排序的数组无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无需参加后续的排序。
注意:划分的关键是要求出基准记录所在的位置pivotpos,划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high] 快速排序。
因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言, “组合”步骤不需要做什么,可看作是空操作。
算法实现
快速排序算法,Java实现,代码如下所示:
public abstract class Sorter {Integer pivot = array[i]; // 初始基准元素,如果quickSort方法第一次调用,pivot初始为数组第一个元素
采用分治的思想对待排序数组进行划分。分治法的基本思想是:
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序,主要是求得一个合理的划分,从而基于此划分来分治排序。使用简单划分方法的思想是:
第一步:
设置两个指针i和j,它们的初值分别为区间的下界和上界,即i=low,i=high; 选取无序区的第一个记录R[i](即R[low])作为基准记录,并将它保存在变量pivot中;
第二步:
快速排序示例过程,如下所示:
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20。
首先,根据数组下界和上界,求得一个划分,划分过程如下:
初始化:i = 0,j=19,以第一个元素array[0] = 94为基准pivot = array[0] = 94。
首先指针j向前移动:
array[19] = 49 pivot = array[0] = 94,i = 0 j = 19,继续移动j指针;
array[18] = 76 pivot = array[0] = 94,i = 0 j = 18,继续移动j指针;
……
array[1] = 12 pivot = array[0] = 94,i = 0 j = 1,继续移动j指针;
i = 0pivotPos-1 = -1排序停止;右侧部分继续递归执行快速排序。
对于{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}:
初始化:i = 1,j=19,以第二个元素(除了第一次划分的基准元素)array[1] = 12为基准pivot = array[1] = 12。
首先指针j向前移动:
array[19] = 49 =pivot = array[1] = 12成立,并且j = 19 i = 1,j指针继续移动;
array[18] = 76 =pivot = array[1] = 12成立,并且j = 18 i = 1,j指针继续移动;
array[17] = 65 =pivot = array[1] = 12成立,并且j = 17 i = 1,j指针继续移动;
array[16] = 12 =pivot = array[1] = 12成立,并且j = 16 i = 1,j指针继续移动;
array[15] = 37 =pivot = array[1] = 12成立,并且j = 15 i = 1,j指针继续移动;
array[14] = 90 =pivot = array[1] = 12成立,并且j = 14 i = 1,j指针继续移动;
array[13] = 83 =pivot = array[1] = 12成立,并且j = 13 i = 1,j指针继续移动;
array[12] = 68 =pivot = array[1] = 12成立,并且j = 12 i = 1,j指针继续移动;
array[11] = 5 =pivot = array[1] = 12不成立,j指针停止移动:
此时i = 1 j = 11,将j指针处的元素移动到i指针处:array[1] = 5(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 2;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12 处仍然是5):
{5,34,76,26,9,0,37,55,76,37,12,68,83,90,37,12,65,76,49}。
指针i向后移动:
array[2] = 34 =pivot = 12不成立,i指针停止移动:
此时i = 2 j = 11,将i指针处的元素移动到j指针处:array[11] = 34(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 10;
子数组变为:
{5,12,76,26,9,0,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 2= pivot = 12成立,并且j = 10 i = 2,j指针继续移动;
array[9] = 76 = pivot = 12成立,并且j = 9 i = 2,j指针继续移动;
array[8] = 55 = pivot = 12成立,并且j = 8 i = 2,j指针继续移动;
array[7] = 37 = pivot = 12成立,并且j = 7 i = 2,j指针继续移动;
array[6] = 0 = pivot = 12不成立,j指针停止移动:
此时j = 6 i = 2,将j指针处的元素array[6] = 0移动到i指针处:array[2] = array[6] = 0(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 3;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12处仍然是0):
{5,0,76,26,9,12,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第2次向后移动:
array[3] = 76i = 3,将i指针处的元素array[3] = 76移动到j指针处:array[6] = array[3] = 0(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 5;
子数组变为:
{5,0,12,26,9,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 3=pivot = 12不成立,j指针停止移动:
此时j = 5 i = 3,将j指针处的元素array[5] = 9移动到i指针处:array[3] = array[5] = 9(基准元素的拷贝为pivot = 12),同时i指针向后移动一次:i++,即i = 4;
子数组变为(下面左边的12表示基准元素,实际j指针移动后并没有移动基准元素,而是pivot变量持有它的拷贝,12处仍然是9):
{5,0,9,26,12,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
指针i第3次向后移动:
array[4] = 26i = 4,将i指针处的元素array[4] = 26移动到j指针处:array[5] = array[4] = 26(基准元素的拷贝为pivot = 12),同时j指针向前移动一次:j–,即j = 4;
子数组变为:
{5,0,9,12,26,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。
判断i与j:i = 4 j = 4不成立,条件不满足:
将基准元素放到i指针处,array[4] = pivot = 12;并返回基准元素的索引i = 4。
划分结束。
根据得到的基准元素的索引,递归快速排序。
算法分析
时间复杂度最好情况
在最好情况下,每次划分所取的基准都是当前无序区的”中值”记录,划分的结果是基准的左、右两个无序子区间的长度大致相等,总的关键字比较次数:0(nlgn)。
最坏情况
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。
因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值:
n(n-1)/2 = O(n^2)
如果按上面给出的划分算法,每次取当前无序区的第1个记录为基准,那么当文件的记录已按递增序(或递减序)排列时,每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录,则快速排序所需的比较次数反而最多。
快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(logn),故递归后需栈空间为O(logn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。
排序稳定性快速排序是不稳定的。
demo地址:https://github.com/weiman152/PaiXu.git 插入排序是一种局部有序的算法。插入排序把待排序的数组分成两部分,前半部分是有序的,但不是绝对有序,因为后面的数据还有可能插进来,改变现有顺序。
demo地址:https://github.com/weiman152/PaiXu.git 选择排序是先比较,并不急着交换,而是记录最小的值的位置,把最小的值与第一个位置的值进行交换。
相关文章
- go实现常见排序算法
- 图解排序算法(三)之堆排序
- 十大排序算法详解(一)冒泡排序、选择排序、插入排序、快速排序、希尔排序[通俗易懂]
- 算法与数据结构之计数排序
- sort用的什么排序算法_lambda表达式有什么组成
- LM算法代码_快速排序算法代码
- 算法学习之路 | 归并排序[Php]
- Python 排序与查找算法收集
- 排序算法
- 快速排序算法详解
- 使用ChatGPT生成了十种排序算法
- 常用排序算法介绍与实现详解程序员
- java选择排序算法详解编程语言
- Java数据结构和算法(九)——高级排序详解编程语言
- 必须知道的八大种排序算法【java实现】(一) 冒泡排序、快速排序详解编程语言
- 常见排序算法及对应的时间复杂度和空间复杂度详解编程语言
- 算法练习之x的平方根,爬楼梯,删除排序链表中的重复元素, 合并两个有序数组详解编程语言
- C语言归并排序算法
- MySQL的两种排序算法快速排序和归并排序(mysql两种排序算法)
- java合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
- C#排序算法之快速排序
- c#快速排序算法
- c语言实现奇偶排序算法
- stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
- C++实现各种排序算法类汇总
- 浅析java快速排序算法