用Java实现快速排序算法
快速排序是一个知名度极高的排序算法，其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。
算法概述/思路
快速排序一般基于递归实现。其思路是这样的：
1.选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值）,称为“枢轴”(pivot)。
2.基于这个值，将数组分为两部分，较小的分在左边，较大的分在右边。
3.可以肯定，如此一轮下来，这个枢轴的位置一定在最终位置上。
4.对两个子数组分别重复上述过程，直到每个数组只有一个元素。
5.排序完成。
代码实现
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //枢轴记录
while (low<high){
while (low<high && arr[high]>=pivot) --high;
arr[low]=arr[high]; //交换比枢轴小的记录到左端
while (low<high && arr[low]<=pivot) ++low;
arr[high] = arr[low]; //交换比枢轴小的记录到右端
}
//扫描完成，枢轴到位
arr[low] = pivot;
//返回的是枢轴的位置
return low;
}
<< · Back Index ·>>
上一篇
相关推荐
【幹貨分享】0基礎做抖小店實戰教程，電商新手小白必讀！
⚠️長文警告⚠️ 全文2800多字，這應該是目前知乎相對最全、最具體、最詳細的抖音小店實戰教程！下面我會用通俗易懂的語言，從抖...
世界船公司大全建议收藏以备查询
船公司名称大全 BNML邦拿美船务有限公司 CLAN S.A.南美邮船公司 CHOYANG朝阳商船有限公司 SENATOR德国胜利航运公司 EIL埃及 ...