O(N^2)冒泡排序、選擇排序、插入排序
亞二次時(shí)間復(fù)雜度--希爾排序
O(NlogN)歸并排序、快速排序、堆排序
非比較排序：計(jì)數(shù)排序、桶排序、基數(shù)排序

#include <stdio.h>
#include <stdlib.h>

void Print(int* a, int l, int r)
{
    for (int i = l; i <= r; ++i){
        printf("%3d", a[i]);
    }
    printf("\n");
}

void Swap(int* a, int i, int j)
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

void NormalSort(int* a, int l, int r)
{
    int len = r - l + 1;
    for (int i = 0; i < len; ++i){
        for (int j = i+1; j < len; ++j){
            if (a[i] > a[j]) Swap(a, i, j);
        }
    }
}

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

void SelectionSort(int* a, int l, int r)
{
    int len = r - l + 1;
    for (int i = 0; i < len; ++i){
        int min = i;
        for (int j = i+1; j < len; ++j){
            if (a[min] > a[j]) min = j;
        }
        Swap(a, i, min);
    }
}

void Insertion(int* a, int s)
{
    int tmp = a[s], j = 0;
    for (j = s; (j > 0) && (tmp < a[j-1]); --j){
        a[j] = a[j-1];
    }
    a[j] = tmp;
}

void InsertionSort2(int* a, int s, int t)
{
    if(s > t) return;

    Insertion(a, s);
    InsertionSort2(a,  s+1,  t);
}

void InsertionSort(int* a, int l, int r)
{
    int len = r - l + 1, j;
    for (int i = 1; i < len; ++i){
        int tmp = a[i];
        for (j = i; (j > 0) && (tmp < a[j-1]); --j){
            a[j] = a[j-1];
        }
        a[j] = tmp;
    }
}

void Shell(int* a, int h, int len)
{
    int j = 0;
    for (int i = h; i < len; ++i){
        int tmp = a[i];
        for (j = i; (j >= h) && (tmp < a[j-h]); j-=h){
            a[j] = a[j-h];
        }
        a[j] = tmp;
    }
}

void ShellSort(int* a, int l, int r)
{
    int len = r - l + 1, h = 1, j;

    for(h = len/3; h > 0; h/=3){
        Shell(a, h, len);
        Print(a, l, r);
    }
}

int main()
{
    int arr[]={3, 4, 5, 6, 24, 13, 26, 1, 2, 27, 38, 15};
    //int arr[]={5};
    int size = sizeof(arr) / sizeof(int);
    //NormalSort(arr, 0, size-1);
    //BubbleSort(arr, 0, size-1);
    //SelectionSort(arr, 0, size-1);
    //InsertionSort(arr, 0, size-1);
    //InsertionSort2(arr, 0, size-1);
    //MergeSort(arr, 0, size-1);
    //QuickSort(arr, 0, size-1);
    //Print(arr, 0, size-1);
    ShellSort(arr, 0, size-1);
    Print(arr, 0, size-1);
    return 0;
}