一、如何用java实现快速排序,简答讲解下原理
二、快速排序
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
下面通过一个例子介绍快速排序算法的思想,假设要对数组a[10]={6,1,2,7,9,3,4,5,10,8}进行排序,首先要在数组中选择一个数作为基准值,这个数可以随意选择,在这里,我们选择数组的第一个元素a[0]=6作为基准值,接下来,我们需要把数组中小于6的数放在左边,大于6的数放在右边,怎么实现呢?
我们设置两个“哨兵”,记为“哨兵i”和“哨兵j”,他们分别指向数组的第一个元素和最后一个元素,即i=0,j=9。首先哨兵j开始出动,哨兵j一步一步地向左挪动(即j–),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i),直到找到一个数大于6的数停下来。
最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。此时就需要交换i和j指向的元素的值。
交换之后的数组变为a[10]={6,1,2,5,9,3,4,7,10,8}:
第一次交换至此结束。接下来,由于哨兵i和哨兵j还没有相遇,于是哨兵j继续向前,发现比6小的4之后停下;哨兵i继续向前,发现比6大的9之后停下,两者再进行交换。交换之后的数组变为a[10]={6,1,2,5,4,3,9,7,10,8}。
第二次交换至此结束。接下来,哨兵j继续向前,发小比6小的3停下来;哨兵i继续向前,发现i==j了!!!于是,这一轮的探测就要结束了,此时交换a[i]与基准的值,数组a就以6为分界线,分成了小于6和大于6的左右两部分:a[10]={3,1,2,5,4,6,9,7,10,8}。
至此,第一轮快速排序完全结束,接下来,对于6左边的半部分3,1,2,5,4,执行以上过程;对于6右边的半部分9,7,10,8,执行以上过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列:1 2 3 4 5 6 7 8 9 10,到此,排序完全结束。
快速排序的一次划分算法从两头交替搜索,直到low和hight重合,因此其时间复杂度是O(n);而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是,每次划分所选择的中间数恰好将当前序列几乎等分,经过log 2 n趟划分,便可得到长度为1的子表。这样,整个算法的时间复杂度为O(nlog 2 n)。
最坏的情况是,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度-1。这样,长度为n的数据表的快速排序需要经过n趟划分,使得整个排序算法的时间复杂度为O(n 2 )。
为改善最坏情况下的时间性能,可采用其他方法选取中间数。通常采用“三者值取中”方法,即比较H->r[low].key、H->r[high].key与H->r[(lowhigh)/2].key,取三者中关键字为中值的元素为中间数。
可以证明,快速排序的平均时间复杂度也是O(nlog 2 n)。因此,该排序方法被认为是目前最好的一种内部排序方法
三、快速排序算法原理与实现
快速排序的基本思想就是从一个数组中任意挑选一个元素(通常来说素)作为中轴元素,将剩下的元素以中,将小于等于中轴元素的放到中轴元素的左边,将大于中轴元素的放到中轴元素的右边。
然后以当前中轴元素的位置为界,将左半部分子数组和右半部分子数组,直到子数组的元素个数小于等于1(因为一个元素的数组必定是有序的)。
数组中两个元素值的Swap方法,其代码
public static void Swap(int[] A, int i
int tmp;
tmp =
A[i] = A[j];
A[j] = tmp;
扩展资料:
快速排序算法 的基本思想是:将所要进行排序的数分为左右两有数据都比另外一 部分的数据小,然后将所分得的两分,重复执行以上的划分操作,直 到所有要进行排序的数据变为
定义两个变量low和high,将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次,low和high的取值分别为0和n-1,接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。
定义一个变量key,接下来以key的取值为基准将数组A划分为左右值为要进行排序序列的第一个元素值。第一次的毎次取值由要划 分序列的起始元素决定。
从high所指向的数组元素开始向左扫描,扫描的同时将下标为high的数组元素依较操作,直到high不大于low或找到第一个小于基准值该值赋值给low所指向的数组元素,同时将low右移一个位置。
如果low依然小于high,那么由low所指向的数组元素开始向右扫描,扫描的同时将下标为low的数组元素值依次与划分的基准作,直到low不小于high或找到第一个大于基准值key的数组元素,然后将该值赋给high所指向的数组元素,同时将hi
重复步骤(3) (4),直到low的植不小于功划分后得到的左右两部分分别为A[low……pos-1]和A[pos1……high],其中,pos下标所对应的数组元素的值就是进行划分的基准值ke为pos的数组元素赋
参考资料:快速排序算法_百度百科