选择排序算法-阿里云开发者社区

开发者社区> wuyudong> 正文

选择排序算法

简介:
+关注继续查看

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

本文地址:http://www.cnblogs.com/archimedes/p/select-sort-algorithm.html,转载请注明源地址。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其 最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

C语言实现:

// Completed on 2014.10.9 08:01
// Language: C99
//
// 版权所有(C)codingwu   (mail: oskernel@126.com) 
// 博客地址:http://www.cnblogs.com/archimedes/

#include<stdio.h>     
#include<stdbool.h>  
void swap(int *a, int *b)   //交换两元素的值
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}
void printArray(int a[], int count)   //打印数组元素
{
    int i;
    for(i = 0; i < count; i++)
        printf("%d ",a[i]);
    printf("\n");
}
void selection_sort(int *a, int len)
{
    register int i, j, min, t;
    for(i = 0; i < len - 1; i ++)
    {
        min = i;
        for(j = i + 1; j < len; j ++) //查找最小值
            if(a[min] > a[j])
                min = j;
        if(min != i)           //交换
            swap(&a[min], &a[i]);
    }
}
int main(void)   
{
    int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1};
    int n = sizeof(a)/sizeof(*a);
    printArray(a, n);
    selection_sort(a, n);
    printArray(a, n);    
    return 0;
}

复杂度分析

选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。

比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
JavaScript ~ 排序算法(选择排序)
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <link type="text/css" rel="stylesheet" href="style/flex.
943 0
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
936 0
排序算法(七):快速排序
快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。
726 0
+关注
wuyudong
我的个人博客地址:http://wuyudong.com/
203
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载