冒泡排序的优化和鸡尾酒排序

发表于 | 分类于 | 浏览 次

冒泡排序的优化有设置哨兵来表示当前整个数组已经有序，以及设置有序区间，下一次只对有序区间进行排序（尚未完全理解）．

详情可见

鸡尾酒排序

鸡尾酒排序算法适用于大部分元素已经有序的情况．它能够在特定条件下，减少排序的回合数；但是缺点是代码量几乎扩大了一倍．

鸡尾酒排序

未进行优化的鸡尾酒排序

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
void clockTailSort(vector<int> &nums) {
    // 未进行优化的鸡尾酒排序
    int tmp = 0;
    for (int i = 0; i < nums.size() / 2 - 1; ++i) {
        // 有序标记，每一轮的初始值是true
        bool isSorted = true;

        // 奇数轮:从做向右比较和交换
        // 奇数轮：区间内最大的数会被冒泡到最右
        for (int j = i; j < nums.size() - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                
            	// 有元素交换，所以，不是有序，标记变为false
            	isSorted = false;
            }
        }

        if (isSorted) {
            break;
        }

        isSorted = true;        // 8 1 2 3 4

        // 偶数轮，从右向左比较和交换
        // 偶数轮，最小的数会被冒泡到最左边
        for (int j = nums.size() - i - 1; j > i; j--) {
            if (nums[j] < nums[j - 1]) {
                tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;

                isSorted = false;
            }
        }

        if (isSorted) {
            break;
        }
    }
}

进行优化的鸡尾酒排序
优化方法：