排序算法学习之快速排序

时间:2021-11-02 10:22:08

1.快速排序的优点:实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多,它是原地排序、且将长度为N的数组排序所需的时间和NlogN成正比。另外,快速排序的内循环比大多数排序算法都要短小,这意味着它无论是在理论上还是在实际中饭都要更快。

2.快速排序的缺点:它的主要缺点是非常脆弱,在实现时要非常小心才能避免低劣的性能。、

3.将长度为N的无重复数组排序,快速排序平均需要~2NlnN次比较(以及1/6的交换)。

4.快速排序最多需要约N2次比较,但随机打乱数组能够预防这种情况。 

5.快速排序的改进:

在排序小数组时,应该将快速排序切换成插入排序。

使用子数组的一小部分元素的中位数来切分数组。将取样大小设为三最为合适。

在有大量重复元素的情况下,一个简单的想法是将数组切分为三部分,分别对应小于、等于和大于切分元素的数组元素。三向切分。

6.对于只有若干不同主键的随机数组,归并排序的时间复杂度是线性对数的,而三向切分快速排序则是线性的。

7.基本排序算法:

 1 public class Quick {
 2     public  static void sort(int[] a)
 3     {
 4         StdRandom.shuffle(a);
 5         sort(a, 0, a.length - 1);
 6     }
 7     
 8     private static void sort(int[] a, int lo, int hi)
 9     {
10         if (hi <= lo) return;//这条语句可以换成: if (hi <= lo + M) {Insertion.sort(a, lo, hi); return;}来换成插入排序以排序数组元素较少的小数组。 
11         int j = partition(a, lo, hi);
12         sort(a, lo, j - 1);
13         sort(a, j + 1, hi);
14     }
15     
16     private static int partition(int[] a, int lo, int hi)
17     {
18         int i = lo,j = hi + 1;
19         int v = a[lo];
20         while(true)
21         {
22             while(a[++i] < v) if (i == hi) break;
23             while(v < a[++j]) if (j == lo) break;
24             if (i >= j) break;
25             exch (a, i, j);
26         }
27         exch(a, lo, j);
28         return j;
29     }
30     
31     private static void exch(int[] a, int i, int j)
32     {
33         int temp = a[i];
34         a[i] = a[j];
35         a[j] = temp;
36     }
37 }

8. 三向切分的快速排序:

 1 //三向切分的快速排序
 2 class Quick3way
 3 {
 4     private static void sort(int[] a, int lo, int hi)
 5     {
 6         if (hi <= lo) return;
 7         int lt = lo, i = lo + 1, gt = hi;
 8         int v = a[lo];
 9         while(i <= gt)
10         {
11             if (a[i] < v) exch(a, lt++, i++);
12             else if (a[i] > v) exch(a, i, gt--);
13             else  i++;
14         }
15         sort(a, lo, lt - 1);
16         sort(a, gt + 1, hi);
17     } 
18     
19     private static void exch(int[] a, int i, int j)
20     {
21         int temp = a[i];
22         a[i] = a[j];
23         a[j] = temp;
24     }
25 }