快速排序

简介 这里我写了几次快排但是呢貌似都有问题所以这里就直接上代码了!!!

import java.text.SimpleDateFormat;

import java.util.Date;


public class QuikSort {

static int counter = 0;

static int arrSize = 80000;// 此处实测80000数据大概是1s左右


public static void main(String[] args) {

// TODO Auto-generated method stub

// 产生随机数

int arr[] = new int[arrSize];

for (int i = 0; i < arrSize; i++) {

arr[i] = (int) (Math.random() * 20);

}

// System.out.println(Arrays.toString(arr));

Date dateStart = new Date();

SimpleDateFormat format = new SimpleDateFormat("YYYY-MM-DD hh:mm:ss");

String start = format.format(dateStart);

System.out.println("开始时间:" + start);


// 测试数组

quickSort(arr, 0, arr.length - 1);


Date endStart = new Date();

String end = format.format(endStart);

System.out.println("结束时间:" + end);

// System.out.println(Arrays.toString(arr));

// TODO Auto-generated method stub


}


public static void quickSort(int arr[], int left, int right) {

int l = left; // 左下标

int r = right; // 右下标

// pivot 中轴值

int pivot = arr[(left + right) / 2];

int temp = 0; // 临时变量,作为交换时使用

// while循环的目的是让比pivot 值小放到左边

// 比pivot 值大放到右边

while (l < r) {

// 在pivot的左边一直找,找到大于等于pivot值,才退出

while (arr[l] < pivot) {

l += 1;

}

// 在pivot的右边一直找,找到小于等于pivot值,才退出

while (arr[r] > pivot) {

r -= 1;

}

// 如果l >= r说明pivot 的左右两的值,已经按照左边全部是

// 小于等于pivot值,右边全部是大于等于pivot值

if (l >= r) {

break;

}


// 交换

temp = arr[l];

arr[l] = arr[r];

arr[r] = temp;


// 如果交换完后,发现这个arr[l] == pivot值 相等 r--, 前移

if (arr[l] == pivot) {

r -= 1;

}

// 如果交换完后,发现这个arr[r] == pivot值 相等 l++, 后移

if (arr[r] == pivot) {

l += 1;

}

}


// 如果 l == r, 必须l++, r--, 否则为出现栈溢出

if (l == r) {

l += 1;

r -= 1;

}

// 向左递归

if (left < r) {

quickSort(arr, left, r);

}

// 向右递归

if (right > l) {

quickSort(arr, l, right);

}


}


}


文章评论

Top