top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

排序算法:选择排序之直接选择排序
直接选择排序是选择排序算法的基本实现,也是一种经典的排序算法,理解起来也简单。

选择排序基本思想:每次从待排序的数据元素中选取关键字最小(或最大)的元素放到数据元素集合的最前面(或最后面),数据元素集合不断缩小,当数据元素集合为空时,排序完成。常用的选择排序算法有直接选择排序和堆排序两种。【堆排序是一种基于完全二叉树的排序】

直接选择排序的基本思想:从待排序的数据元素集合中选取关键字最小的元素并将其与原始数据集合中的第一个元素互换;然后从不包括第一个元素的数据集中选取关键字最小的数据元素,将其与集合中第二个元素互换;....... 如此重复,直到数据元素集合中只剩一个元素时【也可以说进行下一次操作数据集合为空时】,排序完成。

C语言实现及测试:
#include <stdio.h>

/**
 * 直接选择排序:升序
 * @param data  待排序集合
 * @param len   集合大小
 *
 * 注: 此处为方便演示,依旧只是进行简单的 int数组 排序
 */
void selectSortAsc(int data[], int len){
    int i = 0, j = 0;
    int smallIndex = 0, temp = 0;
    for(i = 0; i < len - 1; i++){
        smallIndex = i;
        for(j = i+1; j < len; j++){
            if(data[smallIndex] > data[j]){
                smallIndex = j;  //记录最小元素的下标
            }
        }
        if(smallIndex != i){   //最小元素下标不是 i 时交换,即不是本身时执行交换
            temp = data[i];
            data[i] = data[smallIndex];
            data[smallIndex] = temp;
        }
    }
}

/**
 * 测试
 */
int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23};
    int n = 12;
    selectSortAsc(a, n);

    for(i = 0; i < n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}

复杂度分析
在直接选择排序中,第 1 次比较需进行 n-1 次比较,第 2 次需要进行 n-2 次比较... ... 第 n-1 次需要进行 1 次比较,所以可以得出总的比较次数:(n-1)+(n-2)+(n-3)+ ... ... +1;也就是n(n-1)/2。所以时间复杂度为 O(n2)。空间复杂度,在待排序元素本身就有序的情况下,即最好情况下,空间复杂度为 O(0),最坏情况下为 O(n), 平均空间复杂度为 O(1)

总结
选择排序是很好理解的,因为其实现过程比较贴近生活(暂且这么说),选择大小的过程是排序的关键。值得注意的是该算法是不稳定的算法,因为每次丛无序区选取元素与无序区第一个元素交换时可能导致关键字相同的元素位置发生变化。如果在选出最小(或最大)元素后将它前面的无需元素依次向后移动一个单元,然后再将最小(或最大)元素放到有序区之后,这样就能保证稳定性,所以说也可以实现稳定,但是这样做也就比之前多了额外的开销。

以上只是个人看法,欢迎留言补充。
标签
排序
算法
选择排序
直接选择排序
SelectSort
上一篇:排序算法:插入排序之希尔排序
下一篇:排序算法:交换排序之冒泡排序
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
最新留言
[2018/11/27]博客该更新了
[2018/10/25]网站链接以便更 www.qiuyegen.com
[2018/04/07]太难找了,找到了
[2018/03/21]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/21] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/20]你加我友链了????
[2017/11/20]你的alert 很不友好哈
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3