常见排序算法

希尔排序，快速排序，堆排序，2路归并算法的c++简单实现

#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;

//对数列做一趟增量为d的希尔插入排序
void shellInsert(int *list, int length, int d)
{
    for (int i = d; i < length; i++)
    {
        //间隔为d的插入排序
        if (list[i] < list[i - d])
        {
            int temp = list[i];
            int j;
            //向左查找最终插入位置，查找的同时顺便右搬数据
            for (j = i - d; j >= 0 && temp < list[j]; j -= d)
                list[j + d] = list[j];
            list[j + d] = temp;
        }
    }
}

//希尔排序（升序）
void shellSort(int *list, int length)
{
    //以{2^n-1}为增量序列
    for (int d = 1 << (int)log2(length); d >= 2; d >>= 1)
        shellInsert(list, length, d - 1);
}

//快速排序（升序）
void quickSort(int *list, int length)
{
    if (length <= 1) return;
    //随机选取信标
    int pivot = list[rand() % length];
    int i = 0, j = length - 1;
    while (i != j)
    {
        while (i != j && list[i] < pivot) 
            i++;
        while (i != j && list[j] >= pivot)
            j--;
        swap(list[i], list[j]);
    }
    quickSort(list, i);
    quickSort(list + i, length - i);
}

//堆排序（升序）
void heapSort(int *list, int length)
{
    int heap[length + 1] = {0};
    //建堆
    for (int i = 1; i <= length; i++)
    {
        heap[i] = list[i - 1];
        for (int j = i; j > 1 && heap[j] < heap[j / 2]; j /= 2)
            swap(heap[j], heap[j / 2]);
    }
    //弹出，重调整
    for (int i = 0, j = length; i < length; i++, j--)
    {
        list[i] = heap[1];
        swap(heap[1], heap[j]);
        for (int k = 2; k < j; k *= 2)
        {
            //从2个孩子（或只有1个孩子）中选取最小的那个去比较
            if (k + 1 < j && heap[k + 1] < heap[k])
                k = k + 1;
            if (heap[k] < heap[k / 2])
                swap(heap[k], heap[k / 2]);
            else
                break;
        }
    }
}

//2路归并排序（升序）
void mergeSort(int *list, int length)
{
    if (length <= 1)
        return;
    int mid = length / 2;
    mergeSort(list, mid);
    mergeSort(list + mid, length - mid);
    //2路归并
    int tempList[length];
    int i = 0, j = mid, k = 0;
    while (k < length)
    {
        if (j >= length || (i < mid && list[i] < list[j]))
            tempList[k++] = list[i++];
        if (i >= mid || (j < length && list[j] < list[i]))
            tempList[k++] = list[j++];
    }
    for (k = 0; k < length; k++)
        list[k] = tempList[k];
}

int main()
{
    //初始化数列
    int length;
    cin >> length;

    int *list = new int[length];
    for (int i = 0; i < length; i++)
        list[i] = i;

    //随机洗切数列
    srand(time(0));
    for (int i = length - 1; i > 0; i--)
        swap(list[i], list[rand() % i]);

    //打印排序前数列
    for (int i = 0; i < length; i++)
        cout << list[i] << " ";
    cout << endl;

    //shellSort(list, length);
    //quickSort(list, length);
    //heapSort(list, length);
    mergeSort(list, length);

    //打印排序后数列
    for (int i = 0; i < length; i++)
        cout << list[i] << " ";
    cout << endl;
}

运行结果
在int main()里面写了一个随机数列生成，可以快速验证算法的正确性

欢迎友好交流