快速排序时间复杂度: nlg(n) ~ O(n2),注意不是nln(n). 平均时间复杂度为O(nlogn), 空间复杂度O(log2n)~O(n), 除归并排序O(n)以外, 其余常用算法空间复杂度多数为O(1). 它是不稳定的排序算法. 若要求空间复杂度为O(1),选择堆排序, 否则可选择快速排序和归并排序.
快速排序原理: 从数组arr[]中选某个数为基准, 比它大的放右边, 小的放左边, 最后得到基准的索引m, 递归arr(0, m-1) 和arr(m+1, len-1)两个数组, 直到长度为1
java实现:
public class QuickSort {public static void main(String[] args) {int a[] = {1,23,21,1,45,5,4,7,35,2,65,5,4,3,94,6,4,85,65,6,51,3,49,97,64,64,3,9,19,78,9,4,24,63,4,37,94,1,94,3};sort(a, 0, a.length-1);for (int i = 0; i < a.length; i++) {System.out.println(a[i]);}}public static void sort(int[] a, int left, int right) { //递归if (left >= right) {return;} else {int m = partition(a, left, right); //分组sort(a, 0, m - 1);sort(a, m+1, right);}}public static int partition(int[] a, int left, int right) { //排序// 固定的分割方式// 选择最后一个最为基准int temp = a[right];while (left < right) {// 从前半部分向后扫描while (a[left] <= temp && left < right) {left++;}//直到大于temp的 a[left] , 将left 值 给 right, a[left]没有值,等待接受right,比temp小的值.a[right] = a[left];// 从后半部分向前扫描 , 此时, a[right] > temp, a[right]已经不是原来的a[right].while (a[right] >= temp && right > left) {right--;}//直到小于temp的 a[right] , 将right 值 给left, a[right] 没有值,等待接受比temp大的值.a[left] = a[right];}//此时,left = right, a[left] = a[right], a[right] = a[left] = temp;//a[right] 等待赋值//基准值temp的值给a[right];基准值归位.左边是比temp小的值,右边是比temp大的值a[right] = temp;//返回分割位的索引return right;}
}
算法的问题: 在处理有序数组,尤其是重复数组的时候速度会降到冒泡排序O(n2)的程度, 随机数选取不当也使得速度降低.
算法的优化:
1. 三数取中,作为基准值
2. 当长度小于某个值, 改用插入排序
3. 与基准值相等的数不再递归.
4. 优化递归操作
5. 减少不必要的交换
1.三数取中:
public static void pivotkey(int[] a, int left, int right) {//取中间值int m = left + (right - left)/2;//left最小if (a[left] > a[m]) {swap(a, left, m);}//left最小if (a[left] > a[right]) {swap(a, left, right);}//right不是最大if (a[left] > a[m]) {
swap(a, left, m);
}}
在partition中首先运行pivotkey, 此时a[right] 就是需要的基准值, 左边从left+1开始比较
2.写一段插入排序:
public static void insertSort(int[] a) {int len = a.length;for (int i = 1; i < len; i++) {int temp = a[i];int j = i - 1;while(a[j] > temp && j > -1) {a[j + 1] = a[j];j--;} a[j + 1] = temp;}}
当长度小于8时改用插入排序:
public static void sort(int[] a, int left, int right) {if (left >= right) {return;} else if (a.length < 8) {insertSort(a);return;} else {int m = partition(a, left, right);sort(a, 0, m - 1);sort(a, m+1, right);}}
3.与基准值相等的值不再递归