各类排序模板
内部排序
内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
排序是计算机程序设计中的一种重要操作，其功能是对一个 集合或序列重新排列成一个按数据元素某个相知有序的序列。排序分为两类：内排序和外排序。其中 的是目前排序方法中被认为是最好的方法。
PS：引用自
头文件、宏定义及已定义方法
1 #include2 #include 3 #include 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; //此处从低位开始排序,所以是*1016 }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 template2 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 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 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 template2 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 template2 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 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 template2 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 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 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 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 template2 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 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 template2 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 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 }