排序篇
一、中小规模数组
较小规模的数组，常用的是选择排序和插入排序，
| 交换次数 | 比较次数 | |
|---|---|---|
| 选择排序 | N | N2/2(稳定最差) |
| 插入排序 | N2/4(最好为0) | N2/4（最好为N） |
选择排序模板代码:
public class Selection
{
public:
void sort(Comparable[] a)
{
// 将a[]按升序排列
int N = a.length; // 数组长度
for (int i = 0; i < N; i++)
{
// 将a[i]和a[i+1..N]中最小的元素交换
int min = i; // 最小元素的索引
for (int j = i+1; j < N; j++)
if (less(a[j], a[min])) min = j; //less(1,2) == true
exch(a, i, min);
}
}
// less()、exch()、isSorted()和main()方法见“排序算法类模板”
}
插入排序模板代码：
public class Insertion
{
public:
void sort(Comparable[] a)
{
// 将a[]按升序排列
int N = a.length;
for (int i = 1; i < N; i++)
{
// 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
}
// less()、exch()、isSorted()和main()方法见“排序算法类模板”
}
较大规模的数组，首先考虑希尔排序，时间复杂度为（平均）：nlog2n，最好时间复杂度为：n
解释：使用递增序列的希尔排序所需的比较次数不会超出 N 的若干倍乘以递增序列的长度。数学推导如下：
O
(
N
)
=
k
n
?
l
o
g
2
n
≈
n
l
o
g
2
n
（不考虑交换的常数时间，只考虑比较次数）
O(N) = kn*log2n ≈ nlog2n（不考虑交换的常数时间，只考虑比较次数）
O(N)=kn?log2n≈nlog2n（不考虑交换的常数时间，只考虑比较次数）
模板代码：
public class Shell
{
public :
void sort(Comparable[] a)
{ // 将a[]按升序排列
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
while (h >= 1)
{ // 将数组变为h有序
for (int i = h; i < N; i++)
{ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h/3;
}
}
// less()、exch()、isSorted()和main()方法见“排序算法类模板”
}
二、大规模数组（百万级别）
这种大规模数组首先用简单的希尔排序，先实现，后面进行优化即可，这里主要介绍一下优化的几种方法。
首先是渐进最优的基于比较排序的归并排序（Merge），归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是 ~NlgN。研究表明基于比较的排序算法，需要的比较次数为$N! {—}2^{N}
，时间复杂度为
，时间复杂度为
，时间复杂度为lgN {—}NlgN $，而归并排序的时间复杂度为排序算法的上限，差距不大。
（这里暂时不考虑空间复杂度）
自顶向下版——Merge ：
class Merge{
static datatype *aut_;
public:
void sort(datatype *a){
size_t len = a.size();
datatype *aut_ = new datatype[len];
sort(a,0,len-1);
}
private:
void sort(datatype *a,size_t lo,size_t hi){
if(lo>=hi){
return;
}
size_t mid = lo+(hi-lo)/2;//不要直接(lo+hi)/2
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
void merge(datatype *a, size_t lo, size_t mid, size_t hi){
size_t i = lo;
size_t j = mid+1;
for(size_t k=0;k<a.size();k++){
aut_[k] = a[k];
}// factor about things like std::move()
for(size_t m=lo;m<hi;m++){
if(i>mid){a[m] = aut_[j++];}
else if(j>hi){a[m] = aut_[i++];}
else if(less(aut_[i],aut_[j])){a[m] = aut_[i++];}
else {a[m] = aut_[j++]}
}
}
}
自底向上版——Merge ：
class Merge{
static datatype *aut_;
public:
void sort(datatype *a){
size_t len = a.size();
datatype *aut_ = new datatype[len];
sort(a,0,len-1);
}
private:
void sort(datatype *a,size_t lo,size_t hi){
for(size_t sz = 1;sz<hi;sz = sz+sz){
//sz:子数组大小，针对每两组进行归并排序
for(size_t lo =0;lo<sz;lo+=sz+sz){
//lo:子数组索引
merge(a,lo,lo+sz-1,min(lo+sz+sz-1,hi));
}
}
}
void merge(datatype *a, size_t lo, size_t mid, size_t hi){
size_t i = lo;
size_t j = mid+1;
for(size_t k=0;k<a.size();k++){
aut_[k] = a[k];
}// factor about things like std::move()
for(size_t m=lo;m<hi;m++){
if(i>mid){a[m] = aut_[j++];}
else if(j>hi){a[m] = aut_[i++];}
else if(less(aut_[i],aut_[j])){a[m] = aut_[i++];}
else {a[m] = aut_[j++]}
}
}
}
待优化的几个方面：
- 对小规模子数组采用插入排序
- 不将元素复制到辅助数组，在递归调用的每个层次交换输入数组和辅助数组的角色。
-
快速排序
作为归并排序的补充，将回溯的位置进行了调整，先划分再排序，而归并排序是先排序再合并。
优点
- 平均时间复杂度为O(nlogn)，空间复杂度为O(n)，速度快，所以称为快速排序
- 最好的时间复杂度为O(n)，最坏是O(n2)，所以有待优化。
- 虽然比较次数2NlnN ≈ 1.39NlgN，也就是说平均比较次数只比最好情况多 39%，由于交换移动次数少，性能优秀
快排代码
class Quick_Sort{ public: void sort(datatype *a,size_t lo, size_t hi){ if(lo>=hi){ return; } size_t j = partition(a,lo,hi); sort(a,lo,j-1); sort(a,j+1,hi); } size_t partition(datatype *a, size_t lo, size_t hi){ size_t i,j; j = hi+1; i = lo; datatype v = a[lo]; while(true){ while(less(a[++i],v)){if(i == hi) break;//ommit} while(less(v,a[--j])){if(j == lo) break;//ommit} if(i>=j){break;} exch(a,i,j); } exch(a,lo,j); return j; } }待优化的地方
-
时间复杂度受到了原始数组的影响较大，一般需要一个初始化步骤，将原始数组进行打乱，放置遇到极端情况。
-
对于重复主键较多时，采用三向切分（区别于二分）的quick sort，最好的时候能够达到线性复杂度。
- 三向切分代码：
class Quick3Sort{
public:
void sort(datatype *a,size_t lo, size_t hi){
if(lo>=hi){
return;
}
size_t i,ht,lt;
lt = lo;
i = lo+1;
ht = hi;
datatype v = a[lo];
while(i<=ht){
auto cmp = less(a[i],v)
if(cmp>0){exch(a,i,ht--);}
if(cmp<0){exch(a,i++,lt++);}
else{i++;}
}
sort(a,lo,lt-1);
sort(a,ht+1,hi);
}
}
-
切换到插入排序，
- 对于小数组，快速排序比插入排序慢
- 因为递归，快速排序的 sort() 方法在小数组中也会调用自己。
因此，在排序小数组时应该切换到插入排序。简单地改动算法 ，就可以做到这一点：
将 sort() 中的语句
if (hi <= lo) return;替换成下面这条语句来对小数组使用插入排序：
if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; } -
三取样切分，取子数组的中位数进行划分。
-
优先队列（堆排序）
两个核心的步骤，上浮（swim），下沉（sink）
void swim(int i){ //上浮数组中的第i个元素 while((i>1)&&(less(i/2,i))){ exch(i/2,i); i = i/2; } } void sink(int i){ while(2*i<=N){ int j = 2*i; if(j<N&&(less(j,j+1))) j++; if(!less(i,j)){ break; } exch(i,j); i = j; } }以及两个重要的API(从1开始索引，到N结束)
void insert(Key v){ pq_[++N] = v; swim(N); } Key delMax(){ Key k = pq_[1]; exch(1,N); pq[N--] = NULL; sink(1); }堆排序：构造+排序
难点在于构造！！
void sort(){ for(int k = N/2;k>=1;k--){ sink(a,k,N);//子堆建立 } while(N>=1){ exch(a,1,N--); sink(a,1,N); } }实现方法：下沉排序或者先下沉再上浮
-
特点
-
可以进行无限数组的筛选与排序，针对数组流的处理，具有很强的张力
-
可以归约为求解一类TOPM问题的算法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-guzXMnDh-1661926275545)(2022-8-17 排序篇 221016.assets/image-20220819093538539-16608729399871.png)]
-
-
应用
从上面看见，堆排序的优势在于两点：原地排序和线性对数级别的时间复杂度，但没有稳定性。几个典型的应用案例：
-
任务调度
假设我们需要完成 N 个任务，第 j 个任务需要耗时 tj秒。我们需要在完成所有任务的同时尽量确保客户满意，将每个任务的平均完成时间最小化。
思路：按照最短优先的原则，只要我们将任务按照处理时间升序排列就可以达到目标。因此我们可以将任务按照耗时排序，或是将它们插入到一个最小优先队列中
-
负载均衡
假设我们有 M 个相同的处理器以及 N 个任务，我们的目标是用尽可能短的时间在这些处理器上完成所有的任务。
思路：这个问题是 NP-困难的，因此我们实际上不可能算出一种最优的方案。但一种较优调度方法是最大优先。我们将任务按照耗时降序排列，将每个任务依次分配给当前可用的处理器。要实现这种算法，我们先要逆序排列这些任务，然后为 M 个处理器维护一个优先队列，每个元素的优先级就是对应的处理器上运行的任务的耗时之和（耗时越多优先级越高）。每一步中，我们都删去优先级最低的那个处理器，将下一个任务分配给这个处理器，然后再将它重新插入优先队列。
-
组合搜索
A 算法*：将起始状态放入优先队列中，然后重复下面的方法直到到达目的地：删去优先级最高的状态，然后将能够从该状态在一步之内达到的所有状态全部加入优先队列（除了刚刚删去的那个状态之外）。结束条件为：优先队列为空或者到达目的地。
priority_queue<Type, Container, Functional> type-是堆排序的元素类型，container-是数组实现的容器，Functional-是元素之间比较的方法（greater与less） A *{ priority_queue pq; pq.push(a);//这里的a可以视为初始状态或者根节点 unordered_map<int,int> maps; while(!pq.empty()){ s = pq.top(); maps.insert(s); pq.pop(); if(s == target ){ return; } while(auto child = s.nextChild()){ if(maps.count(child) == 0){ pq.push(child;) } } } }霍夫曼压缩算法
将数据从小到大排序，将最小的两个生成一棵树，其权为二者的和。然后将其加入到队列中与其他的比较并继续此过程。
class huffman { private: const static int r = 256; int freq[256] = {}; std::string st[256]; struct node { int index; int times; node *right; node *left; node() { }; node(int a, int b, node *r, node *l) { index = a; times = b; right = r; left = l; } }; node *create_node(int a, int b, node *r, node *l) { node *newnode = new node; newnode->index = a; newnode->times = b; newnode->right = r; newnode->left = l; return newnode; } node *x, *y,*p; static bool comp(node a, node b) { return a.times > b.times; } node built_tire() { std::vector<node> pq; for (int i = 0; i < r; i++) { if (freq[i] > 0) { //printf("%d ", i); node newnode(i,freq[i],nullptr,nullptr); pq.push_back(newnode); } } //printf("%d", pq.size()); std::sort(pq.begin(), pq.end(), comp); while (pq.size()>1) { x = &pq.back(); pq.pop_back(); y = &pq.back(); pq.pop_back(); p = create_node(0, x->times + y->times, x, y); pq.push_back(*p); std::sort(pq.begin(), pq.end(), comp); } return pq.back(); } void built_code(node x, std::string s) { if (x.left == nullptr&&x.right == nullptr) { st[x.index] = s; std::cout << x.index << std::endl; return; } //printf("%d %d %d", x.times, x.left->times,x.right->times); built_code( *x.left, s + '0'); built_code( *x.right, s + '1'); } public: void compress(std::string s) { for (int i = 0; i < s.length(); i++) { freq[s[i]]++; } std::vector<node> pq; for (int i = 0; i < r; i++) { if (freq[i] > 0) { //printf("%d ", i); node newnode(i, freq[i], nullptr, nullptr); pq.push_back(newnode); } } //printf("%d", pq.size()); std::sort(pq.begin(), pq.end(), comp); while (pq.size() > 1) { x = create_node(pq.back().index, pq.back().times, pq.back().left, pq.back().right); pq.pop_back(); y = create_node(pq.back().index, pq.back().times, pq.back().left, pq.back().right); pq.pop_back(); p=new node(0, x->times + y->times, x, y); pq.push_back(*p); std::sort(pq.begin(), pq.end(), comp); } node root = pq.back(); //node root = built_tire(); //node *t = root.left; built_code(root,""); std::cout << s << std::endl; for (int i = 0; i < s.length(); i++) { std::string code = st[s[i]]; std::cout << code; } } };字符串处理(著名的KMP)：最长重复子字符串算法时会先将字符串的后缀排序
Kruskal 算法，Prim 算法和 Dijkstra 算法等等，以后继续填坑。
-
-