package com.arithmetic.sort; /** * 快速排序法: * 1 选择轴值 ,尽可能使得Left and Right 相等 * 策略: 选择最左边;随机选择;选择平均值 * * @author Administrator * */ public class QuickSort { public static void main(String[] args) { int [] arrays = new int[]{8,2,7,3,6,4,9,1,5,10}; quickSort(arrays, 0, arrays.length-1); for(int i = 0; i<arrays.length;i++){ System.out.print(arrays[i]+" "); } System.out.println(); } /** * 这个函数用于产生轴值或者叫做基准值的位置 * @param begin * @param end * @return */ public static int getPivot(int begin, int end){ return (begin + end) >> 1; } /** * 每一次的分割 * @param arrays * @param begin * @param end * @return */ private static int partition(int[] arrays, int begin, int end){ //得到基准值位置 int pivot = getPivot(begin, end); //得到基准值 int pivotValue = arrays[pivot]; /*将最后一个值赋给pivot 位置,意思就是把轴值作为一个临时变量用于和子序列进行比较,而最后一个 *空着,我们会第一个大于轴值得数据 */ arrays[pivot] = arrays[end]; //只要begin 和 end不相等 ,我们就认为本次排序没有结束 while(begin != end){ //如果begin <end 且 array[begin] < 轴值,我们就认为这个数比轴值小,而不用去管他,就继续比较下一个 while(begin < end && arrays[begin] < pivotValue){ begin++; } //如果begin <end 但是array[begin] > 轴值,我们就把当前值放在最后一个位置 //并且 end位置往前移动一个指针 if(begin < end && arrays[begin] > pivotValue){ arrays[end] = arrays[begin]; end--; } //此时我们就从右边开始比较比,比轴值小的放到刚才begin的位置,如果比轴值大,我们不管 while(begin < end && arrays[end] >= pivotValue ){ end --; } //如果begin < end, 但是array[end] < 轴值,我们就把当前值放在begin空着的那个位置 if(begin < end && arrays[end] < pivotValue){ arrays[begin] = arrays[end]; begin++; } } //如果begin 和 end 相遇,即begin == end,此时两个下标指向同一个元素,即轴值 arrays[begin] = pivotValue; return begin; } /** * 开始进行快速排序 * @param arrays * @param low * @param high */ public static void quickSort(int[] arrays, int low, int high){ if((high - low) < 1){//如果只有一个数或者为空 直接返回 return; } if((high - low) == 1){//如果只有2个数,且前面的数大于后面的数,我们直接交换没有必要快速排序 if(arrays[low] > arrays[high]){ swap(arrays, low, high); } } int pivotPosition = partition(arrays, low, high); quickSort(arrays, low, pivotPosition);//(递归)前面那个子序列 quickSort(arrays, pivotPosition+1, high);//(递归)后面子序列 } /** * 进行值交换 * @param arrays * @param index1 * @param index2 */ public static void swap(int[] arrays,int index1, int index2 ){ int tmp = arrays[index1]; arrays[index1] = arrays[index2]; arrays[index2] = tmp; } }
相关推荐
详解Java常用排序算法-快速排序
基于python的排序算法-快速排序Quick Sort
算法-数据结构和算法-13-快速排序.rar
《数据结构与算法》-李春葆 实验报告-典型排序算法实践-快速排序
算法-理论基础- 排序- 快速排序(包含源程序).rar
《算法设计与分析》实验报告---快速排序.pdf
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
算法设计,快速排序的C++实现代码,并测试运行时间
算法设计及分析实验报告---快速排序.doc
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
实现对数组的普通快速排序和随机快速排序,并统计算法运行时间。
采用速度快的快速排序节省时间,数据结构中快速排序需要时间相对时很短的。
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
算法设计与分析>>课程的实验程序,可以直接使用也可以修改后使用
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
运用编程工具,编程实现快速排序算法相关操作。 设计一个测试程序,并通过简单的图像变化来展示快速排序的实现过程,本程序采用Idea作为开发环境,操作简单,界面清晰,表达清楚,易于为用户所接受。