常见排序算法

template<typename T>
bool cmp(T a, T b)
{
    return a < b;
}

template<typename T>
void exchange(T* a, T* b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

template<typename T>
T GetMax(T* arr, int len)
{
    T ans = arr[0];
    for (int i = 1; i < len; i++)if(cmp(ans,arr[i]))ans=arr[i];
    return ans;
}

这3个基础函数，可以用于各排序算法中。

（2）约定接口

基于比较的排序算法写成泛型接口，提供2个接口版本，即cmp函数指针可以省略

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
}

template<typename T>
void Sort(T* arr, int len)
{
    Sort(arr,len,cmp);
}

基于计算的排序算法直接以int类型作为排序对象类型，以普通小于作为比较函数

void Sort(int* arr, int len)
{
    
}

（3）排序功能测试

搭建一个简单的评测系统，用来判断排序算法是否完成了功能：

#include <iostream>
using namespace std;


int main() {
    const int N = 1000;
    int arr[N];
    for (int i = 0; i < N; i++)arr[i] = rand()%10000;
    Sort(arr, N);
    for (int i = 0; i < N - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            cout << "error! arr[i] = " << arr[i] << ", arr[i+1] = " << arr[i + 1] << endl;
        }
    }
    cout << "end";
    return 0;
}

然后就可以开始写排序算法了。

（4）排序稳定性测试

struct Node {
	int a;
	int b;
	bool operator<(const Node &x) const{
		return a < x.a;
	}
};
template<typename T>
void StableSort(T* arr, int len, bool(*cmp)(T a, T b))
{
	for (int i = 1; i < len; i++) {
		for (int j = i; j > 0; j--) {
			if (cmp(arr[j], arr[j - 1]))exchange(arr + j, arr + j - 1);
			else break;
		}
	}
}
template<typename T>
void StableSort(T* arr, int len)
{
	StableSort(arr, len, cmp);
}
void testStable()
{
	const int N = 12345;
	Node arr[N];
	Node arr2[N];
	for (int i = 0; i < N; i++)arr[i].a = rand() % 1000, arr[i].b = rand(), arr2[i] = arr[i];
	Sort(arr, N);
	StableSort(arr2, N);
	bool flag = true;
	for (int i = 0; i < N; i++)if (arr[i].b != arr2[i].b)flag = false;
	if (flag)cout << "is stable.";
	else cout << "not stable";
}

3，常见排序算法

（1）插入排序

算法思路：先让前i个元素是有序的，然后插入一个元素，让前i+1个元素是有序的。

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    for(int i=1; i<len; i++){
        for(int j=i; j>0; j--){
            if(cmp(arr[j], arr[j-1]))exchange(arr+j, arr+j-1);
            else break;
        }
    }
}

最坏时间：O（n^2）

平均时间：O（n^2）

稳定性测试结果：稳定

PS：插入排序的时间其实就是Θ（n+逆序对的数目）

（2）选择排序

算法思路：选择未排序的所有元素中的最小元素，直接放到已排序的这一段的后面。

template<typename T>
int getMinId(T* arr, int len, bool(*cmp)(T a, T b))
{
    int ans=0;
    for(int i=1;i<len;i++){
        if(cmp(arr[i], arr[ans]))ans=i;
    }
    return ans;
}

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    for(int i=0; i<len; i++){
        int minId = getMinId(arr+i, len-i, cmp);
        exchange(arr+i, arr+i+minId);
    }
}

最坏时间：O（n^2）

平均时间：O（n^2）

稳定性测试结果：不稳定

（3）冒泡排序

算法思路：先把n个元素依次扫描一遍，相邻俩元素排序一下，扫描完之后最大元素就会出现在最后的位置，

然后再扫描前n-1个元素...依次类推

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    for(int i=len-1; i>0; i--){
        for(int j=0;j<i;j++){
            if(cmp(arr[j+1], arr[j]))exchange(arr+j+1, arr+j);
        }
    }
}

最坏时间：O（n^2）

平均时间：O（n^2）

稳定性测试结果：稳定

