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 
 25 int choose(int l, int r){//选择[l,r]直接的随机数
 26     srand((int)time(0));//以时间为种子
 27     int m = random(LEN)+l;
 28     return random(LEN)+l;
 29 }
 30 
 31 void count_sort(int *a, int len, int k = K){//计数排序
 32     int b[len],c[k];//b数组用于存放排序后数列,c[i]记录<=i的数的个数,k表示每位数保证在[0,k)之间
 33     for(int i = 0; i < k; ++i) c[i] = 0;//数组清零
 34     for(int i = 0; i < len; ++i) ++c[a[i]];//c[i]暂存i的个数
 35     for(int i = 1; i < k; ++i) c[i] += c[i-1];//加上前面的就是<=i的数的个数
 36     for(int i = 0; i < len; ++i) b[--c[a[i]]] = a[i];
 37     //--的目的有两个: 1.数组是从0开始;
 38     //              2.下一次这个元素往前要挪一位
 39     //              (为什么是往前,因为记录的是<=i的个数
 40     //               所以当出现相同的值时，c[i]开始表示
 41     //               该元素的最后一个位置)
 42     for(int i = 0; i < len; ++i) a[i] = b[i];//排序后数组放回原来的数组
 43 }
 44 
 45 void radix_sort(int *a, int len, int k = 10){//基数排序
 46     int b[len],c[k],d = 1,t = 1;
 47     //b记录每次排序后数组,c记录当前位<=i的数的个数,d记录最大位数,t记录当前位的位权,k表示一位的值在[0,k)直接
 48     for(int p = 10,i = 0; i < len; ++i)//查找最大位数
 49         while(p <= a[i]){
 50             p *= 10;
 51             ++d;
 52         }
 53     for(int j = 1; j <= d; ++j){//此处代表位数,MSD、LSD皆可
 54         for(int i = 0; i < k; ++i) c[i] = 0;//清零
 55         for(int i = 0; i < len; ++i) ++c[radix];//radix是当前位的值,记录其个数,宏定义: radix (a[i]/t%10)
 56         for(int i = 1; i < k; ++i) c[i] += c[i-1];//累加,记录当前位数<=i的个数
 57         for(int i = 0; i < len; ++i) b[--c[radix]] = a[i];//理同计数排序
 58         for(int i = 0; i < len; ++i) a[i] = b[i];//每次排序完都要替换原数组
 59         t *= 10;//此处从地位开始排序,所以是*10
 60     }
 61 }
 62 
 63 void bucket_sort(int *a, int len, int k = 1){//桶排序
 64     int n = 0;//k表示桶的容量,默认为1,n用于记录桶的个数,不过先要计算一下
 65     for(int i = 0; i < len; ++i)//n记录当前数组最大值
 66         if(a[i] > n)
 67             n = a[i];
 68     n = n/k + 1;//此时n为最大的数,计算后为桶个数,加一保证不会溢出
 69     node *b = new node[n];//申请所有桶的空间,桶的区间分别是[0,k),[k,2*k)~~~,共有n个
 70     for(int i = 0; i < len; ++i){//将a[i]一个一个放入对应的桶中,分配的过程
 71         node *p, *t = new node(a[i]);//因为是链表存储,申请一个结点存储信息
 72         for(p = &b[a[i]/k]; p->next && p->next->x < t->x; p = p->next);//在对应桶中找到该插入的地方
 73         t->next = p->next;//将后一个结点连接到新结点
 74         p->next = t;//将前一个结点连接到新结点
 75     }
 76     for(int t = 0,i = 0; i < n; ++i)//将每个桶一次收集到原数组中
 77         for(node *p = b[i].next; p; p = p->next)//收集一个桶的过程
 78             a[t++] = p->x;
 79 }
 80 
 81 template <class T>
 82 void bubble_sort(T *a, int len){//冒泡排序
 83     for(int i = 0; i < len-1; ++i)//比较len-1趟,每趟将最大值沉底
 84         for(int j = 0; j < len-1-i; ++j)//每趟比较次数,比较区间为[0,len-i]
 85             if(a[j] > a[j+1])
 86                 swap(a[j],a[j+1]);
 87 }
 88 
 89 template <class T>
 90 void select_sort(T *a,int len){//选择排序
 91     for(int i = 0; i < len-1; ++i){//选择len-1趟
 92         int t = i;//标记需要替换的位置
 93         for(int j = i+1; j < len; ++j)//查找最小值的位置
 94             if(a[t] > a[j])
 95                 t = j;
 96         swap(a[i],a[t]);//与标记位置替换
 97     }
 98 }
 99 
