快速排序

快排思想

1. 从数列中挑出一个元素，称为"基准"（pivot），

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就就将原来的数组分为了两个部分，注意：基准不一定再正中间！这个称为分区（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，都会确定一个元素的位置。

快排的时间复杂度

对于长度为n的数组，快排循环一次，确定一个元素的位置。并将数组分为长度分别为I1和I2的子数组。

T(n)表示长度为n的数组快排所需的时间复杂度，D(n)=n-1是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分 I1 和 I2。由递归出以下三种时间复杂度：

1.最好时间复杂度：

• 就是快排每次划分将数组划分成两个等长子数组I1=I2

设 n 为待排序数组中的元素个数， T(n) 为算法需要的时间复杂度，递归得：
$$T(n)=\{\begin{array}{ll}D(1),& n\le 1\\ D(n)+T(I1)+T(I2),& n>1\end{array}$$
所以
$$\begin{array}{rl}T(n)& =D(n)+T(I1)+T(I2)\\ & =D(n)+D(\frac{n}{2})+D(\frac{n}{2})+....\\ & =n-1+2(\frac{n}{2}-1)+2^2(\frac{n}{2^2}-1)+...+2^k(\frac{n}{2^k}-1)\\ & =n-1+n-2+n-2^2+...n-2^k\\ & \because n=2^k\\ & \therefore k=lo{g}_2^n\\ & \therefore T(n)=lo{g}_2^n-2n+1\end{array}$$

• 第二种理解：循环一次将数组分为两个子数组，快排结束的条件是所有子数组的元素个数为1。所以确定数组n个元素的位置，每次循环子数组个数为1，2，2²…2^k=n，每次循环的时间复杂度乘以子数组隔宿即可，也就是
  $$\begin{array}{rl}T(n)& =1(n-1)+2(\frac{n}{2}-1)+2^2(\frac{n}{2^2}-1)+...+2^k(\frac{n}{2^k}-1)\\ & =n-1+n-2+n-2^2+...n-2^k\\ & \because n=2^k\\ & \therefore k=lo{g}_2^n\\ & \therefore T(n)=lo{g}_2^n-2n+1\end{array}$$

2.最坏时间复杂度

• 就是快排每次划分将数组划分成的两个子数组长度为I1=0，I2=n-1

  设 n 为待排序数组中的元素个数， T(n) 为算法需要的时间复杂度，递归得：
  $$T(n)=\{\begin{array}{ll}D(1),& n\le 1\\ D(n)+T(0)+T(n-1),& n>1\end{array}$$
  所以
  $$\begin{array}{rl}T(n)& =D(n)+T(n-1)\\ & =D(n)+D(n-1)+T(n-2)\\ & =(n-1)+(n-2)+(n-3)+....+(n-(n-1))\\ & =(n-1)+(n-2)+...+0\\ & =\frac{n(n-1)}{2}\\ & =O(n^2)\end{array}$$

• 第二中理解：最坏时间复杂度其实就是已经排好了的数组，再次快排，子数组长度为(n-1)，(n-2)，…，0，时间复杂度就是本身遍历的长度，相加即为快排时间复杂度：
  $$\begin{array}{rl}T(n)& =(n-1)+(n-2)+(n-3)+....+(n-(n-1))\\ & =(n-1)+(n-2)+...+0\\ & =\frac{n(n-1)}{2}\\ & =O(n^2)\end{array}$$

3.平均时间复杂度

• 就是每次划分将数组划分成的两个子数组的长度不确定，都是等可能，求时间复杂度就是算个平均值如下：

  $$\{\begin{array}{ll}& I1=0，I2=n-1\\ & I1=1，I2=n-2\\ & ....\\ & I1=n-1，I2=0\end{array}$$

  所以求解如下，思路就是求平均：
  $$\begin{array}{rl}T(n)& =D(n)+\frac{1}{n}\sum _{i=0}^{n-1}[T(i)+T(n-1-i)]\\ & =D(n)+\frac{2}{n}\sum _{i=0}^{n-1}T(i)...(1)式\\ & \therefore T(n-1)=D(n-1)+\frac{2}{n}\sum _{i=0}^{n-2}T(i)...(2)式\\ & \therefore n\ast (1)-(n-1)\ast (2)得:\\ & nT(n)-(n-1)T(n-1)=nD(n)+2\sum _{i=0}^{n-1}T(i)-(n-1)D(n-1)-2\sum _{i=0}^{n-2}T(i)\\ & 整理得:\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2(n-1)}{n(n-1)}\\ & 令B_n=\frac{T(n)}{n+1}，得\end{array}$$
  

  然后求B(n)反代求出T(n)，求解过程很复杂不在此描述，最终时间复杂度为
  $$O(nlog{2}^n)$$

综上:快速排序最好时间复杂度为 O(nlog₂ⁿ) ,最坏时间复杂度为 O(n²) ,平均时间复杂度为 O(nlog₂ⁿ)

快速排序的一些改进方案：

1. 将快速排序的递归执行改为非递归执行

2. 当问题规模 n 较小时 (n≤16) ,采用直接插入排序求解

3. 每次选取 prior 前将数组打乱

4. 每次选取
   $$\frac{E[first]+E[Last]}{2}$$
   或
   $$\frac{E[first]+E[last]+E[(first+last)/2]}{3}$$
   作为 prior

快排的Java实现：

/**
 * 快速排序
 * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
 * 则分别对这两部分继续进行排序，直到整个序列有序。
 * @author Answer
 * 2022.8.11
 */
public class QuickSort 
{	
    //交换数据函数包装
	private static void swap(int[] data, int i, int j) 
    {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

    //函数主体
	private static void subSort(int[] data, int start, int end) 
    {
		if (start < end) 
        {
			int base = data[start]; 
			int low = start;
			int high = end + 1;
			while (true) 
            {
				while (low < end && data[++low] - base <= 0);//low < end，是用于迭代时防止超出范围的限制
				while (high > start && data[--high] - base >= 0);
				if (low < high) 
                {
					swap(data, low, high);
				} 
                else 
                {
					break;
				}
			}
			swap(data, start, high);
			
			subSort(data, start, high - 1);//递归调用
			subSort(data, high + 1, end);
		}
	}
	public static void quickSort(int[] data)
    {
		subSort(data,0,data.length-1);
	}
	
	public static void main(String[] args) 
    {
		int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
		System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
	}
}

• 快排分内外层两循环，其中两个内层循环做的是将将当前小于pivot的元素分到一边（结束时是以大于pivot的元素head结束），将当前大于pivot的元素分到另一边（结束时是以小于pivot的元素tail结束），然后交换head和tail，再次进入外层循环。通过两层循环将大于和小于pivot的元素进行分组，再对子数据进行iteration。
• high=end+1;这个设定很微妙！大大简化代码量！函数体中要排序的下标范围是1~array.length-1，但设置的头是0，尾部是array.length。这样的设定决定函数在对pivot进行比对的时候，需要先自增自减再比对，当然也可以设定头是1，尾部是array.length-1。这样就需要先比较，再根据判断结果决定是否需要对下标进行移动，因此再内层循环中需添加if语句，代码冗杂。不如第一种精巧的设定
• 迭代注意：再函数题内部用于迭代函数的参数一般不写具体数值，否则无论迭代多少次，参数均不变，与迭代的目的向背。而应该写的是函数内部定义的变量，这样函数执行一次参数都发生变化，才符合我们的预期。