转载

数据结构和算法（四）：主流内排序算法

数据结构中通用的算法主要涉及查找和排序。查找操作基本依赖于数据组织的方式(顺序存储、链表存储、树存储等)，主流的有顺序查找、折半查找、插值查找、散列查找等，其操作比较的简单明了；而排序算法算是算法中最热门的讨论话题，算法的考察要点包括对时间、空间的需求及排序的稳定性等。当然，C++标准库中已经封装了大量的容器类以及find、sort、stable_sort等通用算法，工程开发中直接传入迭代器参数就可以使用了。

一、基础知识

1.1 排序的分类

(1). 排序的稳定性：

在排序中如果主关键字一致，对于假设ki=kj(i≠j)，在排序前序列中ri领先于rj(即i<j)，如果排序后ri仍领先于rj，则称排序方法是稳定的；反之，若可能(但不一定)排序后的序列中rj领先ri，也就是关键码相同的记录，经过排序后这些记录的相对次序仍然保持不变，则称排序方法是不稳定的。

(2). 内排序(Internal Sort)和外排序(External Sort)：

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中；外排序是由于排序个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。后面可知，归并排序可以处理外排序问题。

(3). 按照算法的原理分类

a. 插入排序：直接插入排序、二分插入排序、希尔排序

b. 交换排序：冒泡排序、鸡尾酒排序、快速排序

c. 选择排序：直接选择排序、堆排序、

d. 归并排序：归并排序

e. 分配排序：计数排序、桶排序、基数排序

1.2 排序算法的复杂度

1.2.1 算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。

算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))，它表示随着问题规模的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，其中f(n)是问题规模n的某个函数。这种记法称作大O记法。

1.2.2 推导大O阶方法

(1). 用常数1取代运行时间中的所有加法常数；

(2). 在修改后的运行次数函数中，只保留最高阶项；

(3). 如果最高阶存在且不是1，则去除与这个项相乘的常数，从而最终得到结果。

1.2.3 常见的复杂度

要分析算法的复杂度，关键是要分析循环结构的运行情况，常见的时间复杂度有：

O(1)常数阶；
O(logn)对数阶；
O(n)线性阶；
n(logn)表示nlogn阶；
O(n^2)平方阶；
O(n^3)立方阶；
O(2^n)指数阶。
上面的顺序也是复杂度从小到大的排列顺序。

二、经典排序方法总结

2.1 冒泡排序

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

(1). 最常见的版本：经过两轮循环，用当前的i和后面的每个元素比较，如果不是最小就交换到i的位置，这样可以保证每轮外部循环都能将i位置的元素确定，但对其余的记录排序没有什么帮助，效率低。(内层循环从i开始)

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
for(size_ti=0; i<sz; ++i)
for(size_tj=i+1; j<sz; ++j)
if(store[i] > store[j])
std::swap(store[i], store[j]);
}

(2). 正宗的冒泡排序：每次内循环的时候，进行紧密相邻两个元素的比较，将较小的数向前交换，就像是冒泡一样，确保每次最小的值能到达正确的位置，同时其余元素也能够相应地向对应的方向移动。

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
for(size_ti=0; i<sz; ++i)
for(size_tj=0; j<sz-1; ++j)
if(store[j] > store[j+1])
std::swap(store[j], store[j+1]);
}

(3). 优化：在上面正宗的冒泡排序中，如果经过一轮的检查，没有发生任何的swap交换活动，则表明已经有序了，此时就可以直接跳出循环表明排序完成了。

冒泡排序其总的时间复杂度为O(n^2)。

冒泡排序是一种稳定的排序方法。

2.2 鸡尾酒排序(Shaker排序)

该排序又叫作双向冒泡排序，算是冒泡排序的一种轻微改进版本。普通的冒泡排序只能每次从前往后进行一个次序遍历，而Shaker排序每次遍历包括两个方向，先从前往后遍历记录最后发生交换的两个元素位置，然后从这个位置开始从后往前遍历，这种双向交替比较不仅会使小的浮上水面，也会使大的沉到水底，因而效率会比较高。

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
size_tleft=0, right=sz-1;
size_ti=0;

while(left<right) {
//第一遍，从左到右
for(i=left; i<right; ++i) {
if(store[i] > store[i+1])
std::swap(store[i], store[i+1]);
 }
 -- right;

for(i=right; i>left; --i) {
if(store[i] < store[i-1])
std::swap(store[i], store[i-1]);
 }
 ++ left;
 }
}

该排序也是稳定排序算法。

2.3 简单选择排序

简单选择排序的过程就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，然后直接和第i(1≤i≤n)个记录交换之，按照这种方法依次对剩余排序位进行填充。

从简单选择排序的过程看来，其比较的次数并没有减少，但最大的特点就是交换移动数据次数相当少，所以效率会高一些。

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
size_tindex =0;

