算法导论:选择排序的原理与实现

swf动画图解
服务器君一共花费了289.618 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:

首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

下面附上动画演示:

选择排序的思想非常直接,不是要排序么?那好,我就从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作了。可以很清楚的发现,选择排序是固定位置,找元素。相比于插入排序的固定元素找位置,是两种思维方式。不过条条大路通罗马,两者的目的是一样的。

下面是C语言实现:

#include <stdio.h>
#include <stdlib.h>
void main()
{
    int i;
    int arr[10];
    int count;

    printf("排序前数组为:");
    srand((int)time(0));
	for(i=0; i < 10; i++)
	{
	    arr[i] = rand()%100;
	    printf("%d ",arr[i]);
	}

    count = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, count);

    printf("\n排序后数组为:");
    for(i=0; i < 10; i++)
	{
	    printf("%d ", arr[i]);
	}
}

void selectionSort(int data[], int count)
{
    int i, j, min, temp;
    for(i = 0; i < count; i ++) {
        /*find the minimum*/
        min = i;
        for(j = i + 1; j < count; j ++)
            if(data[j] < data[min])
                min = j;
        temp = data[i];
        data[i] = data[min];
        data[min] = temp;
    }
}

从选择排序的思想或者是上面的代码中,我们都不难看出,寻找最小的元素需要一个循环的过程,而排序又是需要一个循环的过程。因此显而易见,这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下,算法可以保证一定的速度,当n足够大时,算法的效率会降低。并且随着n的增大,算法的时间增长很快。因此使用时需要特别注意。

延伸阅读

此文章所在专题列表如下:

  1. 算法导论:选择排序的原理与实现

本文地址:http://www.nowamagic.net/librarys/veda/detail/1849,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1849

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码之美》 聂雪军 (译者)

《代码之美》介绍了人类在一个奋斗领域中的创造性和灵活性:计算机系统的开发领域。在每章中的漂亮代码都是来自独特解决方案的发现,而这种发现是来源于作者超越既定边界的远见卓识,并且识别出被多数人忽视的需求以及找出令人叹为观止的问题解决方案。《代码之美》33章,有38位作者,每位作者贡献一章。每位作者都将自己心目中对于“美丽的代码”的认识浓缩在一章当中,张力十足。38位大牛,每个人对代码之美都有自己独特的认识,现在一览无余的放在一起,对于热爱程序的每个人都不啻一场盛宴。 虽然《代码之美》的涉猎范围很广,但也只能代表一小部分在这个软件开发这个最令人兴奋领域所发生的事情。

更多计算机宝库...