快速排序,给定一个输入的子数组a[p:r]，主要分为3步：
- 分解（partition）: 以a[p]为基本元素，将数组a分为三段，a[p:q-1]，a[q], a[q+1,r] 。其中第一段里的每一个元素都 <= a[q] , 第三段里的每一个元素都
>= a[q]。
2. 递归 (recursion) 。通过递归调用快排算法，分别对a[p:q-1] , a[q+1,r] 进行排序。
3.合并(merge): 由于对a[p:q-1] 和 a[q+1,r]进行排序是就地进行的。所以，在这两段都排好序之后，不需要执行任何操作，数组a 就已经排好序了。
基于以上的思想，快排的伪代码如下：
void quickSort(int[] a,int p,int r){
if(p<r){
q = partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}
对含有n个元素的数组a[0,n-1]进行快速排序，只要调用 quickSort(a,0,n-1)即可。
上述函数中的partition函数是快排的关键，以一个确定的基准元素a[p]对子数组a[p:r]进行划分。该函数返回下标q.
代码：
public int partition(int[] a, int p , int r){
int i = p;
int j = r+1;
int x = a[p];
// 将 < x 的元素交换到左边
// 将 > x 的元素交换到右边
while(true){
while( a[ ++ i] < x && i < r);
while( a[ -- j] > x);
if(i>=j) break;
Swap(a[i],a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}
经过测试之后，可以通过运行的代码：以后可以按照以上的模版写
package Leet_Code;
/**
* @program: Leetcode
* @description:
* @create: 2019-03-07 13:44
**/
public class QuickSort {
public static void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static int partition(int[] a,int p, int r){
// 返回partition所在的下标，该下标之前的元素小于等于，之后的大于等于
int i = p;
int j = r+1;
int x = a[p];
while(true){
while ( a[++i] < x && i<r); // 遇到等于号交换
while ( a[--j] > x);
if (i>=j) break;
swap(a,i,j);
}
// 最终碰到一起，或者 j 在 i前边
a[p] = a[j];
a[j] = x;
return j;
}
public static void quickSort(int[] a, int p , int r){
if (p<r){
int q = partition(a,p,r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}
public static void printArray(int[] nums){
for(int n:nums){
System.out.print(n + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] test = {7,9,0,3,5};
int[] test1 = {3,3,4,9,6,1,0};
int[] test2 = {2,2,2,2,2};
quickSort(test,0,test.length-1);
quickSort(test1,0,test1.length-1);
quickSort(test1,0,test2.length-1);
printArray(test);
printArray(test1);
printArray(test2);
}
}
算法分析：
对于输入的序列a[p:r]. Partition 的计算时间显然为O(r-p-1)
快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。
由于Partition的计算时间为O(n),所以，如果Partition 的每一步划分都出现这种不对称划分，则其计算时间复杂度T(n)满足
{ O(1) n<=1
T(n) = {
{ T(n-1) + O(n) n>1
解此递归方程可得T(n) = O(n^2)
在最好的情况下，每次划分所得的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，此时
{ O(1) n<=1
T(n) = {
{ T(n/2) + O(n) n>1
其解为T(n) = O(nlogn)。
可以证明，快排的平均的复杂度也是O(nlogn)