for(size_ti=0; i<sz; ++i) {
 index = i;
for(size_tj=i+1; j<sz; ++j)
if(store[j] < store[index])
 index = j;

if(i != index)
std::swap(store[i], store[index]);
 }
}

因为会有元素交换，所以简单选择排序不是稳定排序算法。

简单选择排序总的时间复杂度为O(n^2)。

2.4 插入排序

2.4.1 直接插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

直接插入排序是一种插入排序的方法，实际使用的时候可以在序列的头部添加一个哨兵，将i的数据放到哨兵后就空出一个位置，便于后面数据的挪动，找到空位后将哨兵位置的原数据插入进去就可以了。

virtualvoiddo_sort(std::vector<int>& store)override{
std::list<int> tmp;
autoit = tmp.begin();
for(auto& i: store)
 {
for(it = tmp.begin(); it!=tmp.end() && *it<i; ++it)
continue;
 tmp.insert(it, i);
 }
 store.assign(tmp.cbegin(), tmp.cend());
}

直接插入排序法的时间复杂度为O(n^2)。

直接插入排序是一种稳定的排序算法。

2.4.2 二分插入排序

二分插入排序又叫折半插入排序，算是前面直接插入排序的变种改进，主要是用了折半查找的思路进行了优化。上面用了容器的方式直接插入排序，下面用传统的数组方式进行插入排序的模拟。

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
for(size_ti=1; i<sz; ++i) {
intelem = store[i];
intleft =0;
intright = i-1;

while(left <= right)//当left==right，也需要判断mid前还是后
 {
ssize_tmid = (left + right) /2;//向0取整
if(elem > store[mid])
 left = mid + 1;//必须+1 -1，否则相邻序死循环
else
 right = mid - 1;
 }

for(size_tj=i; j>left; --j)
 store[j] = store[j-1];
 store[left] = elem;
 }
}

2.5 希尔排序

希尔排序的思路是：将待排序列分割成若干个子序列，此时每个子序列待排序的记录个数比较少，可以在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。

但是这里的分组不是简单相邻的分组，而是将相隔某个“增量/increment”的记录组成一个子序列，实现跳跃式的交换移动，所以使得排序的效率提高。随着增量的不断减少，跳跃移动的步伐慢慢变小，而整个系列也变的更为的“基本有序”。还需要注意要确保最终的increment=1来实现最后一次精细的排序，然后整个序列就变的有序了。

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();
size_tgap = sz >>1;

while(gap) {
//所有间隔gap的元素为一组，第一个元素不排序，所以跳过gap
for(size_ti=gap; i<sz; ++i) {
intelem = store[i];
intj = i;

while( j>=gap && elem < store[j-gap] ) {
 store[j] = store[j-gap]; //移动gap
 j -= gap;
 }
 store[j] = elem;
 }

 gap >>= 1;
 }
}

目前关于增量/increment的选择还没有统一的方法。希尔排序的时间复杂度是O(n^(3/2))。

由于记录是跳跃式的移动，所以希尔排序并不是一种稳定的排序算法。

2.6 堆排序

堆排序就是利用堆这种数据结构，实现的对简单选择排序进行的一种改进。

堆结构是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。根结点一定是堆中所有结点最大（小）者，而同时较大（小）的结点也较靠近根结点。

对于一个满二叉树，根据其性质有：对于结点n，其双亲是结点[n/2]；对于节点i，其左右子树是2i和2i+i。

下面以大顶堆方法排序为例，其基本思路就是：将待排序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个大顶堆(调整使其成为大顶堆)，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

voidbuildHeap(std::vector<int>& store,size_tcurr/*父*/,size_tlast/*尾，包含*/){
size_tchild =2*curr +1;//左孩
intelem = store[curr];

while(child <= last) {
//两个儿子中较大的
if(child<last && store[child]<store[child+1])
 ++child;

if(elem >= store[child])
break;

// 元素交换，同时递归到子节点，另外一个儿子不用管了
 store[curr] = store[child];
 curr = child;
 child = 2*curr +1;
 }

 store[curr] = elem;
}

virtualvoiddo_sort(std::vector<int>& store)override{
constsize_tsz = store.size();

for(inti=((sz-1)-1)/2; i>=0; --i)// 首先建立堆
 buildHeap(store, i, sz-1);

for(inti=sz-1; i>0; --i) {
std::swap(store[0], store[i]);
 buildHeap(store, 0, i-1);
 }
}

上面从L->length/2开始就是因为这里需要处理的是有孩子的节点。在HeapAdjust中的关键操作，就是从底向顶，递归的将两个孩子和父节点中最大值放到父节点上面，最终堆顶就是最大值了，然后交换到数组的尾部。

构建和调整堆的时间复杂度为O(logn)，所以总体来说堆排序的时间复杂度为O(nlogn)。由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。

2.7 归并排序

归并在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表的过程。

