七大排序算法---选择排序及优化

思路分析

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

时间复杂度O(N^2) 不稳定的排序

代码实现

void SelectSort(int array[], int size)
{
    int i = 0;
    int min = 0;
    while (i < size)
    {
        min = i;
        for (int n = i; n < size; n++)//找到下标i之后最小的数
        {
            if (array[min] > array[n])
                min = n;
        }
        if (array[min] < array[i])//如果找到的最小的数比下标i的数小，进行交换
        {
            array[min] = array[min] + array[i];
            array[i] = array[min] - array[i];
            array[min] = array[min] - array[i];
        }
        i++;
    }
}

int main()
{
    int array[10] = { 2, 5, 9, 8, 6, 4, 0, 1, 3, 7 };
    SelectSort(array, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d,",array[i]);
    }
    return 0;
}

优化

每次查找时不仅找出最小值，还找出最大值，分别插到前面和后面，可以减少一半的查询时间。

//选择排序优化--每次找到最大最小两个数。
void SelectSortPlus(int array[],int size)
{
    int left = 0;//查找的左边界
    int right = size - 1;//查找的右边界
    while(left < right)
    {
        int min = left;
        int max = right;
        for (int i = left; i <= right; i++)//找到最大（max）最小（min）数
        {
            if (array[min]>array[i])
            {
                min = i;
            }
            if (array[max] < array[i])
            {
                max = i;
            }

            if (array[min] < array[left])//如果找到的最小的left数比下标的数小，进行交换
            {
                array[min] = array[min] + array[left];
                array[left] = array[min] - array[left];
                array[min] = array[min] - array[left];
            }
            if (array[max] > array[right])//如果找到的最大的数比下标right的数大，进行交换
            {
                array[max] = array[max] + array[right];
                array[right] = array[max] - array[right];
                array[max] = array[max] - array[right];
            }
        }
        right--;
        left++;
    }
}

int main()
{
    int array[10] = { 2, 5, 9, 8, 6, 4, 0, 1, 3, 7 };
    SelectSortPlus(array, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d,",array[i]);
    }
    return 0;
}