Dotcpp  >  编程教程  >  排序算法  >  直接选择排序C/C++代码图文讲解

直接选择排序C/C++代码图文讲解

点击打开在线编译器,边学边练

直接选择排序就是遍历整个数组,每遍历一遍的目的是找出该数组中的最大数和最小数对应的下标,然后将最小数和数组的第一个数进行交换,最大数和数组的最后一个数进行交换,然后缩小范围再次遍历。


(1)定义

直接选择排序是指每次都从剩余数据中选出最大或者最小的,将其排在已经排好的有序表后面。


(2)基本原理

每次从无序表中选择最小(或最大)元素,将其作为首元素,知道所有元素排完为止。将一个有n个元素的数组从小到大排序,第一次从R[0] ~ R[n-1]中选取最小值,与R[0]交换,第二次从R[1] ~ R[n-1]中选取最小值,与R[1]交换,…,第i次从R[i-1] ~ R[n-1]中选取最小值,与R[i-1]交换,…,第n-1次从R[n-2] ~ R[n-1]中选取最小值,与R[ n -2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

下面的动图非常清晰的诠释了直接插入排序的过程:


直接选择排序


(3)时间复杂度

最好的情况是数组所有元素已经是有序排列,移动次数为0;

最差的情况是数组所有元素全部反序,移动次数为3(n-1)。

无论最好与最差情况,在排序时所有待排元素均需与后面的元素进行比较,比较次数为:

(n-1)+(n-2)+ …+2+1= n(n-1)/2

因此,直接插入排序的平均时间复杂度为O( n 2 n^2 n2) 。


(4)空间复杂度

直接选择排序仅需一个存储空间用于记录交换的暂存单元,因此空间复杂度为:O(1) 。


(5)优缺点

优点:直接选择排序算法简单直观,当待排序记录数量n很小时,局部有序时,较为适用。

缺点:不稳定,由于直接选择排序是以最大或最小值直接与最前方未排序的键值交换,数据排序顺序很有可能被改变。


(6)代码设计

a. 实现直接插入排序需要设计两层循环,整个数组为外循环,后面未排列好的无序元素为内循环;

b. 使用变量minIndex存储最小值的数组元素下标,依次遍历无序元素,找出最小元素下标;

c. 将最小元素与无序元素的首元素进行交换,无序元素个数减1,相应i加1;

d. 重复b和c两步操作,直至i=n-1,即无序元素个数为0,则排序完成。


C语言代码实现如下:

#include <stdio.h>
void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
} 
void chooseSort(int array[],int n)
{
    int i,j;
    int minIndex,temp,num;
    for(i=0;i<n-1;i++)
    {
        minIndex=i;
        for(j=i+1;j<n;j++)
        {
            if(array[j]<=array[minIndex])
            {
                minIndex=j;
            }
        }
        if(i!=minIndex)
        {
            temp=array[minIndex];
            array[minIndex]=array[i];
            array[i]=temp;
        }
        printArray(array, n);
    }
}
int main(void)
{
    int array[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    printArray(array,sizeof(array)/sizeof(int));
    chooseSort(array,sizeof(array)/sizeof(int));
    printf("\n");
    return 0;
}

如果我们编译并运行上述程序,那么它应该产生以下结果:

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48 
2 44 38 5 47 15 36 26 27 3 46 4 19 50 48 
2 3 38 5 47 15 36 26 27 44 46 4 19 50 48 
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48 
2 3 4 5 47 15 36 26 27 44 46 38 19 50 48 
2 3 4 5 15 47 36 26 27 44 46 38 19 50 48 
2 3 4 5 15 19 36 26 27 44 46 38 47 50 48 
2 3 4 5 15 19 26 36 27 44 46 38 47 50 48 
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48 
2 3 4 5 15 19 26 27 36 44 46 38 47 50 48 
2 3 4 5 15 19 26 27 36 38 46 44 47 50 48 
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48 
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48 
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48 
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

知识点标签:排序


本文固定URL:https://www.dotcpp.com/course/941

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)