基础算法之快速排序

今天又是翻了一下「算法导论」中的「快速排序」，在记忆中，似乎记得这是实际应用中使用的最多的排序算法了，尽管它并不是一个很稳当的排序算法。「快速排序」的平均性能看起来是非常好的，但是它不稳定，因而坏起来的话，那也是非常糟糕的。对于「快速排序」来说，我们只能对它的期望时间复杂度做出估计：Ο(nlgn)。

「算法导论」中给出了「快速排序」以下的伪码实现，说实话，我并不是很喜欢这种写法，因为有时候这种方式很容易让人看晕了，还不如实际代码来的直接明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r-1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

QUICKSORT(A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q - 1)
    QUICKSORT(A, q + 1, r)

接下来就是用Java实现了这种排序算法，当然，形式有些不同，或者说是有些优化或者简化吧，这种形式似乎是在严奶奶那本书中有记载。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.test;

/**
 * @author crazylion
 *
 */
public class SortTest
{
    public void quickSort(int[] a, int left, int right)
    {
        if (left < right)
        {
            int key = a[left];
            int low = left;
            int high = right;
            
            while(low < high)
            {
                while(low < high && a[high] > key)
                {
                    high--;
                }
                a[low] = a[high];
                
                while(low < high && a[low] < key)
                {
                    low++;
                }
                a[high] = a[low];
            }
            
            a[low] = key;
            
            quickSort(a, left, low - 1);
            quickSort(a, low + 1, right);
        }
    }
    
    public static void main(String[] args)
    {
        int[] temp = new int[11];
        for(int i = 1; i <= 10; i++)
        {
            temp[i] = (int) (Math.random()*1000);
            System.out.println("==>" + temp[i]);
        }
        
        System.out.println("================================");
        
        SortTest sortTest = new SortTest();
        sortTest.quickSort(temp, 1, 10);
                
        for(int i = 1; i <= 10; i++)
        {
            System.out.println("-->" + temp[i]);
        }
    }
}

代码是经过实际运行的，效果还是不错滴！