天空一声巨响，迪宝闪亮登场。哈哈哈数据结构刷题又来了。实践是检验真理的唯一标准，最近感觉到自己的代码功底越来越深了，看来多写代码确实很有帮助。这次又带来最新的四道题目，来跟我一起去看看把。（顺便提一下，现在我在PTA上浙大《数据结构》这个题库已经排名1/2976了哦！！！）

排序1 排序

这次我们学习了很多高级的排序算法，主要有以下几种：

  • 快速排序
  • 表排序
  • 物理排序
  • 桶排序/基数排序

下面我将尝试用这几种方式对排序1问题进行不同的尝试：

表排序

表排序的话其实就是为每个交换项增加了一个关键字，交换方法还是沿用基本排序算法的。

物理排序

物理排序的话其实在下面Sort with Swap的题目中已有涉及，这种方法在数据范围和数组长度相同时可以几乎达到线性复杂度，这里就不再写了。

桶排序

桶排序或者基数排序的话是用一定的适用场景的（就是在适用场景下才能发挥出桶排序/基数排序的威力，其他情况当然也能用），主要就是用空间换时间，这里也不太适合使用基数排序。

快速排序

下面重点来讲讲这道题的快速排序。快速排序一共分为以下几个步骤：

  • 选主元（左中右取中位数）
  • 子集划分（对撞指针）
  • cutoff阈值（规模较小时直接使用简单排序算法）

快速排序一共用两种实现方式：

  • 直接调用库函数
  • 直接手撕一遍

下面我就来手撕一遍快速排序算法把！
此题代码如下：

  1. #include<iostream>
  2. #include<cmath>
  4. using namespace std;
  5. long int N;
  6. long int *a;
  8. void Median(int l,int r);
  9. int Subset(int l,int r);
  10. void Swap(long int&a,long int&b);
  11. void HSort(long int *H,int n);
  12. void Quicksort(int l,int r);
  14. int main(){
  15.     cin >> N;
  16.     a = new long int[N];
  17.     for(int i = 0;i < N;i++)
  18.         cin >> a[i];
  19.     Quicksort(0,N-1);
  20.     cout<<a[0];
  21.     for(int i = 1;i < N;i++)
  22.         cout << ' ' << a[i];
  23.     return 0;
  24. }
  26. void Swap(long int&a,long int&b){
  27.     long int temp = a;
  28.     a = b;
  29.     b = temp;
  30. }
  32. void Quicksort(int l,int r){
  33.     if(l >= r)
  34.         return;
  35.     else if(r-l == 1){
  36.         if(a[l] > a[r])
  37.             Swap(a[l],a[r]);
  38.         return;
  39.     }
  40.     //如果小于阈值就直接希尔排序
  41.     if(r-l <= 10){
  42.         HSort(a+l,r-l+1);
  43.         return;
  44.     }
  45.     Median(l,r); //选主元
  46.     int med = Subset(l+1,r-1); //子集划分
  47.     Quicksort(l,med-1); //递归排序左子集
  48.     Quicksort(med+1,r); //递归排序右子集
  49. }
  51. void Median(int l,int r){
  52.     int c = (l+r) / 2;
  53.     if(a[l] > a[c])
  54.         Swap(a[l],a[c]);
  55.     if(a[c] > a[r])
  56.         Swap(a[r],a[c]);
  57.     if(a[l] > a[c])
  58.         Swap(a[l],a[c]);
  59.     Swap(a[c],a[r-1]);
  60. }
  62. int Subset(int l,int r){
  63.     int z1 = l;
  64.     int z2 = r-1;
  65.     int flag1 = 0;
  66.     while(z1 < r && z2 < r){
  67.         if(flag1 == 0){
  68.             if(a[z1] > a[r])
  69.                 flag1 = 1;
  70.             else
  71.                 z1++;
  72.         }
  73.         else{
  74.             if(a[z2] < a[r]){
  75.                 if(z1 <= z2){
  76.                     Swap(a[z1],a[z2]);
  77.                     flag1 = 0;
  78.                 }
  79.                 else
  80.                     break;
  81.             }
  82.             else
  83.                 z2--;
  84.         }
  85.     }
  86.     Swap(a[z1],a[r]);
  87.     return z1;
  88. }
  90. void HSort(long int *H,int n){
  91.     int count = 1;
  92.     while((int)pow(2,count) - 1 < n)
  93.         count++;
  94.     count--;
  95.     for(int i = count;i > 0;i--){
  96.         int D = (int)pow(2,i) - 1;
  97.         for(int j = 0;j < D;j++){
  98.             for(int k = j;k < n;k += D){
  99.                 if(k == j)
  100.                     continue;
  101.                 long int t = H[k];
  102.                 for(int p = j;p < k;p += D){
  103.                     if(t < H[p]){
  104.                         for(int s = k;s > p;s -= D){
  105.                             H[s] = H[s-D];
  106.                         }
  107.                         H[p] = t;
  108.                         break;
  109.                     }
  110.                 }
  111.             }
  112.         }
  113.     }
  114. }

