搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 咸鱼成长小站 > 常见排序算法-选择排序

常见排序算法-选择排序

咸鱼成长小站 2018-07-01

上次我们详细的描述了一下冒泡排序的原理与写法。最后还对其最优情况进行了优化,使它最优情况下有O(n)的时间复杂度。

今天我们来介绍第二种排序算————选择排序。

相对于冒泡排序,选择排序更加的简单,也更加的易懂,它的排序过程就是在第i趟排序中,先遍历一遍待排序的数组,然后找出其中最小的一个,将它的位置和第i个交换。也就是说,一个数组包含n个元素,排序的过程就是在第i到n个元素中(i = 1,2,..,n-1),找到最小的一个,放到第i位。

依旧举个栗子:

我们有一个未排序数组:[8,7,6,9,5,4,2,1,3]

第一趟排序

我们首先将第一位下标记位min,然后遍历这个数组,寻找最小的下标。

很显然,最小值为下标为7的1。我们将其与第一位交换,数组就变为

[1,7,6,9,5,4,2,8,3]

第二趟排序

我们这一次只需要遍历第2至9位。因为第一位已经是有序的了。

第二次遍历得到最小值的下标为6。将其与第二位交换,结果变成

[1,2,6,9,5,4,7,8,3]

之后的排序过程与之前的相似,这儿就不再赘述了。

我们最多需要经过 n-1 次排序,就可以将一个无序数组转变为有序数组。

那么它的时间复杂度是多少呢?

我们至多要进行 n-1 次排序,因此外层循环需要执行 n-1 次。

而每一次循环,我们所需要执行的比较次数不一样,分别为 n-1次,n-2次,n-3次…1次

所以我们的时间复杂度就为O(n-1+n-2+…+2+1 = n*(n-1)/2)

最终得到的是一个 O(n^2) 时间复杂度。和冒泡排序是一样的。

但是和冒泡排序不同的点就是选择排序所需要进行的交换次数少,所以尽管两种排序都是O(n^2)的时间复杂度,但选择排序性能还是比冒泡要略优一点。

下面是选择排序的代码样例

 1#include <iostream>
2template <typename T>
3void SelectSort(T *arr,int n){
4    for(int i = 0;i < n;i++){
5        int curmin = i;
6        for(int j = i+1;j < n;j++){
7            if(arr[j] < arr[curmin]){
8                curmin = j;
9            }
10        }
11        if(curmin != i){
12            T temp = arr[i];
13            arr[i] = arr[curmin];
14            arr[curmin] = temp;
15        }
16    }
17}
18int main(){
19    int a[10] = {9,8,7,6,5,4,3,2,1,0};
20    SelectSort(a,10);
21    for(int i = 0;i < 10; i++){
22        std::cout<<a[i]<<" ";
23    }
24    return 0;
25}


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《常见排序算法-选择排序》的版权归原作者「咸鱼成长小站」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注咸鱼成长小站微信公众号

咸鱼成长小站微信公众号:SilentFish98

咸鱼成长小站

手机扫描上方二维码即可关注咸鱼成长小站微信公众号

咸鱼成长小站最新文章

精品公众号随机推荐