快速排序（Quick Sort）
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小， 则可分别对这部分记录继续进行排序，以达到整个序列有序的目的
最好情况o(logn)
最坏情况o(n²)
排序稳定，但需要额外的辅助空间
static void quickSort(int[] array, int low, int high) {
if (array != null && array.length > 0) {
if (low >= high)
return;
// 找出中间索引
int pivot = partition(array, low, high);
System.out.println("low right:" + low + " " + high);
System.out.println(pivot + "array result:" + Arrays.toString(array));
// 对低子表递归排序
quickSort(array, low, pivot - 1);
// 对高子表递归排序
quickSort(array, pivot + 1, high);
}
}```
/**
* 交换顺序表中子表的记录，使枢轴记录到位，并返回其所在位置
* 此时在他之前（后）的记录均不打（小）于它
*/
static int partition(int[] array, int low, int height) {
if (array != null && array.length > 0) {
int pivotkey;
pivotkey = array[low];
while (low < height) {
while (low < height && array[height] >= pivotkey) {
height--;
}
swap(array, low, height);//将比根轴记录小的记录交换到低端
while (low < height && array[low] <= pivotkey) {
low++;
}
swap(array, low, height);//将比轴记录大的记录交换到高端
}
return low;
}
return 0;
}
/**
* 将数组的2个位置交换
*/
static void swap(int[] array, int i, int j) {
if (array != null && array.length > 0) {
if (i >= 0 && j >= 0 && i <= array.length && j <= array.length) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}```
快速排序优化
递归对性能有一定的影响。栈的大小事很有限的，每次递归调用都会消耗一定的栈空间， 函数的参数越多，每次递归消耗的空间也越多。实现尾递归优化。
static void quickSort2(int[] array, int low, int high) {
if (array != null && array.length > 0) {
int pivot;
while (low < high) {
// 找出中间索引
pivot = partition2(array, low, high);
System.out.println("low right:" + low + " " + high);
System.out.println(pivot + "array result:" + Arrays.toString(array));
// 对低子表递归排序
quickSort2(array, low, pivot - 1);
// 尾递归
low = pivot + 1;
}
}
}```
优化选取枢轴（三数取中）
取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数
static int partition2(int[] array, int low, int height) {
if (array != null && array.length > 0) {
int pivotkey;
int m=low+(height-low)/2;//计算数组中间的元素下标
if(array[low]>array[height]){
swap(array,low,height);//保证左端最小
}
if(array[m]>array[height]){
swap(array,m,height);//保证中间最小
}
if(array[m]>array[low]){
swap(array,m,low);//保证中间最小
}
pivotkey = array[low];
while (low < height) {
while (low < height && array[height] >= pivotkey) {
height--;
}
swap(array, low, height);//将比根轴记录小的记录交换到低端
while (low < height && array[low] <= pivotkey) {
low++;
}
swap(array, low, height);//将比轴记录大的记录交换到高端
}
return low;
}
return 0;
}```