100 template <class T>
101 void insert_sort(T *a, int l, int r){//插入排序
102     for(int i = l+1; i <= r; ++i){
103     //将数组分为a[l]和a[l+1]~a[r]两堆,将后面一堆依次插入前面完成排序
104         T key = a[i]; int j;//记录要插入的数,移动前面元素时可能覆盖此处
105         for(j = i-1; j >= l && a[j] > key; --j)//往前找可以插入的位置
106             a[j+1] = a[j];//移动，将该插入的位置空出
107         a[j+1] = key;//插入
108     }
109 }
110 
111 template <class T>
112 void shell_sort(T *a, int len){//希尔排序
113     for(int gap = len>>1; gap; gap >>= 1)//步数,这不是最优序列,选择len/2,并每次减少一半
114         for(int i = gap; i < len; ++i)//此处为减少代码量的写法,每次之间从步数位置开始
115             for(int j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap)//从步数位置往前进行冒泡排序
116                 swap(a[j],a[j+gap]);
117     //注:此处冒泡与普通冒泡不太一样,可自行验证,区别只是交换的顺序发生变化
118 }
119 
120 template <class T>
121 void merge(T *a, int l, int m, int r){//归并
122     //可以进行归并的前提是a[i,m]、a[j,r]已经有序
123     int i = l, j = m+1, k = 0;//将数组分成a[i,m],a[j,r]两个数组
124     T *t = new T[LEN];//LEN = r-l+1,t数组储存归并后的数列
125     while(i <= m && j <= r)//在其中一个数组放完之前
126         if(a[i] < a[j]) t[k++] = a[i++];//将其中小的放进t数组
127         else t[k++] = a[j++];
128     while(i <= m) t[k++] = a[i++];
129     //若a[l,m]中元素未放完,将剩下的放进t数组中
130     while(j <= r) t[k++] = a[j++];
131     //若a[j,r]中元素为放完,将剩下的放进t数组中
132     for(i = 0; i < k; ++i)//放回原数组中
133         a[l+i] = t[i];
134 }
135 template <class T>
136 void merge_sort(T *a, int l, int r){//归并排序
137     if(l >= r) return;//只有元素个数>1才需要排序
138     int m = (l+r)/2;//计算中间点
139     merge_sort(a,l,m);//排序a[l,m]
140     merge_sort(a,m+1,r);//排序a[m+r,r]
141     merge(a,l,m,r);//排序好a[l,m]和a[m+1,r]后就可以进行归并
142 }
143 
144 template <class T>
145 void exchange(T *a, int l, int r){//逆序
146     while(l < r)//这逆序,看不懂么。。。
147         swap(a[l++],a[r--]);
148 }
149 template <class T>
150 void remove(T *a, int l, int r, int x, int y){//交换[l,r]和[x,y]数组
151     //手摇算法使用O(1)的空间交换[l,r]和[x,y]数组
152     //在区间[l,y]中(x = r+1)
153     //逆序[l,r],再逆序[x,y],在逆序[l,y]
154     //实现[l,r]、[x,y]的交换
155     exchange(a,l,r);
156     exchange(a,x,y);
157     exchange(a,l,y);
158 }
159 template <class T>
160 void in_place_merge(T *a, int l, int m, int r){//原地归并
161     /*
162     1.将a[l,r]分成a[i,m]和a[m+1,r],且两数组均有序
163     2.从a[i]开始往后找> a[j]的数,设为a[k]
164     3.从a[j]开始往后找>=a[k]的数,设为a[t]
165     4.交换a[k,j-1]、a[j,t],此时a[i,j-t)有序
166     5.重复1~4直到a[l,r]有序
167     */
168     int i = l,j = m+1,index;
169     while(i < j && j <= r){//当i == j 或者j == r就已经全部有序了
170         while(i < j && a[i] <= a[j]) ++i;//从a[i]往后找 > a[j],找到后a[k] = a[i]
171         index = j;//记录a[j]，即a[index] = a[j]
172         while(j <= r && a[j] < a[i]) ++j;//从a[j]往后找>= a[i](即a[k]),找到后a[t] = a[j]
173         remove(a,i,index-1,index,j-1);//交换a[i,index-1]、a[index,j-1]
174         i += j-index;//将i移到无序的起点,继续排序
175     }
176 }
177 template <class T>
178 void in_place_merge_sort(T *a, int l, int r){//原地归并排序
179     if(l >= r) return;//此处和前面归并同理
180     int m = (l+r)/2;
181     in_place_merge_sort(a,l,m);
182     in_place_merge_sort(a,m+1,r);
183     in_place_merge(a,l,m,r);
184 }
185 
186 /*
187 快速排序这个无数人写烂的排序。
188 此处不多说,仅说一点。关于从左还是从右开始走的问题。
189 
190 假设先选t = a[l]作为枢轴
191 先左后右的排序一趟, i = j且a[i] >= t
192 此时[l,i-1]所以元素 <= t, [i,r] >= t
193 当a[i] > t时,再与a[l]交换,a[l] > a[i]
194 可见此时左边出现大于枢轴的元素,排序会出错
195 
196 同理可证以a[r]作为枢轴,先有后左也会出错
197 
198 所以只要保证以左边作为枢轴时从右边开始,反之亦可
199 */
200 template <class T>
201 void quick_sort1(T *a, int l , int r){//快速排序数据结构版
202     if(l >= r) return;
203     int m = choose(l,r);
204     if(m != l) swap(a[l],a[m]);
205     int i = l, j = r, t = a[l];
206     while(i < j){
207         while(i < j && a[j] >= t) --j; a[i] = a[j];
208         while(i < j && a[i] <= t) ++i; a[j] = a[i];
209     }
210     a[i] = t;
211     quick_sort1(a,l,i-1);
212     quick_sort1(a,i+1,r);
213 }
214 template <class T>
215 void quick_sort2(T *a, int l, int r){//快速排序算法导论版
216     if(l >= r) return;
217     int m = choose(l,r);//随机选择枢轴
218     if(m != r) swap(a[m],a[r]);
219     int t = a[r], j = l-1;
220     for(int i = l; i <= r; ++i)
221         if(a[i] < t){
222             ++j;
223             if(i != j)
224                 swap(a[i],a[j]);
225         }
226     swap(a[r],a[j+1]);
227     quick_sort2(a,l,j);
228     quick_sort2(a,j+2,r);
229 }
230 
231 template <class T>
232 void ajust_heap(T *a, int p, int len){//构造大根堆
233     int t = a[p], c = p<<1|1;//记录初始父亲结点,选择左儿子
234     while(c < len){//保证儿子存在
235         if(c+1 < len && a[c+1] > a[c]) ++c;
236         //若右儿子存在且右儿子>左儿子,选择右儿子
237         if(t >= a[c]) break;
238         //因为此函数目的就是保证初始父亲都大于其儿子
239         //a[c]的儿子 <= a[c]<= t,就不用下去了
240         a[p] = a[c];//找到a[c] > a[p],上移
241         p = c;//往下走,更新父亲位置
242         c = c<<1|1;//往下走,更新儿子结点
243     }
244     a[p] = t;
245     //最后的的父亲结点且其儿子全部 <= t,即找到初始父亲结点该放的位置
246 }
247 template <class T>
248 void heap_sort(T *a, int len){//堆排序
249     for(int i = len>>1; i >= 0 ; --i)
250     //从最大的父亲结点开始往前构造大根堆,保证小的父亲结点构造时下面已经有序
251         ajust_heap(a,i,len);
252     //大根堆保证a[0]在[0,len-1]最大
253     for(int i = len-1; i ; --i){
254         swap(a[0],a[i]);
255         //将a[0]放到a[len-1],此时a[len-1]最大
256         //再将[0,len-2]构造大根堆,将a[0]放到a[len-2],此时a[len-2]第二大
257         //以此类推,直到整个序列有序
258         ajust_heap(a,0,i);
259     }
260 }