排序算法——直接选择排序

一、直接选择排序的思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

1、  初始状态：无序区为array[1…n]，有序区为空；

2、  第一趟排序：

在无序区array[1…n]中选出关键字最小的记录array[k]，将它与无序区的第1个记录array[0]交换，使array[1..1]和array[2…n]分别为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……..

3、第i趟排序

第i趟排序开始时，当有序区和无序区分别为array[0…i-1]和array[i…n-1]。该趟排序从当前无序区中选出关键字最小的记录array[k]，将它与无序区的第1个记录array[i]交换。使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

二、C代码实现

#include "stdio.h"
/*
* 函数：choose_sort(int *array, int n)
* 功能：插入排序
* 参数：n为数组元素的个数
*/
void choose_sort(int array[],int n)
{
    int i,j;
    int b,temp,num;
    for(i=0;i<n-1;i++)
    {
        temp=i;
        for(j=i+1;j<n;j++)
        {
            if(array[j]<=array[temp])//获取待排序的元素中最小的元素
            {
                temp=j;//记录最小元素的下标
            }
        }
        if(i!=temp)
        {
            b=array[temp];
            array[temp]=array[i];
            array[i]=b;
        }
    }
}
int main(int argc,char *argv[])
{
    int array[]={3,8,4,7,1};
    choose_sort(array,5);
    for(int i=0;i<5;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
    return 0;
}

三、直接选择排序的时间

直接选择排序的平均时间复杂度为O(n*n)，并且是一种不稳定的排序。