1、C语言9种常用排序法讲解C语言9种常用排序法1.冒泡排序2.选择排序3.插入排序4.快速排序5.希尔排序6.归并排序7.堆排序8.带哨兵的直接插入排序9.基数排序例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序#includeint main() int i, j, n, a100, temp; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%d,&ai); for(i=0;in-1;i+) /总共需冒泡n-1次 for(j=0;jaj+1) /比较aj与aj+1,使aj+1大于aj temp = aj+1; aj+1 = aj; aj
2、= temp; for(i=0;in;i+) /打印 printf(%d ,ai); printf(n); return 0;2.选择排序#includeint main() int i, j, n, a100, t, temp; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%d,&ai); for(i=0;in-1;i+) /总共排序n-1趟 t = i; for(j=i+1;jaj) t = j; temp = ai; ai = at; at = temp; for(i=0;i=j) 从aj起，向前找小于ax的元素，同时j-，找到后，aj与a
3、x交换，x=j; 从ai起，向后找大于ax的元素，同时i+，找到后，ai与ax交换，x=i; 3.注意快排函数是迭代函数，必须要有结束条件 (因为忽略结束条件,调试了很久.)4.再对alowax-1、ax+1ahigh分别调用快排函数*/#includevoid quicksort(int a,int low,int high);int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%d,&ai); quicksort(a,0,n-1);for(i=0;i=high) return; /坑爹的结束条件，
4、return后面不能跟数值 int i=low, j= high, x=i, temp; while(i=ax&ij;j-); if(i=j即可跳出本次while循环 for(;ai=ax&ij;i+); if(ij) temp = ai; ai = aj; aj = temp; x = i; j-; else break; /跳出本次while循环 quicksort(a,low,x-1); quicksort(a,x+1,high);4.插入排序法#includevoid show(int a,int n) /输出数组 int i; for(i=0;in;i+) printf(%d ,ai
5、); printf(n);void insertsort(int a,int n);int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%d,&ai); insertsort(a,n); show(a,n); return 0;void insertsort(int a,int n) int i ,j ,k ,temp; for(i=1;in;i+) /插入ai j=i-1; for(;ai=0;j-); /寻找插入点 j+; if(j=i) /该数有序，不需要前插 continue; else te
6、mp=ai; for(k=i-1;k=j;k-) /将插入点后面的数依次后移一位 ak+1=ak; aj=temp; 5.shell排序法#includevoid show(int a,int n) /输出数组 int i; for(i=0;in;i+) printf(%d ,ai); printf(n);void shellsort(int a,int n);int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=0;i=1) for(i=k;i=ai-k) /已经有序，不需要移动 continue; else for(j=i-k;
7、aj=ai&j=0;j=j-k); j+=k; /寻找插入点aj temp = ai; / 保存ai for(l=i-k;l=j;l-=k) /依次向后移动k个位置 al+k = al; aj=temp; /插入 k = k/2; 6.归并排序归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解
8、成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序算法流程图：/*伪代码：mergesort(int a,int low,int high)；if(high-low+12)执行如下几步：(3个及以上)mid = (0+n)/2;mergesort(a,low,mid-1);mergesort(a,mid,high); 进行本轮二路归并；bsort(int low,int mid,int high);i=low,j=mid;while(imid&j=ahigh) 交换alow,ahigh; */#include
9、int other100;void exchange(int *a,int *b) int t=*a; *a=*b; *b=t;void show(int a,int n) /输出数组 int i; for(i=0;in;i+) printf(%d ,ai); printf(n);void mergesort(int a,int low,int high);int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=0;i2) /含3个以上 int mid = (high+low)/2; mergesort(a,low,mid); mer
10、gesort(a,mid+1,high); int i=low, j=mid+1, k=low; while(i=mid&j=high) if(aiaj) otherk+=aj+; while(i=mid) otherk+=ai+; while(j=high) otherk+=aj+; for(i=low;iahigh) exchange(a+low,a+high); 7.堆排序/堆排序/*(堆是一个完全二叉树，根结点值最大(小)1.heapadjust(int a,int i,int sizea) 功能:以ai为根，形成一个堆 buildheap(int a,int sizea) 功能:调用
11、heapadjust()，使a形成一个堆 heapsort(int a,int sizea) 功能:do建堆，输出堆顶while(堆不空)*/#includevoid show(int a,int n) /输出数组 int i; for(i=0;in;i+) printf(%d ,ai); printf(n);void exchange(int *a,int *b) int t=*a; *a=*b; *b=t;void heapadjust(int a,int i,int sizea) int maxi=i; int l=2*i+1; int r=2*i+2; if(i(sizea/2) /a
12、i为叶结点，则不需要调整 if(lai) /左孩子比ai大的，取左孩子下标 maxi=l; if(ramaxi) /右孩子最大，取右孩子下标 maxi=r; if(maxi!=i) /取比根大的孩子，与根调换 exchange(&amaxi,&ai); heapadjust(a,maxi,sizea); /跌倒，以amaxi为根，向下调整为大根堆。 /函数功能：从最后一个非叶结点起，向上直到根结点，逐步调整，建立大根对堆void buildheap(int a,int sizea) int i; for(i=(sizea/2-1);i=0;i-) /ai为最后一个非叶结点 heapadjust
13、(a,i,sizea); void heapsort(int a,int sizea) int i; int j=sizea; for(i=0;isizea;i+) /每次循环，都会形成一个大根堆，堆顶元素a0最大 buildheap(a,j); exchange(&a0,&a-j); /将根(最大)结点交换到后面去 /堆中元素个数减一 int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) scanf(%d,&ai); heapsort(a,n); show(a,n); return 0;8. 带哨兵的直接插入排序
14、/*从小到大排序a0用作哨兵，当某个数ai，找插入位置时，先令a0=ai，再向前比较，当比较到a0时，说明插入位置为a1,这样可以防止数组越界.*/#includevoid show(int a,int n) /输出数组 int i; for(i=1;i=n;i+) printf(%d ,ai); printf(n);void dir_insert(int a,int n) int i,j; for(i=2;ia0;j-) /插入位置：j aj+1=aj; a+j=a0; int main() int i, n, a100; while(scanf(%d,&n)!=EOF) for(i=1;i
15、=n;i+) scanf(%d,&ai); dir_insert(a,n); show(a,n); return 0;9.基数排序/基数排序/*假设输入数列最多为4位，且都是十进制数 要做4次划分、收集*/#include#include#define N 4 /每个数最多4位void show(int a,int n) /输出数组 int i; for(i=1;i=n;i+) printf(%d ,ai); printf(n);void radixsort(int c,int i,int n) /以第i位为依据进行划分和收集 int a1030=0,0,0,0,0,0,0,0,0,0; /a
16、i中收集本次划分基数为i的数 int b10=0; /bi表示本次本次划分后，基数为i的数的个数 int j,k,l,m; k=pow(10,i); l=k/10; for(j=1;j=n;j+) /一次分配的过程 m=(cj%k)/l; /判断cj在本次划分中被分到哪个部分 ambm+=cj; /分配完毕后，基数为m的数为bm个 l=1; for(m=0;m10;m+) /收集 for(j=0;jbm;j+) cl+=amj; void basesort(int c,int n) int i; for(i=1;i=N;i+) radixsort(c,i,n); int main() int i, n, c100; while(scanf(%d,&n)!=EOF) for(i=1;i=n;i+) scanf(%d,&ci); basesort(c,n); show(c,n); return 0;
