各类排序模版(计数排序、基数排序、桶排序、冒泡排序、选择排序、插入排序、希尔排序、归并排序、原地归并排序、快速排序、堆排序)...

梦里梦外; 2021-11-06 01:22 347阅读 0赞

# 各类排序模板 #

## 内部排序 ##

> 内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
> 
> 排序是计算机程序设计中的一种重要操作，其功能是对一个 [数据元素][Link 1]集合或序列重新排列成一个按数据元素某个相知有序的序列。排序分为两类：内排序和外排序。
> 
> 其中 [快速排序][Link 2]的是目前排序方法中被认为是最好的方法。

PS：引用自 [百度百科][Link 3]

## 头文件、宏定义及已定义方法 ##

1 #include <ctime>
     2 #include <cstdlib>
     3 #include <iostream>
     4 #define LEN (r-l+1)
     5 #define radix (a[i]/t%10)
     6 #define random(x) (rand()%x)
     7 using namespace std; 
     8 const int K = 100;     //数的范围为[0,K)
     9 typedef struct node{   //链表结点
    10     int x;
    11     struct node *next;
    12     node(int i = 0){ x = i; next = NULL; }
    13 }node;
    14 void init(int *a,int n){  //随机生成n个数
    15     srand((int)time(0));  //以时间为种子
    16     for(int i = 0; i < n; ++i)
    17         a[i] = random(K);
    18  }
    19 void print(int *a, int n){  //打印数组
    20     for(int i = 0; i < n; ++i)
    21         cout << a[i] << " ";
    22     cout << endl;
    23 }
    24 int choose(int l, int r){  //选择[l,r]直接的随机数
    25     srand((int)time(0));   //以时间为种子
    26     int m = random(LEN)+l;
    27     return random(LEN)+l;
    28 }

## 排序导航 ##

*  计数排序
 *  基数排序
 *  桶排序
 *  简单排序（冒泡、选择、插入排序）
 *  希尔排序
 *  归并排序（附原地归并排序）
 *  快速排序
 *  堆排序

## 代码 ##

### 计数排序 ###

1 void count_sort(int *a, int len, int k = K){    //计数排序
     2     int b[len],c[k];                            //b数组用于存放排序后数列,c[i]记录<=i的数的个数,k表示每位数保证在[0,k)之间
     3     for(int i = 0; i < k; ++i) c[i] = 0;        //数组清零
     4     for(int i = 0; i < len; ++i) ++c[a[i]];     //c[i]暂存i的个数
     5     for(int i = 1; i < k; ++i) c[i] += c[i-1];  //加上前面的就是<=i的数的个数
     6     for(int i = 0; i < len; ++i) b[--c[a[i]]] = a[i];
     7     //--的目的有两个: 1.数组是从0开始;
     8     //              2.下一次这个元素往前要挪一位
     9     //              (为什么是往前,因为记录的是<=i的个数
    10     //               所以当出现相同的值时，c[i]开始表示
    11     //               该元素的最后一个位置)
    12     for(int i = 0; i < len; ++i) a[i] = b[i];   //排序后数组放回原来的数组
    13 }

### 基数排序 ###

1 void radix_sort(int *a, int len, int k = 10){    //基数排序
     2     int b[len],c[k],d = 1,t = 1;
     3     //b记录每次排序后数组,c记录当前位<=i的数的个数,d记录最大位数,t记录当前位的位权,k表示一位的值在[0,k)直接
     4     for(int p = 10,i = 0; i < len; ++i)          //查找最大位数
     5         while(p <= a[i]){
     6             p *= 10;
     7             ++d;
     8         }
     9     for(int j = 1; j <= d; ++j){                            //此处代表位数,MSD、LSD皆可
    10         for(int i = 0; i < k; ++i) c[i] = 0;                //清零
    11         for(int i = 0; i < len; ++i) ++c[radix];            //radix是当前位的值,记录其个数,宏定义: radix (a[i]/t%10)
    12         for(int i = 1; i < k; ++i) c[i] += c[i-1];          //累加,记录当前位数<=i的个数
    13         for(int i = 0; i < len; ++i) b[--c[radix]] = a[i];  //理同计数排序
    14         for(int i = 0; i < len; ++i) a[i] = b[i];           //每次排序完都要替换原数组
    15         t *= 10;                                            //此处从低位开始排序,所以是*10
    16     }
    17 }