归并排序的原理是假设初始序列n个记录可以看成是n个有序子序列，每个子序列长度为1，然后两两归并，得到不小于n/2的整数个长度为2或1的有序子序列；再两两归并递归下去，……，如此重复直到得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

具体操作是先分开进行do_merge_sort，然后再进行do_merge_merge进行合并，是一个很典型的递归调用形式。

voiddo_merge_sort(std::vector<int>& store,
size_tbeg,size_tlast) {
if(beg < last) {
size_tmid = (beg + last) /2;
 do_merge_sort(store, beg, mid);
 do_merge_sort(store, mid+1, last);
 do_merge_merge(store, beg, last, mid);
 }
}

voiddo_merge_merge(std::vector<int>& store,
size_tbeg,size_tlast,size_tmid/*included in first*/)
{
size_tindex_1 = beg, index_2 = mid+1;
size_tindex_s =0;
std::vector<int> tmp_vec(last - beg +1);

while(index_1 <= mid || index_2 <= last ) {
if(index_1 > mid) {
while(index_2 <= last)
 tmp_vec[index_s ++] = store[index_2++];
 }
elseif(index_2 > last) {
while(index_1 <= mid)
 tmp_vec[index_s ++] = store[index_1++];
 }
else{
if(store[index_1] < store[index_2])
 tmp_vec[index_s ++] = store[index_1++];
else
 tmp_vec[index_s ++] = store[index_2++];
 }
 }
//将最终的结果拷贝到对应的区段
for(size_ti=0; i<tmp_vec.size(); ++i)
 store[beg+i] = tmp_vec[i];
}

归并中需要对所有元素进行扫描合并，所以复杂度是O(n)，同时由于是二叉树类似的层次结构，所以递归遍历需要O(logn)，整体的时间复杂度是O(nlogn)。

在归并排序中只有两两比较，不存在跳跃操作，因此归并排序是一种稳定的排序算法。

2.8 快速排序

快速排序又名分区排序，其实是冒泡排序的升级，同属于交换排序类。快速排序增大了比较和移动的距离，将较大的记录从前面直接移动到后面，较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。

快速排序基本思想：每次选择一个基准数据，通过一趟排序将待排记录分割成独立两部分，其中一部分记录均比另一部分记录小，然后分别对这两部分记录继续进行排序，最终以达到整个序列有序。

快速排序的核心思想就是数据分区、递归调用。

voiddo_quick_sort(std::vector<int>& store,size_tleft,size_tright){
size_ti=left, j=right;
intpivot = store[i];

while(i<j) {
while(i<j && store[j] > pivot)
 --j;
if(i<j)
std::swap(store[i], store[j]);//pivot == store[j]

while(i<j && store[i] < pivot)
 ++i;
if(i<j)
std::swap(store[i], store[j]);//pivot == store[i]
 }

if(left != i)
 do_quick_sort(store, left, i - 1);

if(right != j)
 do_quick_sort(store, j + 1, right);
}

上面的while循环是整个快速排序的核心部分，设计的比较的巧妙，在右边查找比pivot小的元素，然后将其交换到前半部[i]的位置，再在前面查找比pivot大的值，将其交换到后半部[j]的位置，整个过程中所有的数据移动都是高效有作用的。当检查的目标i、j中间交汇的时候，本轮排序结束。

在最优的情况下(pivot的值选择刚好在整个排序范围的中间)，快速排序算法的时间复杂度为O(nlogn)；在最坏的情况下，其时间复杂度为O(n^2)；平均情况下快速排序的时间复杂度是O(nlogn)。

由于关键字的比较和交换是跳跃进行的，快速排序是一种不稳定的排序方法。

pivot枢轴的选取对于整个排序算法的性能至关重要，基本算法都是选择左边第一个值来作为pivot的，其他衍生算法可以对pivot值得选取做个考究。

2.9 线性时间排序

2.9.1 计数排序

其基本算法如下：

(1). 取出待排序列中的最小值n1和最大值n2，建立一个n2-n1+1长度的数组；

(2). 依次遍历待排元素，根据待排元素的值将对应数组项计数自增；

(3). 这步比较关键，统计数组计数，每项保存前N项和count_arr[k] += count_arr[k-1];这其实是进行了值到最终排列位置的映射关系；

(4). 再依次遍历待排元素，根据元素值查找count_arr中对应的最终排序位置，计入到排序结果中。

缺点是空间要求比较大。

virtualvoiddo_sort(std::vector<int>& store)override{
autoit =std::max_element(store.cbegin(), store.cend());
intmax_item = *it;
std::vector<int> result(store.size());

std::vector<int> bucket(max_item +1);
for(auto& elem: store)
 bucket[elem] ++;

// 关键，调整计数针对索引
for(size_ti=1; i<bucket.size(); ++i)
 bucket[i] += bucket[i-1];

//得到元素位置，保留结果
for(auto& elem: store)
 result[bucket[elem] - 1] = elem;

 store = result;
}