快速排序算法原理及java递归实现
快速排序对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序。使用的是递归原理,在所有同数量级O(nlongn)的排序方法中,其平均性能最好。就平均时间而言,是目前被认为最好的一种内部排序方法
基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
三个指针:第一个指针称为pivotkey指针(枢轴),第二个指针和第三个指针分别为left指针和right指针,分别指向最左边的值和最右边的值。left指针和right指针从两边同时向中间逼近,在逼近的过程中不停的与枢轴比较,将比枢轴小的元素移到低端,将比枢轴大的元素移到高端,枢轴选定后永远不变,最终在中间,前小后大。
需要两个函数:
①递归函数 publicstaticvoidquickSort(int[]n,intleft,intright)
②分割函数(一趟快速排序函数)publicstaticintpartition(int[]n,intleft,intright)
JAVA源代码(成功运行):
packagetestSortAlgorithm;
publicclassQuickSort{
publicstaticvoidmain(String[]args){
int[]array={49,38,65,97,76,13,27};
quickSort(array,0,array.length-1);
for(inti=0;i<array.length;i++){
System.out.println(array[i]);
}
}
/*先按照数组为数据原型写出算法,再写出扩展性算法。数组{49,38,65,97,76,13,27}
**/
publicstaticvoidquickSort(int[]n,intleft,intright){
intpivot;
if(left<right){
//pivot作为枢轴,较之小的元素在左,较之大的元素在右
pivot=partition(n,left,right);
//对左右数组递归调用快速排序,直到顺序完全正确
quickSort(n,left,pivot-1);
quickSort(n,pivot+1,right);
}
}
publicstaticintpartition(int[]n,intleft,intright){
intpivotkey=n[left];
//枢轴选定后永远不变,最终在中间,前小后大
while(left<right){
while(left<right&&n[right]>=pivotkey)--right;
//将比枢轴小的元素移到低端,此时right位相当于空,等待低位比pivotkey大的数补上
n[left]=n[right];
while(left<right&&n[left]<=pivotkey)++left;
//将比枢轴大的元素移到高端,此时left位相当于空,等待高位比pivotkey小的数补上
n[right]=n[left];
}
//当left==right,完成一趟快速排序,此时left位相当于空,等待pivotkey补上
n[left]=pivotkey;
returnleft;
}
}
相关文章
- 快速排序算法详细图解JAVA_实现快速排序
- JAVA多线程面试题_java多线程的实现方式
- Java数据结构与算法(排序)——基数排序(LSD)
- think in java一_Think in Java(一):Java基础「建议收藏」
- 安卓java游戏模拟器_Java手机游戏模拟器
- md5 java 实现_MD5加密的Java实现
- 八大排序算法(java实现) 冒泡排序 快速排序 堆排序 归并排序 等[通俗易懂]
- java实现四种常用排序算法
- 线性查找算法(Java实现)
- Java把string转json格式_java实体类转json字符串
- Java重置_java设置定时任务一小时执行一次
- JAVA对象转map_java处理字符串类型的map
- Java算法大全_java贪心算法几个经典例子
- java冒泡算法
- list java中List对象通用排序算法详解编程语言
- java归并排序算法代码详解编程语言
- java 排序算法详解编程语言
- java 标准输出与标准错误 out与 err 区别 用法 联系 java中的out与err区别 System.out和System.err的区别 System.out.println和System.err.println的区别 Java重定向System.out和System.err详解编程语言
- Linux下查看Java进程的方法(linux查看java进程)
- Java下使用Redis进行高效缓存优化(Redis缓存java)
- 使用Linux安装Java轻松搞定!(linux java安装)
- java合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
- java使用简单的demo实例告诉你优化算法的强大
- JAVA简单选择排序算法原理及实现
- 浅析java希尔排序(Shell)算法