选择排序

一. 算法描述

选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

关键问题：在剩余的待排序记录序列中找到最小关键码记录。

为方便理解我还准备了动图：

二. 算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1) (用于交换和记录索引)

稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）

三. 算法实现

//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
    int temp = *data1;
    *data1 = *data2;
    *data2 = temp;
}

/********************************************************
*函数名称：SelectionSort
*参数说明：pDataArray 无序数组；
*          iDataNum为无序数据个数
*说明：    选择排序
*********************************************************/
void SelectionSort(int* pDataArray, int iDataNum)
{
    for (int i = 0; i < iDataNum - 1; i++)    //从第一个位置开始
    {
        int index = i;
        for (int j = i + 1; j < iDataNum; j++)    //寻找最小的数据索引 
            if (pDataArray[j] < pDataArray[index])
                index = j;

        if (index != i)    //如果最小数位置变化则交换
            DataSwap(&pDataArray[index], &pDataArray[i]);
    }
}