各种排序算法总结(C语言)1.ppt

明明的随机数 /problem/1 #includestdio.h int a[1001]; int main() { int i,n,t,ans=0; scanf(%d,n); for(i=1;i=n;i++) { scanf(%d,t); if(a[t]==0){a[t]=1;ans++;} } printf(%d\n,ans); for(i=1;i=1000;i++) if(a[i]==1)printf(%d ,i); } #includestdio.h int partition(int *a,int low,int high) { int pivotkey; a[0]=a[low]; pivotkey=a[low]; while(lowhigh) { while(lowhigha[high]=pivotkey) high--; a[low]=a[high]; while(lowhigha[low]=pivotkey) low++; a[high]=a[low]; } a[low]=a[0]; return low; } void sort(int *a,int low,int high) { int pivotloc; if(lowhigh) { pivotloc=partition(a,low,high); sort(a,low,pivotloc-1); sort(a,pivotloc+1,high); } } void main() { int a[21]; int *p; int i; printf(input 20 numbers:); for(i=1;i21;i++) scanf(%d,a[i]); p=a; sort(p,1,20); printf(sorted:\n); for(i=1;i21;i++) printf(%d\t,a[i]); } 冒泡排序 快速排序 直接插入排序 希尔排序 选择排序 堆排序 归并排序 6.1.1 冒泡排序 算法描述 设待排序记录序列中的记录个数为n 一般地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，如果发生逆序，则交换之 其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 6.1.1 冒泡排序 算法实例 21 25 25* 16 08 0 1 2 3 4 5 21 25* 49 25 16 49 chang=1 08 25* chang=1 08 16 chang=1 25* 25 21 49 21 25 16 08 49 6.1.1 冒泡排序 算法实例 25* 0 1 2 3 4 5 i = 4 49 16 chang=1 08 25 21 25* i = 5 49 16 chang=0 08 25 21 6.1.1 冒泡排序 算法实例 21 08 25 49 25 16 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 21 49 25 25 16 08 初始关键字 第一趟排序 第四趟排序 第二趟排序 第三趟排序 第五趟排序 6.1.1 冒泡排序 算法实现 输入n 个数给a[1] 到 a[n] for j=1 to n-1 for i=1 to n-j a[i]a[i+1] 真 假 a[i]?a[i+1] 输出a[1] 到 a[n] #include stdio.h main() { int a[11],i,j,t; printf(Input 10 numbers:\n); for(i=1;i11;i++) scanf(%d,a[i]); printf(\n); for(j=1;j=9;j++) for(i=1;i=10-j;i++) if(a[i]a[i+1]) {t=a[i]; a[i]=a[i+1]; a[i+1]=t;} printf(The sorted numbers:\n); for(i=1;i11;i++) printf(%d ,a[i]); } 6.1.2 快速排序 算法特点： 快速排序是通过比较关键码、交换记录， 以某个记录为界(该记录称为支点)