排序算法快速排序

快速排序（Quick Sort）
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小， 则可分别对这部分记录继续进行排序，以达到整个序列有序的目的

最好情况o(logn)

最坏情况o(n²)

排序稳定，但需要额外的辅助空间

Paste_Image.png

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;
}```