十大排序算法详解（一）冒泡排序、选择排序、插入排序、快速排序、希尔排序

插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

这里因为插入排序比较简单就直接展示代码

插入排序代码

void InsetSort(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

希尔排序

希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。希尔于1959年提出这种排序算法。 希尔排序是非稳定排序算法。

其实希尔排序是插入排序的优化版，就是多增加了预排序，为什么要增加预排序，因为如果一个最大的数在最前面，那么他要到最后面要好多步，就非常浪费时间，原来是一步一步走的，现在假设让他一次走数组长度的三分之一，就缩短大量时间。

希尔排序的代码

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = 0; i < n-gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp > a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

因为选择排序过于简单，这里进行一个小优化，就是同时找一个最大和最小的数将其排在一头一尾。

选择排序的代码

void Swap(int* a, int* b)
{
    int s = *a;
    *a = *b;
    *b = s;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin; i <= end; i++)
        {
            if (a[i] > a[maxi])
                maxi = i;
            if (a[i] < a[mini])
                mini = i;
        }
        Swap(&a[begin], &a[mini]);
        Swap(&a[end], &a[maxi]);
        begin++, end--;
    }
}

冒泡排序

冒泡排序，是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

一般来说大家学的第一个排序就冒泡排序，因为过于简单就不过多解释了。

冒泡排序的代码

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

快速排序

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序的代码

void QuickSort(int* a, int begin,int end)
{
    assert(a);
    if (begin > end)
        return;
    int left = begin, right = end;
    int keyi = left;
    while (left < right)
    {
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        Swap(&a[left], &a[right]);
    }
    Swap(&a[keyi], &a[left]);
    keyi = left;
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}

上面这个代码会出现偶然性，所以进行优化，如下

int Index(int* a, int begin, int end)
{
    int mid = (begin + end) / 2;
    if (a[begin] < a[mid])
    {
        if (a[mid] < a[end])
            return mid;
        else if (a[end] < a[begin])
            return end;
        else
            return begin;
    }
    else
    {
        if (a[mid] > a[end])
            return mid;
        else if (a[end] < a[begin])
            return end;
        else
            return begin;
    }
}
void QuickSort1(int* a, int begin, int end)
{
    assert(a);
    if (begin > end)
        return;
    else
    {
        int prev = begin, cur = begin + 1;
        int keyi = begin;
        int mid = Index(a, begin, end);
        Swap(&a[mid], &a[keyi]);
        while (cur <= end)
        {
            if (a[cur] < a[keyi] && ++prev != cur)
            {
                Swap(&a[cur], &a[prev]);
            }
            ++cur;
        }
        Swap(&a[keyi], &a[prev]);
        keyi = prev;
        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
}

快速排序非递归代码代码

void QuickSortNonR(int* a, int begin, int end)
{
    //这里需要栈
    int stack[1000] = { 0 };
    int top = 0;
    stack[top++] = end;
    stack[top++] = begin;
    while (top>0)
    {
        int left = stack[top - 1];
        top--;
        int right = stack[top - 1];
        top--;
        int keyi = PostSort(a, left, right);
        if (left < keyi - 1)
        {
            stack[top++] = keyi-1;
            stack[top++] = left;
        }
        if (right > keyi + 1)
        {
            stack[top++] = right;
            stack[top++] = keyi+1;
        }
    }
}

因为这里要用栈，这里我就直接用数组模拟。