基本排序

选择排序

每次挑最小的放左边

void selectionSort(int s[], int n)
{
    for (int i = 0; i < n-1; ++i)
    {
        int minIndex = i;
        for (int j = i+1; j < n; ++j)
        {
            if (s[j] < s[minIndex])
            {
                minIndex = j;    
            }    
        }
        swap(s[i], s[minIndex]);
    }
}

插入排序

从左往右遍历，取出当前元素有序地插到其左半部分

void insertionSort(int s[], int n)
{
    for (int i = 1; i < n; ++i)
    {
        for (int j = i; j >= 1; --j)
        {
            if (s[j] < s[j-1])
            {
                swap(s[j], s[j-1]);
            }
            else
            {
                break;
            }
        }
    }
}

冒泡排序

从左往右进行两两比较，每一趟可以使最大值在最右边

void bubbleSort(int s[], int n)
{
    for (int i = n-1; i > 0; --i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (s[j] > s[j+1])
            {
                swap(s[j], s[j+1]);
            }
        }
    }
}

改进冒泡排序：优化外层循环

如果某一趟比较没有数值交换，则说明已经排好序；处理在排序过程中数组整体已经有序的情况

void bubbleSort2(int s[], int n)
{
    for (int i = n-1; i > 0; --i)
    {
        bool isSorted = true;

        for (int j = 0; j < i; ++j)
        {
            if (s[j] > s[j+1])
            {
                swap(s[j], s[j+1]);
                isSorted = false;
            }
        }

        if (isSorted)
        {
            return;
        }
    }
}

改进冒泡排序：优化内层循环

每一趟遍历记录最后一次交换的位置，这个位置后的元素其实都是有序的，不需要再次比较

void bubbleSort3(int s[], int n)
{
    int endPos = n-1;
    for (int i = n-1; i > 0; --i)
    {
        int lastExchangeIndex = 0;
        for (int j = 0; j < endPos; ++j)
        {
            if (s[j] > s[j+1])
            {
                swap(s[j], s[j+1]);
                lastExchangeIndex = j;
            }
        }

        endPos = lastExchangeIndex;
    }
}