请你说一说快速排序，并手写代码

Answer 1

参考回答：

1、快速排序的基本思想：

快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2、快速排序的三个步骤：

(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）

(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大

(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。

3、选择基准的方式：

对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列三种选择基准的方法：

方法(1)：固定位置

思想：取序列的第一个或最后一个元素作为基准

方法(2)：随机选取基准

引入的原因：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴

思想：取待排序列中任意一个元素作为基准

方法(3)：三数取中（median-of-three）

引入的原因：虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴

分析：最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数。

固定位置示例程序：

public class QuickSort {
public static void main(String[] args) {
int[] a = {1, 2, 4, 5, 7, 4, 5 ,3 ,9 ,0};
System.out.println(Arrays.toString(a));
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a) {
if(a.length>0) {
quickSort(a, 0 , a.length-1);
}
}
private static void quickSort(int[] a, int low, int high) {
	//1,找到递归算法的出口

    if( low > high) {
    return;
    }
//2, 存
int i = low;
int j = high;
//3,key
int key = a[ low ];
//4，完成一趟排序

while( i< j) {

//4.1 ，从右往左找到第一个小于key的数
while(i<j && a[j] > key){
j--;
}
// 4.2 从左往右找到第一个大于key的数

    while( i<j && a[i] <= key) {
    i++;
    }
//4.3 交换

    if(i<j) {
    int p = a[i];
    a[i] = a[j];
    a[j] = p;
    }
    }
// 4.4，调整key的位置

int p = a[i];

a[i] = a[low];

a[low] = p;

//5, 对key左边的数快排

quickSort(a, low, i-1 );

//6, 对key右边的数快排

quickSort(a, i+1, high);

}

}

 

 

四种优化方式：

优化1：当待排序序列的长度分割到一定大小后，使用插入排序

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排

优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割

优化3：优化递归操作

快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化

优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

优化4：使用并行或多线程处理子序列