手写冒泡排序和选择排序算法

关注

发布于: 20 小时前

今天给大家介绍另外 2 种排序算法：冒泡排序和选择排序。它们的思路有些相似，因此一并介绍，并且给出源码实现。

一、冒泡排序

自然界中，经常会看到一个气泡从水底冒出，最开始很小，浮向水面的过程中会变得越来越大，到达水面时最大。

冒泡排序算法，就是从上面的场景中得到的灵感启发，其想法如下：

要对一个未被排序的数组，实现将元素从小到大的顺序进行排序，那么可以从第一个元素开始，与下一个元素进行比较，如果比下一个元素大，则二者交换顺序。接着，按同样的方式，比较第二个元素和第三个元素，如果比后一个元素大，则二者交换顺序。这样，整个数组遍历一次，就能把最大的元素移动到数组的最后位置上。

然后再从第一个元素开始，与下一个元素进行比较，如果比后一个元素大，则二者交换顺序。依次进行，只是这次遍历，因为最后一个元素已经是最大的了，我们本次遍历就可以不比较这个元素了，也就是遍历的元素数量减少了一个。

反复进行上述的过程，直至需要遍历的元素数量为 0，则排序结束。

每次遍历和比较，就像气泡冒出水面一样，把最大的元素冒泡至数组的尾部。

冒泡排序算法的思路比较容易理解，用 C 语言的代码实现如下：

void bubble_sort(int* parr, int count) {    int item_cnt = count -1;    // to be checked item count    while (item_cnt > 0) {        for (int i = 0; i < item_cnt; i++) {            if (parr[i] > parr[i+1]) {                int val = parr[i];                parr[i] = parr[i+1];                parr[i+1] = val;            }        }
        item_cnt--;    }}

复制代码

二、选择排序

上面介绍的冒泡排序，需要频繁进行数据移动，把大的元素向后移，开销很大。其实，我们可以只记住大的元素的位置，而不移动这个元素。这样遍历一遍后，直接把最大的元素与数组尾部的元素进行数据交换即可，这样也就把最大元素移动到最后了。

这种排序思路，就是选择排序算法。

选择排序算法，用 C 语言的代码实现如下：

void select_sort(int* parr, int count) {    int item_cnt = count -1;    // to be checked item count    while (item_cnt > 0) {        int max_idx = item_cnt;        for (int i = 0; i < item_cnt; i++) {            if (parr[i] > parr[max_idx]) {  // bigger                max_idx = i;            }        }
        if (max_idx != item_cnt) {  // not the lastest item            int val = parr[max_idx];            parr[max_idx] = parr[item_cnt];            parr[item_cnt] = val;        }
        item_cnt--;    }}

复制代码

我的微信号是实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。

发布于: 20 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/109dd01bc9388400a7db02c8d】。

实力程序员

关注

实力程序员，用实力说话！ 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

发布

暂无评论

创作场景

手写冒泡排序和选择排序算法

实力程序员

评论