或者对称的写法：

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
	for (int i = 0; i < len; i++) {
		for (int j = len - 1; j > i; j--) {
			if (cmp(arr[j], arr[j - 1]))exchange(arr + j - 1, arr + j);
		}
	}
}

时间复杂度和稳定性不变

（4）双向冒泡排序

也叫鸡尾酒排序，就是把2个方向的冒泡排序结合一下。

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
	for (int low = 0, high = len - 1; low < high; low++, high--) {
		for (int j = high; j > low; j--) {
			if (cmp(arr[j], arr[j - 1]))exchange(arr + j - 1, arr + j);
		}
		for (int j = low; j < high; j++) {
			if (cmp(arr[j + 1], arr[j]))exchange(arr + j + 1, arr + j);
		}
	}
}

最坏时间：O（n^2）

平均时间：O（n^2）

稳定性测试结果：稳定

（5）归并排序

归并排序主要是Merge操作和递归操作。

template<typename T>
void Merge(T* arr1, int len1, T* arr2, int len2, bool(*cmp)(T a, T b))
{
    T* arr = new T[len1 + len2];
    int i, j;
    for (i = 0, j = 0; i < len1 && j < len2;) {
        if (cmp(arr2[j], arr1[i]))*arr = arr2[j++];
        else *arr = arr1[i++];
        arr++;
    }
    while(i<len1)*(arr++) = arr1[i++];
    while(j<len2)*(arr++) = arr2[j++];
    arr -= len1 + len2;
    for (int i = 0; i < len1 + len2; i++)arr1[i] = arr[i];
}

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    if (len <= 1)return;
    Sort(arr, len / 2, cmp);
    Sort(arr + len / 2, len - len / 2, cmp);
    Merge(arr, len / 2, arr + len / 2, len - len / 2, cmp);
}

最坏时间：O（nlogn）

平均时间：O（nlogn）

稳定性测试结果：稳定

Merge操作合并2个数组的过程中，包含至多len次cmp操作和2*len次赋值操作，其中len=len1+len2表示2个数组的长度和

（6）堆排序

代码来自：二叉堆、堆排序_nameofcsdn的博客-CSDN博客

int LeftChild(int id)
{
	return id * 2 + 1;
}
int RightChild(int id)
{
	return id * 2 + 2;
}

template<typename T>
void AdjustHeap(T* arr, int rootId, int size, bool(*cmp)(T a, T b))
{
    int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
    if (left < size && cmp(arr[largest], arr[left]))largest = left;
    if (right < size && cmp(arr[largest], arr[right]))largest = right;
    if (largest == rootId)return;
    exchange(arr + rootId, arr + largest);
    AdjustHeap(arr, largest, size, cmp);
}
template<typename T>
void InitHeap(T* arr, int size, bool(*cmp)(T a, T b))
{
    for (int i = size / 2; i >= 0; i--)AdjustHeap(arr, i, size, cmp);
}
template<typename T>
void Sort(T* arr, int size, bool(*cmp)(T a, T b))
{
    InitHeap(arr, size, cmp);
    for (int i = size - 1; i > 0; i--) {
        exchange(arr + i, arr);
        AdjustHeap(arr, 0, i, cmp);
    }
}

最坏时间：O（n log n）

平均时间：O（n log n）

稳定性测试结果：不稳定

（7）快速排序

不稳定版：

template<typename T>
void Sort(T* arr, int low, int high, bool(*cmp)(T a, T b))
{
	if (low >= high)return;
	T x = arr[high];
	int id = high;
	for (int i = low; i < id;) {
		if (cmp(arr[i], x))i++;
		else exchange(arr + i, arr + id--);
	}
	arr[id] = x;
	Sort(arr, low, id - 1,cmp);
	Sort(arr, id + 1, high, cmp);
}
template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
	Sort(arr, 0, len - 1, cmp);
}

最坏时间：O（n^2）

平均时间：O（n log n）

稳定性测试结果：不稳定

稳定版：

