专栏首页海天一树小朋友学C语言(27):选择排序

小朋友学C语言(27):选择排序

(一)基本原理(由小到大):

如果有n个数,需要比较n-1轮: 第1轮,将n个数中最小的数与a[0]对换,当然若a[0]就是最小的数则不用对换。 第2轮,将a[1]到a[n-1]中最小的数与a[1]对换,当然若a[1]就是最小的数则不用对换。 …… 第n-1轮,将最后的两个数,即a[n-2]与a[n-1]比较,若a[n-2] > a[n-1],则对换。至此,排序完毕。

(二)例子

例1:a[] = {5, 1, 2, 3, 4}

分析 :需要比较n - 1 = 4轮。

第1轮,a[1]=1是5个元素中最小的,并且a[1]不等于a[0],则对换a[1]与a[0]。对换后数组变为a[] = {1,5,2,3,4}

第2轮,对于a[]的后四个元素来说,a[2]=2是最小的,并且a[2]不等于a[1],则对换a[2]与a[1]。对换后数组变为a[] = {1, 2, 5, 3, 4}

第3轮,对于a[]的后三个元素来说,a[3]=3是最小的,并且a[3]不等于a[2],则对换a[3]与a[2]。对换后数组变为a[] = {1, 2, 3, 5, 4}

第4轮,对于a[]的最后两个元素来说,a[4]=4是最小的,并且a[4]不等于a[3],则对换a[4]与a[3]。对换后数组变为a[] = {1, 2, 3, 4, 5} 至此,排序结束。

例2:b[] = {1, 3, 5, 4, 2, 6}

分析:需要比较n - 1 = 5轮。

第1轮,b[0]就是六个元素中最小的数,不用对换。

第2轮,对于后五个元素来说,b[4] = 2是最小的数,b[4]不等于b[1],则对换b[4]和b[1],对换后,数组变为b = {1, 2, 5, 4, 3, 6}。

第3轮,对于后四个元素来说,b[4] = 3是最小的数,b[4]不等于b[2],则对换b[4]和b[2],对换后,数组变为b = {1, 2, 3, 4, 5, 6}。

第4轮,对于后三个元素来说,b[3] = 4是最小的数,不用对换。

第5轮,对于最后两个元素来说,b[4] = 5是最小的数,不用对换。至此排序结束。

(三)编程实现

