关于常规排序算法的比较实验

一、实验结果

实验说明：在逆序的情况下，模拟部分算法的最坏情况。如有错误望指正。
实验环境：Windows，x86 Release，单线程
实验结果：

实验数据长度	效率关系
大于8200	快排 > 归并 > 插入排序（二叉） > 插入排序（普通）> 冒泡排序
大于7600，小于8000	快排 ≈ 归并 > 插入排序（二叉） > 插入排序（普通） > 冒泡排序
大于2500，小于7600	快排 ≈ 归并 ≈ 插入排序（二叉） > 插入排序（普通） > 冒泡排序
大于1800，小于2500	快排 ≈ 归并 ≈ 插入排序（二叉） ≈ 插入排序（普通） > 冒泡排序
小于1800	快排 ≈ 归并 ≈ 插入排序（二叉） ≈ 插入排序（普通） ≈ 冒泡排序

可以发现，在随着数组数量的减少，各排序算法的时间复杂度逐渐相同。
所以在数量少时，使用最简单的冒泡排序或插入排序（普通）就足以。

排序算法的用时结果_总览 排序算法的用时结果_细节.png

二、排序算法

• 冒泡排序
• 插入排序（普通的、使用二叉查找的）
• 归并排序
• 快速排序

2.1 冒泡排序

算法思路：从数组的结尾往头部“冒泡”。每一步都将优先级高的值移至前位。
最坏时间复杂度：O(n^2)
最优时间复杂度：O(n^2)
空间复杂度：O(1)

void Sort::bubbleSort(int A[], int length, Cmp cmp)
{
    for (int i = 0; i < length; ++i)
        for (int j = length - 1; j > i; --j)
            if (cmp(A[j], A[j - 1]))
                swap(A[j], A[j - 1]);
}

2.2 插入排序

2.2.1 普通的

算法思路：数组的前i个数为有序的，第i+1位数插入前i个有序数列种。
最坏时间复杂度：O(n^2)
最优时间复杂度：O(n)
空间复杂度：O(1)

template<class Cmp>
void Sort::insertionSort(int A[], int length, Cmp cmp) {
    for (int i = 1; i < length; i++) {
        const int key = A[i];
        int j;
        for (j = i - 1; j >= 0 && cmp(key, A[i]); j--)
            A[j + 1] = A[j];
        A[j + 1] = key;
    }
}

2.2.2 使用二叉查找的

算法思路：数组的前i个数为有序的，因为前i个数为有序的，所以可以使用二叉查找，找到位置，再插入。
最坏时间复杂度：优于O(n^2)
最优时间复杂度：O(n)
空间复杂度：O(1)
void Sort::insertionSortWithBS(int A[], int length) {
    for (int i = 1; i < length; i++) {
        int key = A[i];
        int j = binarySearch(A, 0, i - 1, key);
        memcpy(A + j + 1, A + j, sizeof(int)*(i - j));
        A[j] = key;
    }
}

2.3 归并排序

算法思路：将长度为n的数组，分为n组，每次迭代都将相邻两组进行合并。一共迭代log(n)次。
最坏时间复杂度：O(nlog(n))
最优时间复杂度：O(nlog(n))
空间复杂度：O(n)

// 融合数组 [p, q]，[q+1, r]
void Sort::merge(int A[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int* L = new int[n1 + 1];
    int* R = new int[n2 + 1];
    memcpy(L + 1, A + p, sizeof(int)*n1);
    memcpy(R + 1, A + q + 1, sizeof(int)*n2);
    R[0] = L[0] = numeric_limits<int>::min();
    for (int i = r; i >= p; i--) {
        if (L[n1] > R[n2]) {
            A[i] = L[n1--];
        }
        else {
            A[i] = R[n2--];
        }
    }
    delete[] L;
    delete[] R;
}
//
// 归并排序
//
void Sort::mergeSort(int A[], int count, int begin) {
    if (count == 1)
        return;
    int half = count / 2;
    mergeSort(A, half, begin);
    mergeSort(A, count - half, begin + half);
    merge(A, begin, begin + half - 1, begin + count - 1);
}

2.4 快速排序

算法思路：在数组种随机找到一个数，然后将优先级高的移至左边，优先级低的移至右边
最坏时间复杂度：O(n^2)（发生的概率十分低，可以忽略不记）
最优时间复杂度：O(nlog(n))
空间复杂度：O(1)

//
// 随机快排
//        使用左右指针的方式
template<class Cmp>
void Sort::quickSort(int nums[], int s, int e, Cmp cmp) {
    if (e - s <= 1) return;
    int randomI = rand() % (e - s) + s;
    swap(nums[s], nums[randomI]);
    bool right = true;
    int i, j;
    for (i = s, j = e - 1; i < j;) {
        if (cmp(nums[j], nums[i])) {
            swap(nums[j], nums[i]);
            if (right) ++i; else --j;
            right = !right;
        }
        else {
            if (right) --j; else ++i;
        }
    }
    quickSort(nums, s, i, cmp);
    quickSort(nums, i + 1, e, cmp);
}