选择和冒泡排序优化思路

Oct 8, 2019 6 min read 研究

本篇针对两种最基本的排序（冒泡、选择）来讲优化思路。越是简单的东西反而可能存在你越想不到的优化点。但是在开始之前，先给不了解的人讲一个设计原则的问题，我们在设计排序接口的时候，最为常见的有
void sort(type arr[], int len)
也许你也见过
void sort(iter beg, iter end)
这时候问题就来了，很多人会错误地把end认为是最后一个元素，其实不然，这两接口可以相互转换，例如我们可以写 sort(arr, arr + len) ，这样写很自然对不对，但如果你认为end是最后一个元素，那你就不得不改成 sort(arr, arr + len - 1) 。事实上，这类的接口我们需要一个统一的原则，就是左闭右开区间原则，即beg就是首个元素，而end是最后一个元素+1，即end是作为结束标志，不应该把end算在范围内。接下来下面所有的接口写法，都是以
void sort(iter beg, iter end)
这种方式写的，至于这样写有什么好处，接下来我们就看示例。

选择排序

基本实现

我们先来看选择排序，因为它编写简单，而且最不容易出错，我们来看以下两种不同的接口写法，我们定义要排序的数据类型名字是sort_element_t，定义交换函数

void sort_element_swap(sort_element_t *x, sort_element_t *y)
{
    sort_element_t t = *x;
    *x = *y;
    *y = t;
}

具体实现

void select_sort(sort_element_t arr[], size_t len) //方式1
{
    for (size_t i = 0; i < len; ++i)
    {
        size_t head = i;
        for (size_t j = i + 1; j < len; ++j)
        {
            if (arr[j] < arr[head])
                head = j;
        }
        sort_element_swap(arr + i, arr + head);
    }
}

void select_sort(sort_element_t * beg, sort_element_t * end) //方式2
{
    for (; beg < end; ++beg)
    {
        sort_element_t* head = beg;
        for (sort_element_t* i = beg + 1; i < end; ++i)
        {
            if (*i < *head)
                head = i;
        }
        sort_element_swap(beg, head);
    }
}

就这么一眼看过去，看起来还真差不多，这样，我们再细分一下，选择排序的中间那步，其实就是找一个最小的元素，我们单独提取成一个独立函数再来看看

//方式1
size_t find_min(sort_element_t arr[], size_t beg, size_t len)
{
    size_t head = beg;
    for (size_t j = beg + 1; j < len; ++j)
    {
        if (arr[j] < arr[head])
            head = j;
    }
    return head;
}

void select_sort(sort_element_t arr[], size_t len)
{
    for (size_t i = 0; i < len; ++i)
    {
        sort_element_swap(arr + i, arr + find_min(arr, i, len));
    }
}

//方式2
sort_element_t* find_min(sort_element_t * beg, sort_element_t * end)
{
    sort_element_t* head = beg;
    for (sort_element_t* i = beg + 1; i < end; ++i)
    {
        if (*i < *head)
            head = i;
    }
    return head;
}

void select_sort(sort_element_t * beg, sort_element_t * end)
{
    for (; beg < end; ++beg)
    {
        sort_element_swap(beg, find_min(beg, end));
    }
}

仔细观察一下，是不是第二种写法函数参数统一，而且参数数量少，而且也少了很多不必要的加法运算（像方法一需要写arr + i这类）。如果你说方法一的find_min参数也可以只写两个，写成find_min(sort_element_t arr[], size_t len)，那么你在调用的地方将不得不写成find_min(arr + i, len - i)，这种又加又减在遇到更复杂的情况的时候，更容易把你弄晕出Bug。总之结论是最好把参数写成两个指针（或两个迭代器）的形式，不建议使用数组加长度的形式，STL的接口也全使用迭代器的形式。

对于这个排序要注意的一点是，有人会写成类似下面的形式：

void select_sort(sort_element_t arr[], size_t len)
{
	for (size_t j = 0; j < len; ++j)
	{
		for (size_t i = j + 1; i < len; ++i)
		{
			if (arr[j] > arr[i])
			{
				sort_element_t t = arr[j];
				arr[j] = arr[i];
				arr[i] = t;
			}
		}
	}
}

以上这种叫做劣化版的选择排序，在大多数的情况下会比前一个方法慢，极端条件下甚至会慢1倍甚至更多

那说完劣化再讲优化，选择排序的时间复杂度是$O(n^2)$，而且运行时间与原来的排列完全无关。以上的选择排序总是选择小的，那大小一起选呢？能不能起到优化的作用？如果你单纯的多写一个find_max变成双向选择来做，在VS2005下是没有优化效果的，我测试过了。那应该怎么样呢？确实还是双向选择，不过具体实现稍有点不同。

优化1，双向选择

这里的实现是一个函数里同时把最大最小一起找，这样减少了一次遍历的过程，时间能减半之余，还有一个非常有用的优化，就是当你发现最大值等于最小值的时候能提前跳出

