快速排序
快速排序思想
快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
算法步骤：
1.分解：
A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得 A[p ..q-1] <= A[q] <= A[q+1 ..r]
2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。
3.合并。
排序
基准(pivot)的选取选取数组分区后的第一个元素 对数组a[i,...,j]进行操作： 1.首先选择一个中间元素（一般选左端或者右端）。
2.分别获取除中间元素外的左右两端的索引。
3.由左右两端逐渐向中间迭代，每迭代一步比较一下索引中的元素和中间元素，当左边出现比中间元素大的元素的时候，暂停左边的迭代，当右边迭代出比中间元素小的元素的时候，右边迭代也暂停，交换左右两边的元素。
4.重复步骤3，直到左右两边的索引相遇，然后将中间元素移动到中间，这时中间元素左边的元素都比它小，右边的元素都比它大。
5.将上面的中间元素左右两边当成两个数组，分别进行上述过程。
6.重复以上步骤直到数组不可再分。
代码如下
public class quick_sort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={4,5,6,7,223,21,5,22,445,55,2,5,88,33,66,22,4456,3,24,56,78,222};
quickSort(a);
for(int i=0;i<a.length;i++){
System.out.println(a);
}
}
public static void sort(int array[],int low,int high){
int i,j;
int index;
if(low>=high){
return;
}
i=low;
j=high;
index=array[i];
while(i<j){
while(i<j && array[j]>=index){
j--;
}
if(i<j){
array[i++]=array[j];
}
while(i<j && array[i]<index){
}
if(i<j){
array[j--]=array[i];
}
}
array[i]=index;
sort(array,low,i-1);
sort(array,i+1,high);
}
public static void quickSort(int array[]){
sort(array,0,array.length-1);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.02.21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录