1、快速排序
quicksort：是对冒泡排序算法的改进，采用“分治法”，能实现对数据的快速排序；步骤：
1、取基准：从数组中找一个基准值，这个基准值可随机取，一般就取最中间那个值；2、交换：将小于基准的值放在基准的左边，将大于基准的值放在基准的右边；3、递归：对左右两边的部分重复1-2步骤;复杂度：O(N*logN)；稳定性：不稳定。
2、Java代码
package Algorithm.Sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author yhx
* @date 2020/10/05
*/
public class QuickSort {
private static final int NUM = 80000;
public static void main(String[] args) {
// 定义待排序数组
int[] arr1 = {-9, 78, 0, 23, 999, -57};
int[] arr2 = new int[NUM];
for (int i = 0; i < NUM; i++) {
// .random()用于产生一个0到1的随机小数
arr2[i] = (int) ((Math.random() * 2 - 1) * NUM);
}
System.out.println("快速排序简单测试：");
Quick quick = new Quick();
quick.quickSort(arr1, 0, arr1.length - 1);
System.out.println("arr1[] = " + Arrays.toString(arr1));
System.out.println();
System.out.println("快速排序时间效率测试：");
// 时间标记精确到毫秒
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
// Date()函数用于标记时间
Date date1 = new Date();
String date1Str = simpleDateFormat.format(date1);
System.out.println("arr2[]排序前的时间是：" + date1Str);
quick.quickSort(arr2, 0, arr2.length - 1);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("arr2[]排序后的时间是：" + date2Str);
//System.out.println("arr2[]快速排序后的结果为：" + Arrays.toString(arr2));
}
}
class Quick {
/**
* 快速排序算法
*
* @param arr 待排序数组
* @param left 数组的左边界
* @param right 数组的右边界
*/
public void quickSort(int[] arr, int left, int right) {
int l = left;
int r = right;
// pivot：数组中间的那个值
int pivot = arr[(left + right) / 2];
// 临时变量，用于交换
int temp;
while (l < r) {
// 在pivot的左边一直找，找到大于等于pivot值才退出
while (arr[l] < pivot) {
l++;
}
// 在pivot的右边一直找，找到小于等于pivot值才退出
while (arr[r] > pivot) {
r--;
}
// 如果l>=r，说明中轴pivot左右两边的值，已经按规矩排放：小于等于pivot的全放在pivot的左边，大于等于pivot的全放在pivot的右边
if (l >= r) {
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果交换后，arr[l] 等于基准pivot，右索引r就减1，否则会陷入死循环
if(arr[l] == pivot){
r--;
}
// 与上同理
if(arr[r] == pivot){
l++;
}
}
// 如果l == r，必须l++，r--，否则会出现栈溢出
if (l == r) {
l++;
r--;
}
// 向左递归
if (left < r) {
quickSort(arr, left, r);
}
// 向右递归
if (right > l) {
quickSort(arr, l, right);
}
}
}
3、运行结果
快速排序简单测试：
arr1[] = [-57, -9, 0, 23, 78, 999]
快速排序时间效率测试：
arr2[]排序前的时间是：2020-10-05 11:52:11:035
arr2[]排序后的时间是：2020-10-05 11:52:11:060
