七大排序算法-西湖歌舞几时休

这里的七大指的是快速排序、堆排序、归并排序、希尔排序、选择排序、插入排序和冒泡排序，由于桶排序应用场景有限，这里就不写了。先对比一下这几种排序的效率：

观察表发现一个有趣的现象：对于堆排序和归并排序，他们的最好、最坏和平均的时间复杂度都是O(nlogn)，也就是说数据的初始化顺序对这两种算法是没有影响的。先来一个直观的比较（500000条数据）

直观来看，快速排序、堆排序和归并排序的时间在一个数量级上，接着是希尔排序，最后是插入排序、选择排序和冒泡排序。至于排序原理我就不再说了，直接贴代码。

//快速排序   
int Paration(int a[], int low, int high)   
{   
    int key = a[low];   
    while ( low < high )   
    {   
        while (low < high && a[high] >= key ) high--;   
        a[low] = a[high];

        while (low < high && a[low] <= key ) low++;   
        a[high] = a[low];          
    }   
    a[low] = key;   
    return low;   
}   
void QuickSort(int a[], int low, int high)   
{   
    if ( low < high )   
    {   
        int index = Paration(a, low, high);   
        QuickSort(a, low, index - 1);   
        QuickSort(a, index + 1, high);   
    }   
}

调用：QuickSort(a, 0, N - 1);

//堆排序   
void HeapAdjust(int a[], int n, int k)   
{   
    int l = 2 * k + 1;   
    int r = 2 * k + 2;   
   
    if ( l >= n && r >= n ) return;   
   
    int key = a[k];   
    int left = 0x80000000;   
    int right = 0x80000000;   
       
    if ( l < n ) left  = a[l];   
    if ( r < n ) right = a[r];   
    if ( key >= left && key >= right ) return;   
   
    if ( left > right )   
    {   
        a[k] = a[l];   
        a[l] = key;   
        HeapAdjust(a, n, l );   
    }   
    else   
    {   
        a[k] = a[r];   
        a[r] = key;   
        HeapAdjust(a, n, r);   
    }   
}   
   
void HeapSort(int a[], int n)   
{   
    //初始化堆的时候是对所有的非叶子结点进行筛选。 
    //最后一个非终端元素的下标是[n/2]向下取整，所以筛选只需要从第[n/2]向下取整个元素开始，从后往前进行调整。 
    for ( int i = ( n - 1 ) / 2; i >= 0; --i )    
    {   
        HeapAdjust(a, n, i);   
    }   
    while ( n )   
    {   
        int t = a[0];   
        a[0] = a[n-1];   
        a[n-1] = t;   
        n -= 1;   
        HeapAdjust(a, n, 0);   
    }   
}

调用：HeapSort(a, N);

//归并排序   
void Merage(int a[], int low, int mid, int high, int tmp[])   
{   
    int len1 = mid - low + 1;   
    int len2 = high - mid;   
    memcpy(tmp, a + low, len1 * sizeof(int));   
    memcpy(tmp + len1, a + mid + 1, len2 * sizeof(int));   
       
    int index = low;   
    int i = 0;   
    int j = len1;   
    while ( i < len1 && j < len1 + len2 )   
    {   
        if (tmp[i] < tmp[j])   
        {   
            a[index++] = tmp[i++];   
        }   
        else   
        {   
            a[index++] = tmp[j++];   
        }   
    }   
    while ( i < len1 )        a[index++] = tmp[i++];   
    while ( j < len1 + len2 ) a[index++] = tmp[j++];   
}   
   
void MergeSort(int a[], int low, int high)   
{   
    static int *tmp = new int[high];   
    if ( low < high )   
    {   
        int mid = (low + high) / 2;   
        MergeSort(a, low, mid);   
        MergeSort(a, mid + 1, high);   
        Merage(a, low, mid, high, tmp);   
    }   
}

调用：MergeSort(a, 0, N - 1);

//希尔排序   
void ShellSort(int a[], int n)   
{   
    int step[] = {37, 31, 23, 19, 17, 13, 11, 7, 3, 1}; //步长   
    for ( int k = 0; k < 10; ++k )   
    {   
        for (int i = step[k]; i < n; ++i )   
        {   
            int t = a[i];   
            int j = i - step[k];   
            for ( ; j >= 0 && t < a[j]; j -= step[k] )   
            {   
                a[j + step[k]] = a[j];   
            }   
            a[j + step[k]] = t;   
        }   
    }   
}

调用：ShellSort(a, N);

//插入排序   
void InsertSort(int a[], int n)   
{   
    for ( int i = 1; i < n; ++i )   
    {   
        int t = a[i];   
        int j = i - 1;   
        for ( ; j >= 0 && t < a[j]; --j )   
        {   
                a[j + 1] = a[j];   
        }   
        a[j+1] = t;   
    }   
}

调用：InsertSort(a, N); 有没有发现希尔排序和插入排序很像，其实希尔排序就是插入排序，只不过步长不是1。

//选择排序   
void SelectSort(int a[], int n)   
{   
    for ( int i = 0; i < n; ++i )   
    {   
        int min = a[i];   
        int index = i;   
        for ( int j = i + 1; j < n; ++j )   
        {   
            if (a[j] < min )   
            {   
                index = j;   
                min = a[j];   
            }   
        }   
        a[index] = a[i];   
        a[i] = min;   
    }   
}

调用：SelectSort(a, N);

//冒泡排序   
void BubbleSort(int a[], int n)   
{   
    for (int i = 0; i < n; ++i)   
    {   
        for ( int j = 0; j < n - i - 1; ++j)   
        {   
            if ( a[j] > a[j+1] )   
            {   
                int t = a[j];   
                a[j] = a[j+1];   
                a[j+1] = t;   
            }   
        }   
    }   
}

调用：BubbleSort(a, N);

有没有发现，代码越简单的效率越低。需要注意的是在上面的写法中，调用快速排序和归并排序时，传入的参数数最后一个元素的下标，而不是数组的大小，就是说N - 1。