阈值为10的结果如下所示：
image.png
阈值为30的结果如下所示：
image.png
阈值为70的结果如下所示：
image.png
可以发现，当阈值为30时，排序时间复杂度最小，但是这个也跟问题规模有关，当问题规模相对较小时，快速排序比较慢，这时候可以选择简单排序算法如希尔排序等。所以快速排序的方法可以归纳为：分而治之+对每个分好的子集使用简单排序算法。

统计工龄

这道题挺简单的，没什么难点。
此题代码如下：

  1. #include<iostream>
  3. using namespace std;
  4. long int N;
  5. long int *a;
  7. int main(){
  8.     int temp;
  9.     cin >> N;
  10.     a = new long int[51];
  11.     for(long int i = 0;i < N;i++){
  12.         cin >> temp;
  13.         a[temp]++;
  14.     }
  15.     for(int i = 0;i < 51;i++){
  16.         if(a[i] != 0)
  17.             cout<<i<<':'<<a[i]<<endl;
  18.     }
  19.     return 0;
  20. }

PAT Judge

这道题非常锻炼代码能力。主要的思路就是根据几个指标进行桶排序，或者叫基数排序，而且要采用“次位优先”的方法，还使用到了链表和哈希表的相关知识和操作，可以说出的很不错。
此题代码如下：

  1. #include<iostream>
  2. #include<string>
  4. using namespace std;
  5. int N,K;
  6. long int M;
  7. int *p;
  9. class Node2{
  10.     public:
  11.     string name;
  12.     int ttr;
  13.     int grade;
  14.     int s[6];
  15.     Node2(){
  16.         ttr = 0;name = "";
  17.         grade = 0;
  18.         for(int i = 1;i <= K;i++)
  19.             s[i] = -2;
  20.     }
  21.     Node2 &operator=(const Node2& n){
  22.         if(this == &n)
  23.             return *this;
  24.         else{
  25.             this->name = n.name;
  26.             this->ttr = n.ttr;
  27.             this->grade = n.grade;
  28.             for(int i = 1;i < 6;i++)
  29.                 this->s[i] = n.s[i];
  30.             return *this;
  31.         }
  32.     }
  33.     bool operator==(const Node2& n){
  34.         if(this->name != n.name || this->ttr != n.ttr || this->grade != n.grade)
  35.             return false;
  36.         for(int i = 1;i < 6;i++){
  37.             if(this->s[i] != n.s[i])
  38.                 return false;
  39.         }
  40.         return true;
  41.     }
  42. };
  44. class Node{
  45.     private:
  46.     Node2 value;
  47.     Node* next;
  48.     public:
  49.     Node(){ next = NULL; }
  50.     Node2 Getvalue() { return this->value; }
  51.     Node* Getnext() { return this->next; }
  52.     void Setvalue(Node2 num) { value = num; }
  53.     void Setnext(Node* a) { next = a; }
  54. };
  56. class Nodearray{
  57.     public:
  58.     Node* head;
  59.     Node* tail;
  60.     Nodearray(){
  61.         head = NULL;
  62.         tail = NULL;
  63.     }
  64.     void Addnum(Node2 num){
  65.         if (head == NULL){
  66.             head = new Node;
  67.             head->Setvalue(num);
  68.             head->Setnext(NULL);
  69.             tail = head;
  70.         }
  71.         else{
  72.             tail->Setnext(new Node);
  73.             (tail->Getnext())->Setvalue(num);
  74.             (tail->Getnext())->Setnext(NULL);
  75.             tail = tail->Getnext();
  76.         }
  77.     }
  78.     void Delnum(Node2 num){
  79.         Node* p1 = head;
  80.         Node* p2 = head;
  81.         if (head == NULL){
  82.             cout << "这是空列表" << endl;
  83.             return;
  84.         }
  85.         else{
  86.             if (head->Getvalue() == num){
  87.                 head = head->Getnext();
  88.                 return;
  89.             }
  90.             else
  91.                 p2 = p2->Getnext();
  92.             while (p2 != NULL){
  93.                 if (p2->Getvalue() == num){
  94.                     p1->Setnext(p2->Getnext());
  95.                     cout << "删除成功" << endl;
  96.                     return;
  97.                 }
  98.                 p1 = p1->Getnext();
  99.                 p2 = p2->Getnext();
  100.             }
  101.         }
  102.     }
  103. };
  105. Node2 *a;
  106. Nodearray *b,*c,*d;
  108. int main(){
  109.     cin >> N >> K >> M;
  110.     a = new Node2[N+1];
  111.     p = new int[K+1];
  112.     int mf = 0;
  113.     for(int i = 1;i <= K;i++){
  114.         cin >> p[i];
  115.         mf += p[i];
  116.     }
  117.     string temp;int k,g;
  118.     for(int m = 0;m < M;m++){
  119.         cin >> temp >> k >> g;
  120.         if(a[stoi(temp)].name == "")
  121.             a[stoi(temp)].name = temp;
  122.         if(g > a[stoi(temp)].s[k]){
  123.             if(a[stoi(temp)].s[k] >= 0)
  124.                 a[stoi(temp)].grade += g - a[stoi(temp)].s[k];
  125.             else if(g >= 0)
  126.                 a[stoi(temp)].grade += g;
  127.             a[stoi(temp)].s[k] = g;
  128.             if(g == p[k])
  129.                 a[stoi(temp)].ttr++;
  130.         }
  131.     }
  132.     //按照总分排序
  133.     b = new Nodearray[K+1];
  134.     c = new Nodearray[mf+1];
  135.     int flag;
  136.     for(int i = 1;i <= N;i++){
  137.         if(a[i].name == "")
  138.             continue;
  139.         if(a[i].grade == 0){
  140.             flag = 0;
  141.             for(int j = 1;j <= K;j++){
  142.                 if(a[i].s[j] >= 0)
  143.                     break;
  144.                 if(j == K)
  145.                     flag = 1;
  146.             }
  147.             if(flag == 1)
  148.                 continue;
  149.         }
  150.         b[a[i].ttr].Addnum(a[i]);
  151.     }
  152.     //按照完全对题数排序
  153.     Node *p;
  154.     for(int i = K;i > -1;i--){
  155.         p = b[i].head;
  156.         while(p != NULL){
  157.             c[(p->Getvalue()).grade].Addnum(p->Getvalue());
  158.             p = p->Getnext();
  159.         }
  160.     }
  161.     //按照ID排序
  162.     Node *p2;
  163.     int count = 1;int lastcount;int lastg = -1;
  164.     for(int i = mf;i > -1;i--){
  165.         p2 = c[i].head;
  166.         while(p2 != NULL){
  167.             if((p2->Getvalue()).grade != lastg){
  168.                 cout<<count<<' ';
  169.                 lastcount = count;
  170.             }
  171.             else
  172.                 cout<<lastcount<<' ';
  173.             lastg = (p2->Getvalue()).grade;
  174.             cout<<(p2->Getvalue()).name<<' '<<(p2->Getvalue()).grade;
  175.             for(int j = 1;j <= K;j++){  
  176.                 if((p2->Getvalue()).s[j] >= 0)
  177.                     cout<<' '<<(p2->Getvalue()).s[j];
  178.                 else if((p2->Getvalue()).s[j] == -1)
  179.                     cout<<" 0";
  180.                 else
  181.                     cout<<" -";
  182.             }
  183.             cout<<endl;
  184.             count++;
  185.             p2 = p2->Getnext();
  186.         }
  187.     }
  188.     return 0;
  189. }

