选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素,存放在序列的起始位置，直到全部待排序的数据元素排完。

1、从第一个元素开始，分别与后面的元素向比较，找到最小的元素与第一个元素交换位置；
2、从第二个元素开始，分别与后面的元素相比较，找到剩余元素中最小的元素，与第二个元素交换；
3、重复上述步骤，直到所有的元素都排成由小到大为止。

代码：

#include<stdio.h>
void SlectSort(int *a,int n);
int main(void)
{
    int k;
    int x[10] = {2,4,6,8,0,1,3,5,7,9};
    for(k=0;k<10;k++)
    {
      printf("%d ",x[k]);
    }
    printf("\n");

    SlectSort(x,10);

    for(k=0;k<10;k++)
    {
      printf("%d ",x[k]);
    }
    getchar();
  return 0;
}

void SlectSort(int *a,int n)
{
   int i,j,t;
   int min;
   for(i=0;i<n-1;i++)  //外层循环遍历整个数组
   {
      min = i;  //设下标i是数组中最小的元素
      for(j=i+1;j<n-1;j++)//内层循环遍历i之后的数组
      {
          if(a[j]<a[min])//让i之后的数组和i做比较，找出最小值
          {
            min = j;
          }
      }
          t = a[i];
          a[i] = a[min];
          a[min] = t;//交换算法，把最小值和i做比较（从小到大排列）
   }
       
}

运行结果:

2 4 6 8 0 1 3 5 7 9
0 1 2 3 4 5 6 7 8 9

时间复杂度

时间复杂度为O(n*n)

总结:

N个元素需要排序N-1轮；
第i轮需要比较N-i次；
N个元素排序，需要比较n（n-1）/2次；
选择排序的算法复杂度仍为O（n*n）；
相比于冒泡排序，选择排序的交换次数大大减少，因此速度要快于冒泡排序