选择排序

排序方法

选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最快的 时间复杂度都是O(n 2)），然而它们排序的方式确是值得观察与探讨的。

选择排序

选择排序法原理：

将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个最小值，并放入前端已排序部份的最后一个，

例如：

排序前：70 80 31 37 10 1 48 60 33 80

[1] 80 31 37 10 70 48 60 33 80 选出最小值1

[1 10] 31 37 80 70 48 60 33 80 选出最小值10

[1 10 31] 37 80 70 48 60 33 80 选出最小值31

[1 10 31 33] 80 70 48 60 37 80 ......

[1 10 31 33 37] 70 48 60 80 80 ......

[1 10 31 33 37 48] 70 60 80 80 ......

[1 10 31 33 37 48 60] 70 80 80 ......

[1 10 31 33 37 48 60 70] 80 80 ......

[1 10 31 33 37 48 60 70 80] 80 ......

例题分析

例：对一组数据由小到大进行排序，数据分别为 526、36、2、369、56、45、78、92、125、52。

思路分析：程序中用到两个for循环语句。第一个 for 循环是确定位置的，该位置是存放每次从待排序数列中经选择和交换后所选出的最小数。第二个 for 循环是实现将确定位置上的数与后面待排序区间中的数进行比较的。

参考代码：

#include <stdio.h>
int main()
{
    int i,j,t,a[];    //定义变量及数组为基本整型
    printf("请输入10个数：\n");
    for(i=;i<;i++)
        scanf("%d",&a[i]);    //从键盘中输入要排序的10个数字
    for(i=;i<=;i++)
        for (j=i+;j<=;j++)
            if(a[i]>a[j])    //如果前一个数比后一个数大，则利用中间变量t实现两值互换
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
    printf("排序后的顺序是：\n");
    for(i=;i<=;i++)
        printf("%5d", a[i]);    //输出排序后的数组
    printf("\n");
    return ;
}

运行结果：

请输入10个数：526 36 2 369 56 45 78 92 125 52

排序后的顺序是： 2 36 45 52 56 78 92 125 369 526

技术要点：

选择排序的基本算法是从待排序的区间中经过选择和交换后选出最小的数值存放到 a[0] 中，再从剩余的未排序区间中经过选择和交换后选出最小的数值存放到 a[1] 中，a[1] 中的数字仅大于 a[0]，依此类推，即可实现排序。