当前位置: 代码迷 >> 综合 >> 快速排序及优化总结
  详细解决方案

快速排序及优化总结

热度:83   发布时间:2024-01-17 00:19:45.0

快速排序时间复杂度:  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.与基准值相等的值不再递归



  相关解决方案