2022年C语言种排序算法及其实现 .pdf
C 语言 6 种排序算法及其实现C 语言中常见的排序算法：冒泡排序法、选择排序法、插入排序法、快速排序法、希尔排序法、堆排序法6 种。1.冒泡排序算法思想简单描述：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。冒泡排序是稳定的。算法时间复杂度O(n2)。main() int a10,i,j,k; printf(This is a maopao sortn); printf(Please input 10 numbers for sort:); for(i=0;i10;i+)scanf(%d,&ai); for(i=0;i9;i+) for(j=0;jaj+1) k=aj; aj=aj+1; aj+1=k; printf(The corret sort of those numbers is:); for(i=0;i10;i+) printf( %d,ai); printf(n); 2.选择排序算法思想简单描述：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。选择排序是不稳定的。算法复杂度O(n2)。main() int t,k,i,j,a10; printf(This is a select sortn); printf(Please input some number that you want to sort:); for(i=0;i10;i+) scanf(%d,&ai); for(i=0;i9;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - k=i; for(j=i+1;jaj) k=j; t=ai; ai=ak; ak=t; printf(The correct sort of those number is:); for(i=0;i=2 个数已经是排好顺序的，现在要把第n 个数插到前面的有序数中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。直接插入排序是稳定的。算法时间复杂度O(n2)。main() int a10,j,i,m; printf(this is a insert sortn); printf(Please input the 10 number you want to sort:); for(i=0;i10;i+)scanf(%d,&ai); for(j=1;j=0;i-) if(aim) break; else ai+1=ai; ai+1=m; printf(The correct order of those numbers is:); for(i=0;i10;i+) printf( %d,ai); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 4.快速排序算法思想简单描述：快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后， 使得排序序列的长度能大幅度地减少。在冒泡排序中， 一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保以某个数为基准点的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。显然快速排序可以用递归实现，当然也可以用栈化解递归实现。快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n) ，最坏 O(n2)。quick(int first,int end,int L) int left=first,right=end,key; key=Lfirst; while(leftright) while(left=key) right-; if(leftright) Lleft+=Lright; while(leftright)&(Lleft=key) left+; if(leftfirst) split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); main() int a10,i; printf(This is a quick sortn); printf(Please input 10 numbers for sort:); for(i=0;i10;i+) scanf(%d,&ai); quick_sort(a,0,9); printf(The correct sort of those numbers is:); for(i=0;i0; h=h/2) /*控制增量 */ for (j=h; j=0 & t=h2i,hi=2i+1 ）或（hi=h2i,hi=2i+1 ）(i=1,2,.,n/2) 时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆， 这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1) 个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n 个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。有最大堆和最少堆之分堆排序是不稳定的。算法时间复杂度O(nlog2n) 。功能：渗透建堆void sift(int *x, int n, int s) int t, k, j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - t = *(x+s); /* 暂存开始元素*/ k = s; /*开始元素下标*/ j = 2*k + 1; /* 右子树元素下标*/ while (jn) if (jn-1 & *(x+j) *(x+j+1)/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。 */ j+; if (t=0; i-) sift(x,n,i); /* 初始建堆 */ for (k=n-1; k=1; k-) t = *(x+0); /* 堆顶放到最后*/ *(x+0) = *(x+k); *(x+k) = t; sift(x,k,0); /* 剩下的数再建堆*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -
