选择排序算法

选择排序(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值较小时，选择排序比冒泡排序快。

常见的排序算法 在实际应用中，我们经常遇到需要将大量数据进行排序的问题，下边博主将带领大家认识常见的排序算法，相信通过这一篇文章让你能够掌握基本的排序算法，这些排序也是在面试笔试中的高频考点，让我们读完这篇文章，从此不做迷糊人！
常见的排序算法（上） 时间如流水，今天就到初阶数据结构最后一个知识章节了，常见的排序算法！在进入这期之前，程爱打篮球的程序猿想说一句，如果有不懂的地方可以反复观看我之前的内容，再还有不懂可以直接找我，帮你安排的妥妥的！