Sort(插入排序、希尔排序、选择排序、堆排序)

1.插入排序
原理：从第二个元素开始拿出元素，向其前面的区间里插。知道插到最后一个元素完了即有序。
特点：序列接近有序时效率较高，适合小于千级数量的排序。
时间复杂度：O（N^2） 最好的时候接近O（N），即每次插的位置都是其原位，不用挪动。
空间复杂度：O（1）

void InsertSort(int *a,size_t size)
{
    assert(a);
    for(int i = 1;i < size;++i)
    {
        int tmp = a[i];
        int j;
        for(j = i-1;j >= 0 &&tmp < a[j];--j)
        {
            a[j+1] =a[j];
        }
        a[j + 1] = tmp;
    }
}

2.希尔排序
原理：希尔排序其实是插入排序的优化，其排序的最后一趟即为插入排序，之前多做的比较是为了让序列接近有序，提高希尔排序效率。
时间复杂度：O（N^1.3）
空间复杂度：O (1)

代码：

void ShellSort(int *a,size_t size)
{
    int gap = size;
    while(gap > 1)
    {
        gap = gap/3 + 1;//加1防止gap小于1
        for(int i = gap;i < size;++i)
        {
            int tmp = a[i];
            int end = i - gap;
            while(end >= 0 && tmp < a[end])
            {
                a[end+gap] = a[end];
                end -= gap;//倒回去比
            }
            a[end + gap] = tmp;
        }
    }
}

3.选择排序
原理:每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
特点：不稳定
时间复杂度：O(N^2)
空间复杂度：O(1)

void SelectionSort(int a[],size_t size)
{
    assert(a);
    for(int i = 0;i < size - 1;++i)
    {
        int min = i;
        for(int j = i + 1;j < size;++j)
        {
            if(a[j] < a[min])
            {
                min = j;
            }
        }
        if(a[min] != a[i])
        {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

4.堆排序
原理：利用二叉堆进行排序。
特点：需要辅助空间，适合海量数据比较。
时间复杂度：O（N*lgN）
空间复杂度：O（1）

void AjustDown(int *a,size_t size,size_t root)
{
    assert(a);
    int child = root * 2 + 1;
    int parents = root;
    while(child < size)
    {
        if(child + 1 < size && a[child+1] > a[child])
        {
            child++;
        }
        if(a[child] > a[parents])
        {
            swap(a[child],a[parents]);
            parents = child;
            child = child *2 +1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int *a,size_t size)
{
    assert(a);
    //单趟堆排，建堆
    for(int i = (size - 2)/2;i >= 0;--i)//size - 1为最后一个元素，在-1除2为第一个叶子节点的根节点
    {
        AjustDown(a,size,i);
    }
    //开始调整
    for(int i = size -1;i > 0; --i)
    {
        swap(a[i],a[0]);
        AjustDown(a,i,0);
    }
}

测试

void Print(int *a,size_t size)
{
    assert(a);
    for(int i = 0;i < size;++i)
    {
        printf("%d ",a[i]);
    }
    cout<<endl;
}
#include <iostream>
using namespace std;
#include "Sort.h"


void Test()
{
    int a[10] = {2,4,3,8,5,1,6,7,9,0};
    //InsertSort(a,10);
    //ShellSort(a,10);
    //SelectionSort(a,10);
    HeapSort(a,10);
    Print(a,10);
}
int main()
{
    Test();
    return 0;
}