template<typename T>
void Sort(T* arr, T* arr2, int low, int high, bool(*cmp)(T a, T b))
{
	if (low >= high)return;
	int id = low, id2, id3;
	T x = arr[high];
	for (int i = low; i < high; i++) {
		if (cmp(arr[i], arr[high]))arr2[id++] = arr[i];
	}
	id2 = id;
	for (int i = low; i < high; i++) {
		if (!cmp(arr[i], arr[high]) && !cmp(arr[high], arr[i]))arr2[id++] = arr[i];
	}
	arr2[id++] = x;
	id3 = id;
	for (int i = low; i < high; i++) {
		if (cmp(arr[high], arr[i]))arr2[id++] = arr[i];
	}
	for (int i = low; i <= high; i++)arr[i] = arr2[i];
	Sort(arr, arr2, low, id2 - 1, cmp);
	Sort(arr, arr2, id3, high, cmp);
}
template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
	T* arr2 = new T[len];
	Sort(arr, arr2, 0, len - 1, cmp);
}

最坏时间：O（n^2）

平均时间：O（n log n）

稳定性测试结果：稳定

（8）基数排序

适应场景：假设排序对象全是自然数

void Sort(int* arr, int len, int key)
{
    int** p = new int*[10];
    for(int i=0;i<10;i++)p[i]=new int[len];
    int num[10]={0};
    for(int i=0;i<len;i++){
        int val = arr[i]/key%10;
        p[val][num[val]++] = arr[i];
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<num[i];j++)*(arr++)=p[i][j];
    }
}

void Sort(int* arr, int len)
{
    int m = GetMax(arr,len);
    for(int key=1;key<=m;key*=10){
        Sort(arr,len,key);
    }
}

最坏时间：O（kn），其中k是最大自然数的10进制的位数

平均时间：O（kn）

稳定性测试结果：用上面的测试代码测不了，实际上是不稳定。

怎么理解这个时间复杂度呢？

从一个角度看，k不会超过10，所以可以理解为O（n）但是常数比较大。

从另外一个角度看，在很多场景下，最大数的数值是比n要大的，那么kn实际上比nlogn还大。

总之，无论如何都有一个共识，虽然看似是O（n）的复杂度，但是常数很大，很多时候很慢。

如果是像我代码这样，每次都要new，那就更慢了，这一步可以优化，但是优化完也比其他很多排序算法慢。

（9）计数排序

适应场景：假设排序对象全是自然数，而且最大数不会太大

void Sort(int* arr, int len)
{
    int m = GetMax(arr, len);
    int* pnum = new int[m + 1];
    for (int i = 0; i <= m; i++)pnum[i] = 0;
    for (int i = 0; i < len; i++)pnum[arr[i]]++;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j < pnum[i]; j++)*(arr++) = i;
    }
}

最坏时间：O（m+n），其中m是最大自然数

平均时间：O（m+n）

稳定性测试结果：用上面的测试代码测不了，实际上是不稳定。

（10）桶排序

算法思路：先把所有数分成若干个桶，然后每个桶调用别的排序算法进行排序，组装起来就是完整的排序了。

适用场景：待排序元素都是实数，但是这里我们用都是自然数为例来实现代码。

void Sort(int* arr, int len)
{
    int m = GetMax(arr, len);
    const int T = 10; //大于1的任何数都行
    int gap = m / T + 1; //桶的范围大小
    int num[T] = { 0 };
    for (int i = 0; i < len; i++)num[arr[i] / gap]++;
    int id[T] = { 0 };
    for (int i = 1; i < T; i++)id[i] = id[i - 1] + num[i - 1];
    int* p = new int[len];
    for (int i = 0; i < len; i++)p[id[arr[i] / gap]++] = arr[i];
    int s = 0;
    for (int i = 0; i < T; i++) {
        Sort2(p + s, num[i]);
        s += num[i];
    }
    for (int i = 0; i < len; i++)arr[i] = *(p++);
}

其中的sort2是调用别的排序算法，比如算法导论中提到的是插入排序，

甚至这个函数可以改一改，调用本身递归也是可以完成排序的（只针对整数的情况，对实数没法完成排序），这样其实就基本和基数排序一样了，只不过顺序反过来的，

基数排序是先按照低位（个位）排一次，然后再高位排，这里如果调用自身完全排序，那就是先按照高位排，然后再低位排。

我这里是用计数的方法，用一个数组p依次存下了所有的桶，实际上用链表或者vector来存这些桶更方便。

