快速排序是典型的使用分治策略的一种交换排序.
一般步骤:
1)选择一个枢纽元素(关键点);
2)使用该枢纽元素分割数组,使得比该元素小的元素在它的左边,比它大的在右边。并把枢纽元素放在合适的位置;
3)根据枢纽元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
由于关键点是用来比较的基准所以如果基准选择得当可以减少交换的次数, 从而提高算法效率 , 是比较有技巧的部分), 以该关键点元素作为基准, 从数组两头分别与之比较, 大的放右边,小的放左边,相等的无论哪边都成(干脆不动). 最后当遍历完数组一遍(即两头的标志指向同一个数组元素)时把关键点元素放到该位置(此时确定这里为分治点 ),完成一次排序.
例如:待排序的数组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
进行第三次交换后: 27 38 13 97 76 49 65
进行第四次交换后: 27 38 13 49 76 97 65
经过一躺快速排序之后的结果是:
27 38 13 49 76 97 65
即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程:
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序后:
{13} 27 {38} 49 { 65} 76 {97}
public class Quicksort {
private int getPivot(int begin, int end) {
return (begin + end) >> 1;
}
// 一次排序
private int partition(int[] array, int begin, int end) {
int pivot = getPivot(begin, end);
// int pivot=0; 也可以
int tmp = array[pivot];
array[pivot] = array[end];
while (begin != end) {
while (array[begin] < tmp && begin < end)
begin++;
if (begin < end) {
array[end] = array[begin];
end--;
}
while (array[end] > tmp && end > begin)
end--;
if (end > begin) {
array[begin] = array[end];
begin++;
}
}
// 此时两个下标指向同一个元素.以这个位置左右分治(分治点)
array[begin] = tmp;
return begin;
}
private void qsort(int[] array, int begin, int end) {
if (end - begin < 1)
return;
int pivot = partition(array, begin, end);
qsort(array, begin, pivot);
qsort(array, pivot + 1, end);
}
public void sort(int[] array) {
qsort(array, 0, array.length - 1);
}
public static void main(String[] args) {
int[] array = { 3, 2, 2, 2, 3, 1, 4, 5, 1 };
// int[] array={49,38,65,97,76,13,27};
new Quicksort().sort(array);
//new Quicksort().partition(array,0,6);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ", ");
}
}
}
下载源码:
分享到:
相关推荐
快速排序 java实现
快速排序的简单实现程序,java编制,迭代法对数据组分区,知道简单的java基础,基本就可以看懂这个小程序了
快速排序JAVA源代码,已运行成功 同时可以记录整个过程中的比较次数
快速排序 java代码
快速排序 java c++ 随机算法 最高效
详细解释了快速排序的java实现.里面有代码,还有注释说明
public static void quicksort(int[] array,int start, int end){ if(start>=end) return; int middle=partition(array,start,end); quicksort(array,start,middle-1); quicksort(array,middle+1,end);...
利用分治法思想实现快速排序,Java语言描述。
java 快速排序 折半查找的界面实现 (递归与分治法)
快速排序算法,可以运行,运行截图一并打包,分享给大家。
此代码是快速排序的实现代码,采用分治的方法,能垢计算计算机处理快速排序的时间。
java语言实现的快速排序源码,其中包括java语言的随机数组生成器。
NULL 博文链接:https://funine.iteye.com/blog/2426289
采用java语言实现的排序排序,通俗易懂。
java中实现快速排序算法。随机产生几个数然后对其进行排序
这是我自己写的java,快速排序法。以前在网上找了很久,都没有合适的,就自己写了个,希望大家有需要的能用到。呵呵呵
用Java语言 实现 快速 排序
包括冒泡,归并和快速排序三种排序方式的java代码,可执行
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045