首先是百度百科地址
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
主要是贴代码:
static void quickSort(int[] v, int left, int right) { if (left < right) { int pivot = v[left]; // 枢轴 int low = left; int high = right; while (low < high) { // high下标位置开始,向左边遍历,查找不大于枢轴的元素 while (low < high && v[high] >= pivot) { high--; } if (low < high) { // 找到小于枢轴key的元素 v[low] = v[high]; // 赋值给low下标位置,low下标位置元素已经与枢轴对比过了 low++; // low下标后移 } else { // 没有找到比枢轴小的元素,说明high位置右边元素都不小于枢轴 break; } // low下标位置开始,向右边遍历,查找不小于枢轴的元素 while (low < high && v[low] <= pivot) { low++; } if (low < high) { // 找到比枢轴大的元素 v[high] = v[low]; // 赋值给high下标位置,high下标位置元素已经与枢轴对比过了 high--; // high下标前移, } else { // 没有找到比枢轴小的元素,说明low位置左边元素都不大于枢轴 break; } } v[low] = pivot; // low下标赋值枢轴 // 递归执行 quickSort(v, left, low - 1); quickSort(v, low + 1, right); } }
记录防忘!
相关推荐
C++排序算法之快速排序源码
C++排序算法之快速排序
数据结构排序算法之快速排序,可以再 vc6.0平台上直接运行,按照提示要求操作即可,希望对大家有所帮组……
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
1. 算法思想 选取一个基准值,将待排序数据分为左(小于基准值)右(大于基准值)两个区间,然后对两个分区的数据进行同样的循环操作,最后便可得到一组有序数据。...因此快速排序的平均时间复杂度为$O(n^
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
快速排序算法C语言实现,快排序算法QuickSort.cpp
用分治算法的思想,加上递归 实现快速排序
c语言版本的数据结构的快速排序算法,适用于新手学习
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
自己编写的基于java的快速排序和归并算法
详细解释了快速排序的java实现.里面有代码,还有注释说明