之所以选择插入排序是因为，插入排序在对几乎已经排好序的数据操作时效率高。

如果分桶之后嵌套的是插入排序，那么时间复杂度是：

最坏时间：O（n^2）

平均时间：O（n + n^2 / T）其中T是桶的数量，当T=n时，平均时间是O（n）

这个平均时间的计算比较复杂，算法导论上是用指示器随机变量来算的。

（11）希尔排序

参考下文

（12）近似计数排序

计数排序只能处理整数的情况，如果用关联容器，可以处理更多的类型。

template<typename T>
class fun
{
public:
    bool operator()(T a, T b) const
    {
        return cmp(a,b);
    }
};

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    map<T, int, fun<T>>m;
    for (int i = 0; i < len; i++)m[arr[i]]++;
    for (auto& it : m) {
        for (int j = 0; j < it.second; j++) *(arr++) = it.first;
    }
}

把cmp函数封装成了函数对象。

耗时主要在map的插入操作，log1 + log2 + log3 + ... + logn = n logn

所以时间复杂度是O（n logn）

二，希尔排序

1，希尔排序

希尔排序是一种逐步调整，让整个数组越来越有序，最终完全排序的算法。

和桶排序的思想比较接近，也是先分组，然后组内嵌套调用其他排序算法

希尔排序是根据间隔d，把间隔为d的元素都划分到一个组内，即根据下标mod d的同余系进行分组，组内调用其他排序算法。

刚开始d很大，然后逐渐减小，最后一次d=1，因为d=1的时候调用了其他排序算法，所以肯定是完成了排序任务的。

2，希尔排序的实现

按照希尔排序的步骤，很容易就产生一个疑问，既然希尔排序的最后一趟就是一次完整的简单排序，那希尔排序相对于简单排序而言还有什么优势呢？

Shell sort can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort)

如果是内嵌插入排序，主要好处是时间复杂度可能是低于插入排序的（取决于间隔序列）。

如果是内嵌冒泡排序，主要好处是比冒泡本身的交换次数少一些。

代码实现：

template<typename T>
void Sort(T* arr, int len, bool(*cmp)(T a, T b))
{
    vector<int> vd = getd(len); //获取间隔序列
    for (auto d:vd) {
        Sort(arr, len, d, cmp); //间隔式排序
    }
}

希尔排序框架的代码是固定的，所以下面还需要讨论的是：

（1）内嵌排序

void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b)) //间隔式排序

要么是插入排序，要么是冒泡排序

（2）获取间隔序列

vector<int> getd(int len)

获取一个递减的间隔序列，最后一个一定是1

当我们描述希尔排序的间隔序列时，既可以递增描述，如1,2,4,8，也可以递减描述，8,4,2,1，因为希尔排序的步骤是明确是，一定是按照递减的间隔序列依次调用内嵌排序。

3，内嵌冒泡的希尔排序

（1）排序网络

内嵌冒泡排序的希尔排序有排序网络，以8个元素为例，如果采用原始序列d=4,2,1，那么排序网络如下：

PS：

如果n=8，那么采用原始的d=4,2,1这个序列是很不明智的选择，因为效率低。

（2）代码实现

template<typename T>
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b))  //间隔式冒泡排序
{
    for (int s = 0; s < d; s++) {
        for (int i = len - d; i > 0; i -= d) {
            for (int j = s; j < i; j += d) {
                if (cmp(arr[j + d], arr[j]))exchange(arr + j + d, arr + j);
            }
        }
    }
}

（3）交换次数对比

以1000个随机数的排序为例，冒泡排序的交换次数是257362

以500 250 125 62 31 15 7 3 1作为间隔序列，内嵌冒泡排序的希尔排序的总交换次数为7256

由此可见，内嵌冒泡的希尔排序比冒泡本身的交换次数明显要少。

PS:

我测试了一些，内嵌插入排序的希尔排序，交换次数和内嵌冒泡的希尔排序是一样的。

4，内嵌插入的希尔排序

（1）排序网络

内嵌插入排序的一般不是遗忘比较算法，没有排序网络。

