选择排序（SelectionSort）

http://blog.csdn.net/magicharvey/article/details/10274765

算法描述

选择排序是一种不稳定排序。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

基本思想

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

实现步骤

从序列中找到最小的元素，并与第一个元素交换；
从a[2],...a[n]中的元素中找到最小的元素，并与a[2]交换，从而a[1],a[2]是有序的；
以此类推，从a[i],...,a[n]中的元素中找到最小的元素，并与a[i]交换，则a[1],a[2],..,a[i]是有序的。

算法实现

代码在xcode中进行验证，可以直接使用。

//选择排序

void SelectionSort(int a[], int length)

{

    int min_index;

    for(int i = ; i < length; i++)

    {

        min_index = i;

        //从a[i+1],a[i+2],..,a[length-1]的序列中找到最小值，保存在min_index中

        for(int j = i + ; j < length; j++)

        {

            if(a[min_index] > a[j])

            {

                min_index = j;

            }

        }

        //交换a[i]与a[min_index]

        if(min_index !=i)

        {

            int temp = a[i];

            a[i] = a[min_index];

            a[min_index] = temp;

        }

    }

}

性能分析

最坏和最好的时间复杂度都为o(n^2)，空间复杂度为o(1)

秒客网