快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)。
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一趟快速排序的算法是:
1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;
2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I=J;
例如:待排序的数组A的值分别是:(初始关键数据X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
进行第一次交换后: 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找)
进行第二次交换后: 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )
进行第三次交换后: 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找)
进行第四次交换后: 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )
此时再执行第三步的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27 38 13 49 76 97 65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束
结束
图6 快速排序全过程
1)、设有N(假设N=10)个数,存放在S数组中;
2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];
3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下,那么第一躺快速排序的过程是:
数组下标: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53
通过一躺排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。
/**
*交换指定数组a的两个变量的值
*@parama数组应用
*@parami数组下标
*@paramj数组下标
*/
publicstaticvoid swap(int a[], int i, int j) {
if(i == j) return;
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
/**
*
*@paramarray待排序数组
*@paramlow数组下标下界
*@paramhigh数组下标上界
*@returnpivot
*/
publicstaticint partition(int array[], int low, int high) {
//当前位置为第一个元素所在位置
int p_pos = low;
//采用第一个元素为轴
int pivot = array[p_pos];
for (int i = low + 1; i <= high; i++) {
if (array[i] < pivot) {
p_pos++;
swap(array, p_pos, i);
}
}
swap(array, low, p_pos);
return p_pos;
}
/**
*快速排序实现
*@paramarray
*@paramlow
*@paramhigh
*/
publicstaticvoid quickSort(int array[], int low, int high) {
if (low < high) {
int pivot = partition(array, low, high);
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
上面的代码是从网上找的,选取的是数组第一个数作为比较数,下面是自己写的,以中间的数为比较数,其实思想都是每次比较后把比较数放中间,然后不断递归下去而已:
public static void x_quickSort(int[] array, int low, int high){
if(low < high){
int midDataIndex = x_partition(array, low, high);
if(midDataIndex-1>low)
x_quickSort(array, low, midDataIndex-1);
if(midDataIndex+1<high)
x_quickSort(array, midDataIndex+1, high);
}
}
public static int x_partition(int[] array, int low, int high){
int midData = array[(low+high)/2];
x_swap(array, low, (low+high)/2);
int midDataIndex = low;
low++;
boolean low_found = false;
while(low<high){
if(array[low]<midData && !low_found)
low++;
else
low_found = true;
if(array[high]>midData)
high--;
else if(low_found){
x_swap(array, low, high);
low_found=false;
high--;
}
}
if(array[low]<midData)
x_swap(array, low, midDataIndex);
else
x_swap(array, low-1, midDataIndex);
return low;
}
public static void x_swap(int[] array, int low, int high){
if(low==high) return;
array[low] = array[low] + array[high];
array[high] = array[low] - array[high];
array[low] = array[low] - array[high];
}
相关推荐
网上关于快速排序的算法原理和算法实现都比较多,不过java是实现并不多,而且部分实现很难理解,和思路有点不搭调。所以整理了这篇文章。如果有不妥之处还请建议。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
包含Bit-map、堆排序、二分查找、哈希表、快速排序等算法的原理及其C实现代码
在这个教程中,我们将深入探讨快速排序的工作原理,并提供一个Java示例来演示如何实现它。无论您是新手还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的排序工具,有助于解决各种排序问题。 快速排序...
主要介绍了Java 快速排序(QuickSort)原理及实现代码,有需要的朋友可以参考一下
这里提供了冒泡排序,插入排序,递归排序,基数排序,快速排序,选择排序,希尔排序这几种排序算法。里面有大量的注释,可以理解实现思路
在本篇文章里小编给大家整理了关于PHP快速排序算法实现的原理及代码相关知识点,需要的朋友们跟着学习下。
快速排序 简介 复杂度与稳定性 过程介绍 图示过程 主要代码实现 计数排序 简介 复杂度与稳定性 过程介绍 图示过程 代码实现 桶式排序 简介 复杂度与稳定性 过程介绍 图示过程 代码实现 基数排序 ...
目录插入排序直接插入排序基本原理代码实现性能分析折半插入排序代码实现希尔排序基本原理代码...快速排序基本原理代码实现(递归和非递归)性能分析归并排序基本原理代码实现性能分析排序总结各种排序算法之间的比较...
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 void Init_Random();//数组随机数初始化函数声明 void Show_Array();//展示...
冒泡排序和快速排序则是经典的排序算法,通过实际编码实现,可以更加直观地感受它们的效率差异和应用场景。 除此之外,项目还包含了链表、栈、队列等其他常见数据结构的实现,以及基于这些数据结构的实际应用案例。...
本文实例为大家分享了C/C++实现双路快速排序算法的具体代码,供大家参考,具体内容如下 看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂。这里写一下自己的理解过程,也加深一下自己的理解...
选择排序、快速排序、冒泡排序三种基本排序方法的程序,vc6.0实现,思路清晰简单,注释详细易懂,通过对比可加深理解排序方法和原理。
本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。排序算法有许多种,这里介绍4中排序算法:冒泡...
快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素进行重新排列,以得到一个快速排序的分区。...
主要介绍了快速排序算法在Java中的实现,简单介绍了快速排序的实现原理,分享了两种实现代码,具有一定参考价值,需要的朋友可以了解下。
本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理,并进行代码实现。通过对大量样本的测试结果,统计不同排序算法的时间效率与输入规模的关系,通过经验分析方法,展示不同排序算法的时间...
代码实现 # -*- coding:utf-8 -*- """ Author: leadingme Mail:leadingme@qq.com MyWebsite:leadingme.top """ import timeit List = [7, 5, 9, 3, 5, 1, 12, 10, 15, 9] def bubbleSort(List):