简单选择排序及其优化（C#）

基本思想

就是首先扫描整个数组，找到最小的元素，然后和第一个元素进行交换，如此一来就等同于将最小的元素放到它在有序表中最终的位置上。然后从第二个元素开始扫描整个表，找到剩余n-1个元素中最小的元素，与第二个元素交换位置。以此类推，在执行n-1遍之后，这个数组就自然有序了。（当然每次找最大的元素，与最后一个元素交换也是可行的）

复杂度

选择排序有一个最明显的优于冒泡排序的地方：数据交换的次数。在选择排序中，一共最多产生n-1次交换（有时当剩余数组第一个值就是最小值的时候甚至不需要进行交换）， 虽然选择排序的时间复杂度也是O(n^2)，选择排序的空间复杂度也是O(1)。

稳定性

不稳定排序

总结

选择排序优缺点：

优点：一轮比较只需要换一次位置；

缺点：效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。

    /// <summary>
    /// 简单选择排序
    /// </summary>
    /// <param name="array">排序数组</param>
    void OptBase(int[] array)
    {
        if (array.Length < 2) return;
        int minIdx;
        for (int i = 0; i < array.Length; i++)
        {
            //每次循环开始，重置坐标
            minIdx = i;
            //前i个已经有序
            //内循环是在[i,array.length-1]的区间找出最小的元素位置，和第i个进行交换
            for (int j = i; j < array.Length; j++)
            {
                if (array[j] < array[minIdx]){
                    minIdx = j;
                }
            }
            //判断第i个不是最小的进行减缓，是的话不做处理
            if(i != minIdx)
            {
                Swap(array, minIdx, i);
            }
        }
    }

优化

可以一次性地找到最大值和最小值，分别和头、尾两个元素进行交换。 这样一来外循环只要执行原来一半的循环次数就可以了。但是需要注意一点：每次循环要进行2次交换，第一次最小值交换结束之后，在进行最大值交换的时候要先判断，最大值是不是在第一个位置，在第一次最小值交换的时候已经换到了后面？所以要先交换最小的，再交换最大的

    /// <summary>
    /// 简单选择排序的优化
    /// </summary>
    /// <param name="array">排序数组</param>
    void OptOptimize(int[] array)
    {
        if (array.Length < 2) return;
        //一次找到最大值和最小值
        int minIdx, maxIdx;
        //外循环遍历一半结束
        //如果完整遍历，整个数组都会变成倒序排列
        for (int i = 0; i < array.Length; i++)
        {
            minIdx = i;
            maxIdx = i;
            //内循环从两边缩进
            for (int j = i; j < array.Length-i; j++)
            {
                if (array[j] < array[minIdx])
                {
                    minIdx = j;
                }
                if (array[j] > array[maxIdx])
                {
                    maxIdx = j;
                }
            }
            if (i != minIdx)
            {
                Swap(array, i, minIdx);
            }
            if(array.Length-1-i != maxIdx)
            {
                //防止最大数在第一个，优先和最小值进行交换
                if(i == maxIdx)
                {
                    Swap(array, array.Length - 1 - i, minIdx);
                }
                else
                {
                    Swap(array, array.Length - 1 - i, maxIdx);
                }
            }
        }
    }

  //互换函数
   void Swap(int[] arr, int index1, int index2)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }