排序系列 之 快速排序算法 —— Java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序系列 之 快速排序算法 —— Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1707字，纯文字阅读大概需要3分钟。
内容图文
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.设置 low=0, high=N-1。
2.选择一个基准元素赋值给temp,即temp=a[low]。
3.从high开始向前搜索，即由后开始向前搜索（high--），找到第一个小于temp的值，将a[high]和a[low]交换。
4.从low开始向前搜索，即由前开始向后搜索（low++），找到第一个大于temp的值，将a[high]和a[low]交换。
5.重复第3步和第4步，直到 low==high ,3,4步中，若没找到符合条件的值，执行 high-- 或 low++ ，直到找到为止。进行交换时 low和high的位置不变。当low==high时循环结束。
基准点的选取：固定切分、随机切分、三取样切分。
快速排序是不稳定的
快速排序在序列元素很少时，效率比较低。因此，元素较少时，可选择使用插入排序。
Java实现：
package
sort;
/**
* 快速排序的实现
*
@author
那一季的银杏叶
*
*/
public
class
QuickSort {
public
static
void
main(String[] args) {
//
TODO Auto-generated method stub
new
QuickSort().run();
}
public
void
run(){
int a[] = {3,1,5,7,2,4,9,6};
int n = a.length;
System.out.println("———————————————————快速排序算法—————————————————————");
if(n>0){
quickSort(a, 0, n - 1);
}
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
/**
* 快速排序
* 快速排序 时间复杂度为O(NlogN).
*/privatevoid quickSort(int[] a,int low,int high){
if (low < high) {
/**
* 将数组a一分为二
*/int middle = getMiddle(a, low, high);
/**
* 将小于基准元素的数据进行递归排序
*/
quickSort(a, low, middle - 1);
/**
* 将大于基准元素的数据进行递归排序
*/
quickSort(a, middle + 1, high);
}
}
publicint getMiddle(int[] list, int low, int high) {
/**
* 数组的第一个数为基准元素
*/int temp = list[low];
while (low < high) {
while (low < high && list[high] > temp) {
high--;
}
/**
* 比基准小的数据移到低端
*/
list[low] = list[high];
while (low < high && list[low] < temp) {
low++;
}
/**
* 比基准大的记录移到高端
*/
list[high] = list[low];
}
/**
* 此时 low == high
*/
list[low] = temp;
return low;
}
}
运行结果展示：
（本文仅供学习交流，如有更好的思路，欢迎留下意见供大家探讨学习~）
原文：http://www.cnblogs.com/snowcan/p/6244398.html
内容总结
以上是互联网集市为您收集整理的排序系列 之 快速排序算法 —— Java实现全部内容，希望文章能够帮你解决排序系列 之 快速排序算法 —— Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。