（2）代码实现

template<typename T>
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b))  //间隔式插入排序
{
    for (int s = 0; s < d; s++) {
        for (int i = s + d; i < len; i += d) {
            for (int j = i; j > s; j -= d) {
                if (cmp(arr[j], arr[j - d]))exchange(arr + j, arr + j - d);
                else break;
            }
        }
    }
}

5，间隔序列、时间复杂度

对于内嵌冒泡的希尔排序，时间复杂度和冒泡相同。

对于内嵌插入排序的希尔排序，简单的分析来看，最坏时间复杂度是O（n^2），

但是精确分析的话还能提出各种更严格的渐进上确界，而且和间隔d的取值序列有关，比较复杂，至今仍然没有很好的解答。所以讨论时间复杂度默认指的都是内嵌插入排序。

本章来自 Shellsort - Wikipedia

Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

即这些序列分为2类，第一类是根据规模N的不同而略有差别，公式会直接给出整个递减序列，第二类是一个固定的无穷序列，使用时从中取出小于N的所有数，即得到适用于规模N的序列。

6，第一类序列

（1）Shell序列（原始序列）

$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$

最坏时间复杂度： $\theta(n^2)$ ，当n=2^k时是最坏情况。

When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N^2) comparisons in the worst case. For instance, this case occurs for N equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.

获取间隔序列：

vector<int> getd(int len)
{
	vector<int> ans;
	len /= 2;
	while (len) {
		ans.push_back(len);
		len /= 2;
	}
	return ans;
}

获取间隔序列本身所花的时间是log n，可忽略不计。

（2）Frank序列

${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1},k=1,2,3...$

最坏时间复杂度： $\Theta \left(N^{\frac {3}{2}}\right)$

证明参见Weiss的数据结构与算法分析一书。

证明过程用到一个引理：

对于任意一个数列和递减的间隔序列{a1,a2,...}，经过间隔为a1的排序之后，就是a1-有序的（即任何间隔为a1的2个数的顺序都是OK的），之后无论再经过多少ak排序之后，仍然是a1-有序的。

获取间隔序列：

vector<int> getd(int len)
{
	vector<int> ans;
	len /= 2;
	while (len) {
		len /= 2;
		ans.push_back(len * 2 + 1);
	}
	return ans;
}

获取间隔序列本身所花的时间是log n，可忽略不计。

7，第二类序列

第二类序列，都是固定序列，直接硬编码即可，不消耗时间。

static vector<int> ids = { 1,3,7,15 };
vector<int> getd(int len)
{
	vector<int> ans;
	for (auto vi : ids) {
		if (vi > len)break;
		ans.insert(ans.begin(), vi);
	}
	return ans;
}

第二类序列只需要硬编码static vector<int> ids = { 1,3,7,15 };这一行即可，其他代码不变。

甚至，这些都不用自己算一遍，维基百科里面有各个序列的在The On-Line Encyclopedia of Integer Sequences® (OEIS®)的网址，直接复制过来就行。

（1）Hibbard序列

2^k - 1

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295

最坏时间复杂度：同上

（2）Papernov序列

2^k + 1

1, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825, 2147483649

最坏时间复杂度：同上

（3）Pratt序列

3-smooth numbers，即所有素因子都不超过3的那些数

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888

如果一个序列既是2k-有序的，又是3k-有序的，那么在进行以k为间隔的插入排序时，每个元素最多只需要和前面一个数比较一次即可。

所以对于这个间隔序列采用插入排序，每一趟排序中的每个数只需要与前面的数比较一次（插入就会停止），所以这个特定的希尔排序也可以用排序网络描述：

对于这个特定序列，间隔式插入排序可以简化成：

template<typename T>
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b))
{
	for (int s = 0; s < d; s++) {
		for (int i = s + d; i < len; i += d) {
			if (cmp(arr[i], arr[i - d]))exchange(arr + i, arr + i - d);
		}
	}
}

或者再化简成：

template<typename T>
void Sort(int* arr, int len, int d, bool(*cmp)(T a, T b)) 
{
	for (int i = d; i < len; i++) {
		if (cmp(arr[i], arr[i - d]))exchange(arr + i, arr + i - d);
	}
}

