选择排序及其简单优化

选择排序是不稳定的排序算法，譬如[8, 8, 2],在第一轮选择的时候是选择到最小值2，第一个8与2交换后两个8之间的顺序发生了变化，所以不稳定

未优化的选择排序

一次遍历过程只找出一个最大值或是最小值

    void SelectSort(T* arr,int n)
    {
        int max = 0;
        for (int index = 0; index < n-1; index++)
        {
            max = index ;
            int pos = index + 1;
            //找出最值
            while (pos<n)
            {
                if (arr[pos]>arr[max])
                {
                    max = pos;               
                }
                pos++;
            }
            //交换
            swap(arr[index], arr[max]);
        }
    }

优化后的选择排序

    void SelectSort2(T*arr,int n)
    {
        int left = 0;
        int right = n-1;
        while (left < right)
        {
            int min = left;
            int max = right;
            for (int i = left; i <= right ; i++)
            {
                if (arr[i] < arr[min])
                    min = i;
                if(arr[i] > arr[max])
                    max = i;
            }
            //考虑修正的情况，最大值在最小位置，最小值在最大位置。
            swap(arr[max], arr[right]);

            if (min == right)
            {
                min = max;
            }
            swap(arr[min], arr[left]);
            left++;
            right--;
        }
    }

总结：

选择排序的时间复杂度在最好和最坏的情况下都是O(n^2),