快速排序算法思想
分治法：比大小，再分区
- 从数组中取出一个数，作为基准数；
- 分区：将比这个数大或等于的数全放到他的右边，小于他的数全放到他的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
实现思路：
- 将基准数挖出形成第一个坑。
- 由后向前找比他小的数，找到后挖出此数填到前一个坑中。
- 由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
- 再重复执行2，3两步骤。
实现思路框图：
实现代码：
public static void main(String[] args){
int arr[]={2,4,2,6,7,2,4,2,1,56,12,5,6,-3};
Mytool.quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end) {
if(start<end){
int index = getIndex(arr,start,end);
quickSort(arr,index+1,end);
quickSort(arr,start,index-1);
}
}
private static int getIndex(int[] arr, int start, int end) {
int i = start;
int j = end;
int x = arr[i];
while(i<j){
while(i<j&&arr[j]>=x){
j--;
}
if(i<j){
arr[i]=arr[j];
i++;
}
while(i<j&&arr[i]<x){
i++;
}
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=x;
return i;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/14650.html
