java实现快速排序
优化了一些细节,速度比上一个快排快10%
/*** @author CLY
* 快速排序
*/
public class MyQuickSort {
/**
* 对待排数组排序(升序)
* @param arr 待排数组
* @param pivot 枢轴在待排数组中的起始位置(排序起始位)
* @param end 本次快排的结束位(排序结束位)
*/
public static void sort(int[] arr,int pivot,int end) {
int tmp_pivot = pivot;
int tmp_end = end;
//为true时pivot在数组左边,为false时在右边
boolean flag = true;
//整个过程是end往pivot逼近的过程
while (tmp_pivot!=tmp_end) {
if (flag) {//pivot在左边
while (tmp_pivot<tmp_end) {
//如果成立,则枢轴被换到右边,比枢轴小的数被换到左边
if (arr[tmp_pivot]>arr[tmp_end]) {
int tmp = arr[tmp_pivot];
arr[tmp_pivot] = arr[tmp_end];
arr[tmp_end] = tmp;
int tmp_index = tmp_pivot;
tmp_pivot = tmp_end;
tmp_end = tmp_index;
tmp_end++;
break;
}else {//查找上一个右边的数,看是否比枢轴小
tmp_end--;
}
}
flag = false;
}else {//pivot在右边
while (tmp_pivot>tmp_end) {
//如果成立,则枢轴被换到左边,比枢轴大的数被换到左边
if (arr[tmp_pivot]<arr[tmp_end]) {
int tmp = arr[tmp_pivot];
arr[tmp_pivot] = arr[tmp_end];
arr[tmp_end] = tmp;
int tmp_index = tmp_pivot;
tmp_pivot = tmp_end;
tmp_end = tmp_index;
tmp_end--;
break;
}else {//查找下一个左边的数,看是否比枢轴大
tmp_end++;
}
}
flag = true;
}
}
//此时枢轴左边的数都比它小,右边的数都比它大。
//如果整个待排数组长度小于2,就表示已经排到底了。
if (end-pivot<2) {
return;
}
//如果当前枢轴在起始点的右边,就表示枢轴左边有值,可以对左边进行快排
if (tmp_pivot>pivot) {
sort(arr, pivot, tmp_pivot-1);//对左边的数进行快排
}
//如果当前枢轴在结束点的左边,就表示枢轴右边有值,可以对右边进行快排
if (tmp_pivot<end) {
sort(arr, tmp_pivot+1, end);//对右边的数进行快排
}
}
}
以上是 java实现快速排序 的全部内容, 来源链接: utcz.com/z/392238.html