基本思想:
- 先从数列中取出一个数作为基准数
- 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
- 再对左右区间重复第二步,直到各区间只有一个数
快速排序=挖坑填数+分治法
实例:
数组a[]如下,取第一个数作为基准点
初始时,i=0; j=9; key=a[i]=72
因为已经将a[0]保存到key种,可以理解为在a[0]上挖了一个坑,可以将其他数据填进来。
从j开始,从后往前找一个小于或者等于key的数。当j=8时,满足条件,将a[8]挖出,在填到上一个坑a[0]中。a[0]=a[8];i++;这样a[0]这个坑就解决了。但又有了一个新坑a[8]。这次从i开始从前往后找一个大于或者等于key的数,当i=3,满足条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;
数组变为:
红色数字为移动后的数值,红色为新产生的坑
此时,i=3, j=7, key=72
在重复以上步骤,先从后往前,在从前往后
从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;
从i开始向后找,当i=5时,由于i==j退出。
此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将key填入a[5]。
此时数组变为:
蓝色数字为第二次改动后的数值
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
递归和非递归实现代码如下:
import java.util.Arrays;
import java.util.Stack;
public class Quick {
//找基准点
public static int partition(int []arr,int start,int end) {
int key=arr[start];
while (start<end) {
//开始从后往前找
while (arr[end]>=key && end>start) {
end--;
}
arr[start]=arr[end];//从后往前找到小于key的值
//开始从前往后找
while (arr[start]<=key && start<end) {
start++;
}
arr[end]=arr[start];//从前往后找,找到一个大于key的数
}
arr[start]=key;
return start;
}
//递归实现
public static void quick(int arr[],int start,int end) {
if (start<end) {
int index=partition(arr, start, end);
quick(arr, start, index-1);
quick(arr, index+1, end);
}
}
//非递归实现
public static void non_quick(int[] arr,int start,int end) {
Stack<Integer> stack=new Stack<>();
if(start<end) {
stack.push(end);
stack.push(start);
while (!stack.isEmpty()) {
int left=stack.pop();
int right=stack.pop();
int index=partition(arr, left, right);
if (left<index-1) {
stack.push(index-1);
stack.push(left);
}
if (right>index+1) {
stack.push(right);
stack.push(index+1);
}
}
}
}
public static void main(String[] args) {
int[] a1= {9,5,3,7,6,1,4,2,0,5,11,12};
int[] a= {9,5,3,7,6,1,4,2,0,5,11,12};
int start=0;
int end=a1.length-1;
quick(a1, start, end);
System.out.println(Arrays.toString(a1));
non_quick(a, start, end);
System.out.println(Arrays.toString(a));
}
}
时间复杂度:
最坏时O(n^2)
最好为O(nlogn)
空间复杂度:
若每次划分均匀,复杂度为O(logn)
最坏为:O(n)