### 桶排序 ###

1 void bucket_sort(int *a, int len, int k = 1){  //桶排序
     2     int n = 0;                                 //k表示桶的容量,默认为1,n用于记录桶的个数,不过先要计算一下
     3     for(int i = 0; i < len; ++i)               //n记录当前数组最大值
     4         if(a[i] > n)
     5             n = a[i];
     6     n = n/k + 1;                               //此时n为最大的数,计算后为桶个数,加一保证不会溢出
     7     node *b = new node[n];                     //申请所有桶的空间,桶的区间分别是[0,k),[k,2*k)~~~,共有n个
     8     for(int i = 0; i < len; ++i){              //将a[i]一个一个放入对应的桶中,分配的过程
     9         node *p, *t = new node(a[i]);          //因为是链表存储,申请一个结点存储信息
    10         for(p = &b[a[i]/k]; p->next && p->next->x < t->x; p = p->next);  //在对应桶中找到该插入的地方
    11         t->next = p->next;                     //将后一个结点连接到新结点
    12         p->next = t;                           //将前一个结点连接到新结点
    13     }
    14     for(int t = 0,i = 0; i < n; ++i)//将每个桶一次收集到原数组中
    15         for(node *p = b[i].next; p; p = p->next)//收集一个桶的过程
    16             a[t++] = p->x;
    17 }

### 简单排序（冒泡、选择、插入排序） ###

1 template <class T>
     2 void bubble_sort(T *a, int len){        //冒泡排序
     3     for(int i = 0; i < len-1; ++i)      //比较len-1趟,每趟将最大值沉底
     4     for(int j = 0; j < len-1-i; ++j)    //每趟比较次数,比较区间为[0,len-i]
     5         if(a[j] > a[j+1])
     6             swap(a[j],a[j+1]);
     7 }
     8 
     9 template <class T>
    10 void select_sort(T *a,int len){        //选择排序
    11     for(int i = 0; i < len-1; ++i){    //选择len-1趟
    12     int t = i;                         //标记需要替换的位置
    13     for(int j = i+1; j < len; ++j)     //查找最小值的位置
    14     if(a[t] > a[j])
    15         t = j;
    16         swap(a[i],a[t]);               //与标记位置替换
    17     }
    18 }
    19 
    20 template <class T>
    21 void insert_sort(T *a, int l, int r){        //插入排序
    22     for(int i = l+1; i <= r; ++i){
    23     //将数组分为a[l]和a[l+1]~a[r]两堆,将后面一堆依次插入前面完成排序
    24     T key = a[i]; int j;                     //记录要插入的数,移动前面元素时可能覆盖此处
    25     for(j = i-1; j >= l && a[j] > key; --j)  //往前找可以插入的位置
    26         a[j+1] = a[j];                       //移动，将该插入的位置空出
    27         a[j+1] = key;                        //插入
    28     }
    29 }

### 希尔排序 ###

1 template <class T>
    2 void shell_sort(T *a, int len){                              //希尔排序
    3     for(int gap = len>>1; gap; gap >>= 1)                    //步数,这不是最优序列,选择len/2,并每次减少一半
    4     for(int i = gap; i < len; ++i)                           //此处为减少代码量的写法,每次之间从步数位置开始
    5     for(int j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap)  //从步数位置往前进行冒泡排序
    6         swap(a[j],a[j+gap]);
    7     //注:此处冒泡与普通冒泡不太一样,可自行验证,区别只是交换的顺序发生变化
    8 }