Sort with Swap

这道题就是赤裸裸的物理排序了，先想清楚答案是怎么计算得到的，再考虑一些特殊情况（比如一开始0就在索引为0的位置等），这道题帮助大家巩固表排序和物理排序。
此题代码如下：

  1. #include<iostream>
  3. using namespace std;
  4. long int N;
  5. long int *a;
  6. long int *vis;
  8. int main(){
  9.     cin >> N;
  10.     if(N == 1){
  11.         cout<<'0';
  12.         return 0;
  13.     }
  14.     a = new long int[N];
  15.     vis = new long int[N];
  16.     for(int i = 0;i < N;i++)
  17.         vis[i] = 0;
  18.     for(int i = 0;i < N;i++)
  19.         cin >> a[i];
  20.     int count = N-2;
  21.     if(a[0] == 0)
  22.         count += 2;
  23.     for(int i = 0;i < N;i++){
  24.         if(vis[i] == 0){
  25.             if(a[i] == i){
  26.                 vis[i] = 1;
  27.                 count -= 1;
  28.                 continue;
  29.             }
  30.             int temp = i;
  31.             while(a[temp] != i){
  32.                 vis[temp] = 1;
  33.                 temp = a[temp];
  34.             }
  35.             vis[temp] = 1;
  36.             count++;
  37.         }
  38.     }
  39.     cout<<count;
  40.     return 0;
  41. }

总结

这次的刷题记录是排序专场，我们学习到了几种高级排序方法，各有千秋，强烈建议所有排序大家都手写一次，这样子以后用到的时候直接CV就行（这也是为自己的代码库增加新代码的方式嘛！）。通过这次刷题，我又获得了新的体悟：1）你现在写的代码有可能可以为将来节省不少时间，之后再遇到直接CV即可；2）在实现算法之前多想想，不要只是急于实现，刷题到这个地步时也要想想如何高效实现，包括时间空间复杂度和代码量等等。
欢迎对ECE/CS/AI感兴趣的小伙伴关注我，如果你对我的内容有什么建议的话，或者你也对算法和数据结构感兴趣的话，可以单独找我讨论，也欢迎在评论区留下你的声音。