sort_element_t* find_min_max(
    sort_element_t * beg,
    sort_element_t * end,
    sort_element_t** head_max)
{
    sort_element_t* head = beg;
    *head_max = beg;
    for (sort_element_t* i = beg + 1; i < end; ++i)
    {
        if (*i < *head)
            head = i;
        else if (**head_max < *i)
            *head_max = i;
    }
    return head;
}

void double_select_sort(sort_element_t * beg, sort_element_t * end)
{
    while (end - beg > 1)
    {
        sort_element_t * head_max, * head = find_min_max(beg, end, &head_max);
        if (head_max != head)
        {
            if (head_max == beg)
                head_max = head;
            sort_element_swap(beg++, head);
            sort_element_swap(--end, head_max);
        }
        else
        {
            break;
        }
    }
}

与选择排序的运行时间比较如下，排序45000个int，编译环境是VS2015，用10组不同分布的数据，表格中的数字单位是毫秒，即排序用时

int 1 2 3 4 5 6 7 8 9 10 Avg
select2 0 1114 834 1113 1124 1124 1119 1124 1124 1141 981
select 2213 2238 2227 2229 2256 2242 2238 2241 2245 2260 2238

合理运用双向，效果也往往不错，但是千万要注意，环境不同会导致测试结果不相同，例如你换到mingw上使用-O3编译那么将会是select比select2快，所以上面数据只供参考，具体结果请自己做测试。

优化2，数据结构

选择排序的优化主要是在find_min上面，find_min的时间复杂度是$O(n)$，那如果我们通过一些数据结构的组织，例如二叉堆，那么找最大或最小值时间将变成$O(1)$，而维护这个数据结构的代价是$O(logn)$的话，总体时间复杂度将变为$O(nlogn)$，这比起选择排序的$O(n^2)$就是一个巨大的变化，具体内容在之后的 堆排序 篇具体讲解。

冒泡排序

基本实现

冒泡排序是我们课本必然介绍的一个排序，相对于选择排序，这种在编写的时候更容易出现逻辑错误，我们先来看典型的实现（双迭代器实现）

void bubble_sort(sort_element_t * beg, sort_element_t * end)
{
    for (; beg < end; --end)
    {
        for (sort_element_t * i = beg + 1; i < end; ++i)
        {
            if (*i < i[-1])
                sort_element_swap(i - 1, i);
        }
    }
}

冒泡排序这种写法，铁定的$O(n^2)$时间没跑，不过好在冒泡排序的优化方法也不少。

优化1，提前跳出

void bubble_sort(sort_element_t * beg, sort_element_t * end)
{
    for (; beg < end; --end)
    {
        int sorted = 1;
        for (sort_element_t * i = beg + 1; i < end; ++i)
        {
            if (*i < i[-1])
            {
                sort_element_swap(i - 1, i);
                sorted = 0;
            }
        }
        if (sorted)
            break;
    }
}

通过sorted变量记录某一轮是不是存在交换，如果没有交换则表明数据已经是有序的，可以提前退出循环。有这个优化对于已经有序的数据，冒泡排序将运行得特别快，即最优情况时间复杂度只有$O(n)$

优化2，鸡尾酒排序

前面的冒泡写法是单向冒泡，把最大值向最右边移，这回我们做成双向，一边把最大值右移，一边把最小值左移，不过这种方法有另一个命名，叫做鸡尾酒排序

void cocktail_sort(sort_element_t * beg, sort_element_t * end)
{
    while (beg < end)
    {
        int sorted = 1;
        for (sort_element_t * i = beg + 1; i < end; ++i)
        {
            if (*i < i[-1])
            {
                sort_element_swap(i - 1, i);
                sorted = 0;
            }
        }
        if (sorted)
            break;
        --end;

        sorted = 1;
        for (sort_element_t * i = end - 1; i > beg; --i)
        {
            if (*i < i[-1])
            {
                sort_element_swap(i - 1, i);
                sorted = 0;
            }
        }
        if (sorted)
            break;
        ++beg;
    }
}

那改成双向就真的有提升了吗？我们看实测，排序45000个int，用10组不同分布的数据，表格中的数字单位是毫秒，即排序用时

int 1 2 3 4 5 6 7 8 9 10 Avg
cocktail 0 0 1313 1502 1614 1674 671 1 2 836 761
bubble 0 0 1245 2286 2329 2332 871 1 4 1459 1052

其中第4组是乱序无重复数值的数据，最有代表性的一列。从中可以看到，cocktail比起bubble能节省30%的时间

让我们再脑洞大开，除了可以双向，还有一种对CPU执行有利的优化方式

优化3，奇偶排序

这种排序的排序方式见下表，假设有8个数，奇数轮比较(1,2), (3,4), (5,6), (7,8)，偶数轮比较(2,3), (4,5), (6,7)，如此循环，直到没有交换为止

轮次 1 2 3 4 5 6 7 8
0 8 7 6 5 4 3 2 1
1 7 8 5 6 3 4 1 2
2 7 5 8 3 6 1 4 2
3 5 7 3 8 1 6 2 4
4 5 3 7 1 8 2 6 4