### 归并排序（下附原地归并排序） ###

1 template <class T>
     2 void merge(T *a, int l, int m, int r){    //归并
     3     //可以进行归并的前提是a[i,m]、a[j,r]已经有序
     4     int i = l, j = m+1, k = 0;            //将数组分成a[i,m],a[j,r]两个数组
     5     T *t = new T[LEN];                    //LEN = r-l+1,t数组储存归并后的数列
     6     while(i <= m && j <= r)               //在其中一个数组放完之前
     7         if(a[i] < a[j]) t[k++] = a[i++];  //将其中小的放进t数组
     8         else t[k++] = a[j++];
     9     while(i <= m) t[k++] = a[i++];        //若a[l,m]中元素未放完,将剩下的放进t数组中
    10     while(j <= r) t[k++] = a[j++];        //若a[j,r]中元素为放完,将剩下的放进t数组中
    11     for(i = 0; i < k; ++i)                //放回原数组中
    12         a[l+i] = t[i];
    13 }
    14 template <class T>
    15 void merge_sort(T *a, int l, int r){  //归并排序
    16     if(l >= r) return;                //只有元素个数>1才需要排序
    17     int m = (l+r)/2;                  //计算中间点
    18     merge_sort(a,l,m);                //排序a[l,m]
    19     merge_sort(a,m+1,r);              //排序a[m+r,r]
    20     merge(a,l,m,r);                   //排序好a[l,m]和a[m+1,r]后就可以进行归并
    21 }

### 原地归并排序 ###

1 template <class T>
     2 void exchange(T *a, int l, int r){  //逆序,即将序列(a0,a1,...,an-1,an)变换为(an,an-1,...,a1,a0)
     3  while(l < r)                       //这逆序,看不懂么。。。
     4  swap(a[l++],a[r--]);
     5 }
     6 template <class T>
     7 void remove(T *a, int l, int r, int x, int y){  //交换[l,r]和[x,y]数组
     8     //手摇算法使用O(1)的空间交换[l,r]和[x,y]数组
     9     //在区间[l,y]中(x = r+1)
    10     //逆序[l,r],再逆序[x,y],在逆序[l,y]
    11     //实现[l,r]、[x,y]的交换
    12     exchange(a,l,r);
    13     exchange(a,x,y);
    14     exchange(a,l,y);
    15 }
    16 template <class T>
    17 void in_place_merge(T *a, int l, int m, int r){  //原地归并
    18     /*
    19       1.将a[l,r]分成a[i,m]和a[m+1,r],且两数组均有序
    20       2.从a[i]开始往后找> a[j]的数,设为a[k]
    21       3.从a[j]开始往后找>=a[k]的数,设为a[t]
    22       4.交换a[k,j-1]、a[j,t],此时a[i,j-t)有序
    23       5.重复1~4直到a[l,r]有序
    24     */
    25     int i = l,j = m+1,index;
    26     while(i < j && j <= r){                //当i == j 或者j == r就已经全部有序了
    27         while(i < j && a[i] <= a[j]) ++i;  //从a[i]往后找 > a[j],找到后a[k] = a[i]
    28         index = j;                         //记录a[j]，即a[index] = a[j]
    29         while(j <= r && a[j] < a[i]) ++j;  //从a[j]往后找>= a[i](即a[k]),找到后a[t] = a[j]
    30         remove(a,i,index-1,index,j-1);     //交换a[i,index-1]、a[index,j-1]
    31         i += j-index;                      //将i移到无序的起点,继续排序
    32     }
    33 }
    34 template <class T>
    35 void in_place_merge_sort(T *a, int l, int r){  //原地归并排序
    36     if(l >= r) return;                         //此处和前面归并同理
    37     int m = (l+r)/2;
    38     in_place_merge_sort(a,l,m);
    39     in_place_merge_sort(a,m+1,r);
    40     in_place_merge(a,l,m,r);
    41 }

