算法-快速排序

Posted on | In |

介绍

分析

基本思想:

通过一遍排序将需要排序的数据分成两部分，使其中一部分数据比另一部数据小，然后再分别对这两部分继续进行这种排序，按此规则继续，直到每个部分为空或者只含一个数时，整个排序结束。

算法描述:

  1. 从数列中挑出一个元素，称该元素为“基准”
  2. 扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准“大的元素排在基准后面
  3. 通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序
C实现
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
59
60
61
62
63
64
65
66
67
/**
 分治法拆分数组

 @param a 原数组
 @param left 左边
 @param right 右边
 @return 拆分点
 */
int patition(int a[], int left, int right)
{
    //基准元素
    int base = a[left];
    
    while (left < right) {
        while (left < right && a[right] > base) {
            --right;
        }
        a[left] = a[right];
        
        while (left < right && a[left] < base) {
            ++left;
        }
        a[right] = a[left];
    }
    a[left] = base;
    
    return left;
}

/**
 快速排序

 @param a 原数组
 @param left 左边
 @param right 右边
 */
void quicklySort(int a[], int left, int right)
{
    if (left < right) {
        int i = patition(a, left, right);
        quicklySort(a, left, i - 1);
        quicklySort(a, i + 1, right);
    }
}


/**
 测试快速排序
 */
void testQuicklySort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("快速排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    quicklySort(arr, 0, len - 1);
    
    printf("\n快速排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
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
class QuicklySort {

    /// 分治法拆分数组
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - left: 左边
    ///   - right: 右边
    /// - Returns: 拆分点
    func patition(a: inout [Int], left: Int, right: Int) -> Int {
        let base = a[left]
        var i = left
        var j = right
        while i < j {
            while i < j && a[j] > base {
                j -= 1
            }
            a[i] = a[j]
            
            while i < j && a[i] < base {
                i += 1
            }
            a[j] = a[i]
        }
        a[i] = base;
        
        return i
    }
    
    /// 快速排序
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - left: 左边
    ///   - right: 右边
    func quicklySort(a: inout [Int], left: Int, right: Int) {
        if left < right {
            let i = patition(a: &a, left: left, right: right)
            quicklySort(a: &a, left: left, right: i - 1)
            quicklySort(a: &a, left: i + 1, right: right)
        }
    }
    
    
    /// 测试
    func testQuicklySort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("归并排序前:\(arr)", separator: " ")
        quicklySort(a: &arr, left: 0, right: arr.count - 1)
        print("归并排序后:\(arr)", separator: " ")
    }
}

总结

时间复杂度:

  • 最差O(n^2)

  • 最优O(nlogn)

  • 平均O(nlogn)

空间复杂度:

  • O(nlogn)

稳定性:

  • 不稳定

当数组元素基本有序时，快速排序将没有任何优势，基本退化为冒泡排序，可在选取基准元素时选取中间值进行优化。