具体实现代码如下

void odd_even_sort(sort_element_t * beg, sort_element_t * end)
{
    int sorted = 0, last_sorted = 0;
    while (sorted == 0)
    {
        last_sorted = sorted;
        sorted = 1;
        for (sort_element_t * i = beg + 1; i < end; i += 2)
        {
            if (*i < i[-1])
            {
                sort_element_swap(i - 1, i);
                sorted = 0;
            }
        }
        if (last_sorted && sorted)
            break;

        last_sorted = sorted;
        sorted = 1;
        for (sort_element_t * i = beg + 2; i < end; i += 2)
        {
            if (*i < i[-1])
            {
                sort_element_swap(i - 1, i);
                sorted = 0;
            }
        }
        if (last_sorted && sorted)
            break;
    }
}

让我们再脑洞大开，除了比较方向，好像我们有一个条件没有考虑上，就是冒泡排序总是相邻元素的比较，那么如果不相邻地比较呢？

优化4，梳排序

通过一开始设置较大的步长，让元素能较快移动，然后逐步减少步长，直到1变成普通的冒泡排序为止。这个方法的优点，就是快，相对前面的方法来说飞快。当然，最后一步你也可以选择不调用冒泡排序，而改调用cocktail_sort或odd_even_sort都可以，差别不明显。

void comb_sort(sort_element_t * beg, sort_element_t * end)
{
    const double shrink_factor = 0.8;
    ptrdiff_t gap = end - beg;
    while (gap > 1)
    {
        if (gap > 1)
        {
            gap = (ptrdiff_t)(gap * shrink_factor);
            if (gap == 10 || gap == 9)
                gap = 11;
        }
        for (sort_element_t * i = beg + gap; i < end; ++i)
        {
            if (*i < i[-gap])
                sort_element_swap(i, i - gap);
        }
    }
    bubble_sort(beg, end);
}

完整测试

在完整测试里你会发现一些和你想象中完全不一样的情况，可不要以为你的“优化”一定就是优化

VS2005下的运行时间比较（按Avg平均值排序）

int 1 2 3 4 5 6 7 8 9 10 Avg
combsort 0 0 1 3 3 1 1 0 1 2 1
odd_even 0 0 574 1315 1315 1222 557 0 3 878 586
cocktail 0 0 1313 1502 1614 1674 671 1 2 836 761
select2 0 1114 834 1113 1124 1124 1119 1124 1124 1141 981
bubble 0 0 1245 2286 2329 2332 871 1 4 1459 1052
select 2213 2238 2227 2229 2256 2242 2238 2241 2245 2260 2238

如果你只测试随机数据，那么排序应该是

combsort << select2 < odd_even < cocktail < select < bubble

在mingw64(gcc8)下使用-O3编译（最大优化）的运行时间比较

int 1 2 3 4 5 6 7 8 9 10 Avg
combsort 0 1 1 2 3 2 2 1 2 3 1
select 497 497 434 501 501 500 501 503 500 502 493
odd_even 0 0 564 1311 1264 1217 562 0 2 882 580
cocktail 0 0 1242 1515 1610 1677 669 0 3 837 755
select2 1 1114 837 1114 1114 1112 1114 1113 1112 1114 974
bubble 0 0 1247 2312 2332 2338 951 0 3 1455 1063

你可以发现，找最小值过程在mingw64下被特别照顾了一下，结果它比其它的明显要快，你可以从中得知，如果你想在mingw下写出运行得快的双向选择排序，如果你的想法是再写一个find_max函数，那对不起，这样是没有优化效果的。但这不是全部，还有让你更大跌眼镜的情况。

在mingw64(gcc8)下使用-O1编译（基本优化）的运行时间比较

int 1 2 3 4 5 6 7 8 9 10 Avg
combsort 0 0 0 3 3 1 1 0 2 2 1
select2 0 263 375 256 260 258 255 254 531 255 270
odd_even 0 0 597 1287 1256 1204 1368 1 3 780 649
cocktail 0 0 1244 1504 1594 1656 1081 1 3 815 789
bubble 0 0 1241 2091 2117 2115 685 0 3 1247 949
select 2233 2233 2232 2231 2232 2224 2229 2229 2225 2232 2230

现在双向选择不但最快，而且还比-O3下的快得多。老实说，会造成这种奇怪的结果，-O1比-O3还快的原因还真不要问我，找开发gcc/mingw的开发者。

最后还是忠告一句，千万不要在一个编译器某个编译参数上看到有优化效果，就以为是事实，优化的坑远比你想象的要来得深，并不是你以为优化了它就一定变快了，编译器和编译参数以及运行环境才是你的老大。

算法 排序 冒泡排序 选择排序 鸡尾酒排序 奇偶排序 梳排序 c c++
Avatar
抱抱熊

一个喜欢折腾和研究算法的大学生

Related

comments powered by Disqus