最坏时间复杂度： $\Theta \left(N\log ^{2}N\right)$

（4）Knuth序列

(3^k-1)/2

1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200, 5230176601, 15690529804, 47071589413, 141214768240, 423644304721, 1270932914164

最坏时间复杂度： $N^{\frac {3}{2}}$

（5）Sedgewick序列

$4^{k}+3\cdot 2^{k-1}+1$

1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, 1050113, 4197377, 16783361, 67121153, 268460033, 1073790977, 4295065601, 17180065793, 68719869953, 274878693377, 1099513200641, 4398049656833, 17592192335873, 70368756760577

最坏时间复杂度： $N^{\frac {4}{3}}$

三，排序算法效率、组合嵌套

1，为什么嵌套

评价一个排序算法的时间效率，主要看最坏时间、平均时间、常数

比如归并排序的最坏时间是O（nlogn），但是常数大，插入排序的最坏时间是O（n^2），但是常数小，所以数组较小时用插入排序可能更快。

又比如快速排序的平均时间是同类算法中最快的，但是最坏时间是O（n^2）。

因为有这2种情况的存在，所以把两种及以上的排序算法进行组合嵌套，能达到更好的效果。

2，常见组合嵌套

桶排序、希尔排序，本身就是嵌套了其他排序算法的排序算法。

除此之外还有Timsort、pdqsort

3，Timsort

把归并排序和插入排序结合起来，就是Timsort

Timsort是稳定排序（归并和插入都是非稳定排序），且拥有和归并排序一样的最坏时间：O（nlogn）

Timsort的原理参考算法导论习题：

答：总时间是Θ（k^2）* n/k = Θ（nk）

答：上面提到，Merge操作合并2个数组的时间是Θ（len），其中len=len1+len2表示2个数组的长度和

n/k个数组需要log(n/k) / log2轮合并，每一轮的时间都是Θ（n），所以总时间是Θ（nlog(n/k)）

答：log n

答：这个主要就看各个常数了，这个比较复杂，不过k应该是不超过10的

4，pdqsort（pattern-defeating quicksort）

pdqsort是快速排序、堆排序、插入排序的组合，参考c++ sort

四，OJ实战

链表适合插入排序，统计逆序数适合归并排序。

力扣 147. 对链表进行插入排序（插入排序）

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路一：插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(!head)return NULL;
        ListNode* p=head;
        while(p && p->next){
            ListNode*pn=p->next;
            if(p->val<=pn->val){
                p=pn;
                continue;
            }
            p->next=pn->next;
            if(pn->val<head->val)pn->next=head,head=pn;
            else{
                ListNode* h =head;
                while(h->next->val<pn->val)h=h->next;
                pn->next=h->next,h->next=pn;
            }
        }
        return head;
    }
};

思路二：

直接调用我的ListSort函数模板：ACM模板

力扣 148. 排序链表（插入排序）

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

思路一：插入排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head)return NULL;
        ListNode* p=head;
        while(p && p->next){
            ListNode*pn=p->next;
            if(p->val<=pn->val){
                p=pn;
                continue;
            }
            p->next=pn->next;
            if(pn->val<head->val)pn->next=head,head=pn;
            else{
                ListNode* h =head;
                while(h->next->val<pn->val)h=h->next;
                pn->next=h->next,h->next=pn;
            }
        }
        return head;
    }
};

440 ms

思路二：归并排序

//把两个升序的链表合并为一个升序的链表
ListNode* mergeTwoUpLists(ListNode* p, ListNode* q) {
    if(!p)return q;
    if(!q)return p;
    ListNode *head;
    if(p->val < q->val)head=p,p=p->next;
    else head=q,q=q->next;
    ListNode *ans=head;
    while(p && q)
    {
        if(p->val < q->val)ans->next=p,ans=p,p=p->next;
        else ans->next=q,ans=q,q=q->next;
    }
    if(p)ans->next=p;
    else ans->next=q;
    return head;
}

