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

举报
实力程序员 发表于 2021/07/16 09:00:41 2021/07/16
【摘要】 今天给大家介绍另外2种排序算法:冒泡排序和选择排序。它们的思路有些相似,因此一并介绍,并且给出源码实现。一、冒泡排序自然界中,经常会看到一个气泡从水底冒出,最开始很小,浮向水面的过程中会变得越来越大,到达水面时最大。冒泡排序算法,就是从上面的场景中得到的灵感启发,其想法如下:要对一个未被排序的数组,实现将元素从小到大的顺序进行排序,那么可以从第一个元素开始,与下一个元素进行比较,如果比下一个...

今天给大家介绍另外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--;
    }
}



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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200