java实现快速排序

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

回到顶部