class Solution {
public:
    ListNode* sortList(ListNode* head,int len) {
        if(len<2)return head;
        int k=len/2;
        ListNode* p=head;
        for(int i=0;i<k-1;i++)p=p->next;
        ListNode* p2=sortList(p->next,len-k);
        p->next=NULL;
        p=sortList(head,k);
        return mergeTwoUpLists(p,p2);
    }
    ListNode* sortList(ListNode* head) {
        int len=LinkGetLength(head);
        return sortList(head,len);
    }
};

132 ms

思路三：

直接调用我的ListSort函数模板：ACM模板

POJ 2299 Ultra-QuickSort（归并排序）

题目：

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4 ,Ultra-QuickSort produces the output 0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input

5
9
1
0
5
4
3
1
2
3
0
Sample Output

6
0

题意很好理解，输入一个数列，输出它的逆序数。

我的原始代码（超时）：

#include<iostream>
using namespace std;

int n;
int c[500005];
int num[500005];

int sum(int i)
{
	int s = 0;
	while (i)
	{
		s += c[i];
		i -= (i&(-i));
	}
	return s;
}

void add(int i, int x)
{
	while (i <= n)
	{
		c[i] += x;
		i += (i&(-i));
	}
}

int findmax()
{
	int max = 1;
	for (int j = 2; j <= n; j++)if (num[max] < num[j])max = j;
	return max;
}

int main()
{	
	ios_base::sync_with_stdio(false);
	long long s;
	while (cin >> n)
	{
		if (n == 0)break;
		for (int i = 1; i <= n; i++)
		{
			cin >> num[i];
			c[i] = 0;
		}
		s = 0;
		for (int i = 1; i <= n; i++)
		{
			int j = findmax();
			num[j] = -1;
			s += sum(j);
			add(j, 1);
		}
		cout << s << endl;
	}
	return 0;
}

很明显它的时间是n*n，所以超时了。

但是好在思路差的不是很多，稍微改了下就对了。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
 
struct node
{
	int num;
	int index;
};
 
int n;
int c[500005];
node nod[500005];
 
bool cmp(node a, node b)
{
	return a.num > b.num;
}
 
int sum(int i)
{
	int s = 0;
	while (i)
	{
		s += c[i];
		i -= (i&(-i));
	}
	return s;
}
 
void add(int i, int x)
{
	while (i <= n)
	{
		c[i] += x;
		i += (i&(-i));
	}
}
 
int main()
{	
	ios_base::sync_with_stdio(false);
	long long s;
	while (cin >> n)
	{
		if (n == 0)break;
		for (int i = 1; i <= n; i++)
		{
			cin >> nod[i].num;
			nod[i].index = i;
			c[i] = 0;
		}
		s = 0;
		sort(nod + 1, nod + 1 + n, cmp);
		for (int i = 1; i <= n; i++)
		{
			int j = nod[i].index;
			s += sum(j);
			add(j, 1);
		}
		cout << s << endl;
	}
	return 0;
}

这个虽然过了，但是很慢，我猜想手写快速排序或者归并排序应该会比较快。

普通的归并排序，只需要加一句sum += mid - i + 1;就可以变成边排序边统计逆序数。

代码：

#include<iostream>
using namespace std;
 
int n;
long long sum;
int num[500005];
int copynum[500005];
 
void merge(int low, int high)
{
	int mid = (low + high) / 2;
	int i = low, j = mid + 1, k = low;
	while (i <= mid && j <= high)
	{
		if (num[i] < num[j])copynum[k++] = num[i++];
		else
		{
			copynum[k++] = num[j++];
			sum += mid - i + 1;
		}
	}
	while (i <= mid)copynum[k++] = num[i++];
	while (j <= high)copynum[k++] = num[j++];
	for (int i = low; i <= high; i++)num[i] = copynum[i];
}
 
void sort(int low, int high)
{
	if (low == high)return;
	int mid = (low + high) / 2;
	sort(low, mid);
	sort(mid + 1, high);
	merge(low, high);
}
 
int main()
{	
	ios_base::sync_with_stdio(false);
	while (cin >> n)
	{
		if (n == 0)break;
		for (int i = 1; i <= n; i++)cin >> num[i];
		sum = 0;
		sort(1, n);
		cout << sum << endl;
	}
	return 0;
}