#include<stdio.h>
// 打印数组,方便观察结果
void print_array(int a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
// 选择排序算法
void select_sort(int a[],int n)
{
    int i, j, min;
    // i代表比较的轮数,i的取值范围是0到n-2,共n-1轮
    for(i = 0; i < n - 1; i++)
    {
        /* min表示本轮比较中,最小元素的下标。
           这里先赋值为i,也就是本轮比较的首个元素所在的位置。
           下面根据比较结果,有可能变化,也有可能不变。*/
        min = i;
        // a[i]右侧的所有元素都与a[i]比较
        for(j = i + 1; j < n; j++)
        {
            // 若发现有更小的数,把该数的下标赋值给min
            // min在这个循环里可能会不断变化,最后会停在最小数所在的下标
            if(a[j] < a[min])
            {
                min = j;
            }
        }
        // 如果min与i不相等,说明a[i]右侧有比a[i]更小的数(可能不止一个)
        // 则a[min]就是a[i]右侧最小的数,将a[i]与a[min]互换位置
        if(min != i)
        {
            a[min] ^= a[i];
            a[i] ^= a[min];
              a[min] ^= a[i];
        }
        printf("After %d round sort, the array is:", i + 1);
        print_array(a, n);
    }
}
int main()
{
    int b[] = {5, 1, 2, 3, 4};
    int cnt = sizeof(b) / sizeof(int);
    select_sort(b, cnt);
    return 0;
}

运行结果:

After 1 round sort, the array is:1 5 2 3 4 
After 2 round sort, the array is:1 2 5 3 4 
After 3 round sort, the array is:1 2 3 5 4 
After 4 round sort, the array is:1 2 3 4 5 

(四)程序分析:

n - 1 = 4轮比较中,共产生了十次循环。分别是 i = 0, j = 1 i = 0, j = 2 i = 0, j = 3 i = 0, j = 4 i = 1, j = 2 i = 1, j = 3 i = 1, j = 4 i = 2, j = 3 i = 2, j = 4 i = 3, j = 4

具体执行如下:

i = 0, min = 0 j = 1, 第一个if成立,min = 1 j = 2, 第一个if不成立,min仍然为1 j = 3, 第一个if不成立,min仍然为1。 j = 4, 第一个if不成立,min仍然为1。内循环结束,跳出内循环 。第二个if成立,a[0]与a[min](即a[1])对换,数组变为{1, 5, 2, 3, 4}

i = 1, min = 1 j = 2, 第一个if成立,min = 2 j = 3, 第一个if不成立,min仍然为2。 j = 4, 第一个if不成立,min仍然为2。内循环结束,跳出内循环 。第二个if成立,a[1]与a[min](即a[2])对换,数组变为{1, 2, 5, 3, 4}

i = 2, min = 2 j = 3, 第一个if成立,min = 3 j = 4, 第一个if不成立,min仍然为3。内循环结束,跳出内循环 。第二个if成立,a[2]与a[min](即a[3])对换,数组变为{1, 2, 3, 5, 4}

i = 3, min = 3 j = 4, 第一个if成立,min = 4。内循环结束,跳出内循环 。第二个if成立,a[3]与a[min](即a[4])对换,数组变为{1, 2, 3, 4, 5} 至此,外循环结束,跳出外循环,继续执行下面的代码。

(五)作业

编写代码; 断点调试; 默写。

本文分享自微信公众号 - 海天一树(gh_de7b45c40e8b),作者:海天一树

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 小朋友学C++(1):Hello World!

    在学C++之前,最好先学习一下C语言 让我们先运行一段简单的代码,编译器可以使用 在线C++编译器 或 Xcode(苹果系统) 或Dev C++(Windows...

    海天一树
  • 小朋友学C语言(12):判断

    (一) 先动手编写一个程序: #include <stdio.h> int main() { if(1) { printf("T...

    海天一树
  • Python selenium实现微博自动登录

    这里使用selenium实现。 如果没有安装过python的selenium库,则安装命令如下

    海天一树
  • 深度线性神经网络也能做非线性计算,OpenAI使用进化策略新发现

    【新智元导读】OpenAI研究人员Jakob Foerster在OpenAI博客介绍了一个很有趣的实验,他们发现线性神经网络中的浮点表示实际上在零附近有一个比较...

    新智元
  • 腾讯课堂 IMWeb 七天前端求职提升营 Day 6

    本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中,所推送的面试题目及编程练习的一次汇总,期间还包括三次直播课的分享,均由腾讯导师给大家讲解,该系列博...

    Nian糕
  • 关于响应式前端WEB

    响应式 Web 设计 -Viewport什么是 Viewport? viewport 是用户网页的可视区域。 viewport 翻译为中文可以叫做"视区"。 手...

    企鹅号小编
  • 格雷码的实现

    http://blog.csdn.net/beiyeqingteng/article/details/7044471

    bear_fish
  • 二维码的生成(可设置大小)以及插件下载地址

    本文写的二维码生成是基于jQuery和jquery.qrcode.min.js插件的,本文将介绍两种方法和方式,仅供朋友选择和取舍。本文最下面附有插件的下载地...

    Java中文社群_老王
  • 社交机器人即将登堂入室 你准备好了吗?

    做好准备跟Jimmy、Pepper和Jibo说“你好”。 为普通家庭开发的第一波真正的社交陪伴机器人将在2015年来到你身边的商店-虚拟的或者其他形式的。 ...

    机器人网
  • python 检查字符串中是否包含非中文字符的方法

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    FungLeo

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动