### 快速排序 ###

1 template <class T>
     2 void quick_sort1(T *a, int l , int r){
        //快速排序数据结构版
     3     if(l >= r) return;
     4     int m = choose(l,r);
     5     if(m != l) swap(a[l],a[m]);
     6     int i = l, j = r, t = a[l];
     7     while(i < j){
     8         while(i < j && a[j] >= t) --j; a[i] = a[j];
     9         while(i < j && a[i] <= t) ++i; a[j] = a[i];
    10     }
    11     a[i] = t;
    12     quick_sort1(a,l,i-1);
    13     quick_sort1(a,i+1,r);
    14 }
    15 template <class T>
    16 void quick_sort2(T *a, int l, int r){  //快速排序算法导论版
    17     if(l >= r) return;
    18     int m = choose(l,r);               //随机选择枢轴
    19     if(m != r) swap(a[m],a[r]);
    20     int t = a[r], j = l-1;
    21     for(int i = l; i <= r; ++i)
    22         if(a[i] < t){
    23             ++j;
    24             if(i != j)
    25                 swap(a[i],a[j]);
    26         }
    27     swap(a[r],a[j+1]);
    28     quick_sort2(a,l,j);
    29     quick_sort2(a,j+2,r);
    30 }

#### 关于快速排序的枢轴问题 ####

关于从左还是从右开始走的问题。  
假设先选t = a\[l\]作为枢轴  
先左后右的排序一趟, i = j且a\[i\] >= t  
此时\[l,i-1\]所以元素 <= t, \[i,r\] >= t  
当a\[i\] > t时,再与a\[l\]交换,a\[l\] > a\[i\]  
可见此时左边出现大于枢轴的元素,排序会出错  
同理可证以a\[r\]作为枢轴,先有后左也会出错  
所以只要保证以左边作为枢轴时从右边开始,反之亦可

### 堆排序 ###

1 template <class T>
     2 void ajust_heap(T *a, int p, int len){       //构造大根堆
     3     int t = a[p], c = p<<1|1;                //记录初始父亲结点,选择左儿子
     4     while(c < len){                          //保证儿子存在
     5         if(c+1 < len && a[c+1] > a[c]) ++c;  //若右儿子存在且右儿子>左儿子,选择右儿子
     6         if(t >= a[c]) break;
     7         //因为此函数目的就是保证初始父亲都大于其儿子
     8         //a[c]的儿子 <= a[c]<= t,就不用下去了
     9         a[p] = a[c];                         //找到a[c] > a[p],上移
    10         p = c;                               //往下走,更新父亲位置
    11         c = c<<1|1;                          //往下走,更新儿子结点
    12     }
    13     a[p] = t;                                //最后的的父亲结点且其儿子全部 <= t,即找到初始父亲结点该放的位置
    14 }
    15 template <class T>
    16 void heap_sort(T *a, int len){      //堆排序
    17     for(int i = len>>1; i >= 0 ; --i)  //从最大的父亲结点开始往前构造大根堆,保证小的父亲结点构造时下面已经有序
    18     ajust_heap(a,i,len);               //大根堆保证a[0]在[0,len-1]最大
    19     for(int i = len-1; i ; --i){
    20         swap(a[0],a[i]);
    21         ajust_heap(a,0,i);
    22         //将a[0]放到a[len-1],此时a[len-1]最大
    23         //再将[0,len-2]构造大根堆,将a[0]放到a[len-2],此时a[len-2]第二大
    24         //以此类推,直到整个序列有序
    25     }
    26 }

转载于:https://www.cnblogs.com/qq188380780/p/8283107.html

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0
[Link 2]: https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
[Link 3]: https://baike.baidu.com/item/%E5%86%85%E9%83%A8%E6%8E%92%E5%BA%8F