#ifndef SORTING_ALGORITHM
#define SORTING_ALGORITHM

void BubbleSort(int* arr, int len)
{
    for (int i = 0, temp = 0; i < len - 1; ++i)
    {
        for (int j = 0; j < len - 1 - i; ++j)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

void BubbleSortPlus(int* arr, int len)
{
    for (int i = 0, temp = 0, flag = 0; i < len - 1; ++i)
    {
        flag = 0;
        for (int j = 0; j < len - 1 - i; ++j)
        {       
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = 1;
            }
        }
        if (0 == flag)
            break;
    }
}

void SelectionSort(int* arr, int len)
{
    for (int i = 0, min_index = 0, temp = 0; i < len - 1; ++i)
    {
        min_index = i;
        for (int j = i + 1; j < len; ++j)
        {
            if (arr[j] < arr[min_index])
                min_index = j;
        }
        temp = arr[i];
        arr[i] = arr[min_index];
        arr[min_index] = temp;
    }
}

void InsertionSort(int* arr, int len)
{
    for (int i = 1, pre_index = 0, current = 0; i < len; ++i)
    {
        pre_index = i - 1;
        current = arr[i];
        while (pre_index >= 0 && arr[pre_index] > current)
        {
            arr[pre_index + 1] = arr[pre_index];
            --pre_index;
        }
        arr[pre_index + 1] = current;
    }
}

void ShellSort(int* arr, int n) 
{
    for (int d = n / 2; d >= 1; d = d / 2)
    {
        for (int k = 0; k < d; k++) 
        {
            for (int i = k + d; i < n; i++) 
            {
                int temp = arr[i];
                int j = i - d;
                while (j >= k && arr[j] > temp) 
                {
                    arr[j + d] = arr[j];
                    j = j - d;
                }
                arr[j + d] = temp;
            }
        }       
    }
}

void QuickSort(int* arr, int left, int right)
{
    int pivot = arr[left], temp = 0, start = left, end = right;
    while (left < right)
    {
        while (left < right && arr[right] > pivot)
        {
            --right;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot)
        {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    if (left - 1 > start)
        QuickSort(arr, start, left - 1);
    if (end > left + 1)
        QuickSort(arr, left + 1, end);
}

void Merge(int* arr, int left, int mid, int right)
{
    int *temp = new int[right - left];
    int t = 0, i = left, j = mid;
    while (i < mid || j < right)
    {
        if (i >= mid)
        {
            temp[t++] = arr[j++];
        }
        else if (j >= right)
        {
            temp[t++] = arr[i++];
        }
        else
        {
            if (arr[i] < arr[j])
            {
                temp[t++] = arr[i++];
            }
            else
            {
                temp[t++] = arr[j++];
            }
        }
    }
    t = 0;
    for (int i = left; i < right; i++)
    {
        arr[i] = temp[t++];
    }
    delete[] temp;
}

void MergeSort(int* arr, int left, int right)
{
    if (left + 1 < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid, right);
        Merge(arr, left, mid, right);
    }
}

#endif /*SORTING_ALGORITHM*/

参考文章：
十大经典排序算法（动图演示）
快速排序算法，C语言快速排序算法详解
归并排序C++实现
常用排序算法总结（C++实现）