C语言的几个算法排序.doc

算法排序/xiajun07061225/article/details/6898246下面简要总结了常用的一些排序算法。如有错误，还请大家指正、见谅谢谢【1】插入排序：是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度：O(n2)，空间复杂度：O(1)。是稳定的排序方法。代码：view plaincopy to clipboardprint?1. /insertionsort 2. #include 3. usingnamespacestd;4. 5. /insertionsort 6. voidInsertionSort(int*a,intn)7. 8. inttemp;9. for(inti=1;i=0&*(a+j)temp)14. 15. *(a+j+1)=*(a+j);16. -j;17. 18. *(a+j+1)=temp;19. 20. 21. 22. intmain()23. 24. intn,temp;25. coutpleaseinputthenumberofthevaluesthatneedtosort:n;27. int*a=(int*)malloc(n*sizeof(int);28. coutpleaseinputeachvalue:endl;29. for(inti=0;itemp;32. *(a+i)=temp;33. 34. /*35. /insertionsort36. for(inti=1;i=0&*(a+j)temp)41. 42. *(a+j+1)=*(a+j);43. -j;44. 45. *(a+j+1)=temp;46. */47. InsertionSort(a,n);48. 49. coutthevaluesaftersort:endl;50. for(inti=0;in;+i)51. cout*(a+i)*(a+low)return(low+1);8. else9. returnlow;10. 11. intmid=(low+high)/2;12. if(val*(a+mid)&val*(a+mid+1)13. returnInsertLoc(a,mid+1,high,val);14. elseif(val*(a+mid)&val*(a+mid+1)15. returnInsertLoc(a,low,mid,val);16. else17. returnmid;18. 19. 20. voidInsertionSort(int*a,intn)21. 22. inttemp,insert_location;23. for(inti=1;in;+i)24. 25. temp=*(a+i);26. intj=i-1;27. insert_location=InsertLoc(a,0,j,temp);28. coutinsert_location:insert_location=insert_location)30. 31. *(a+j+1)=*(a+j);32. -j;33. 34. *(a+insert_location)=temp;35. for(intm=0;m=i;+m)36. cout*(a+m);37. coutendl;38. 39. 【2】选择排序第一次找出A0,.,n-1的最小的元素，与A0交换，接着，找出A1,.,n-1的次小得元素，与A1互换。对A中头n-1个元素执行这一过程。时间复杂度：O(n2)，空间复杂度O(1)。是不稳定的排序方法。比如序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是不稳定的排序算法。但是严蔚敏的数据结构书上面Page289页说，所有时间复杂度为O(n2)的简单排序都是稳定的。不知道为什么？求指导其给出的简单排序的伪代码：view plaincopy to clipboardprint?1. voidSelectSort(SqList&L)2. 3. /对顺序表L做简单排序 4. for(i=1;iL.length;+i)/选择第i小得记录，并交换到位 5. 6. j=SelectMinKey(L,i);/在L.ri.L.length中选择key最小的记录 7. if(i!=j)/与第i个记录交换 8. 9. temp=L.ri;10. L.ri=L.rj;11. L.rj=temp;12. 13. 14. 代码：view plaincopy to clipboardprint?1. /选择排序 2. #include 3. usingnamespacestd;4. 5. voidChoseSort(int*a,intn)6. 7. inttemp,minVal,minIndex;8. for(inti=0;in-1;+i)9. 10. minVal=*(a+i);/记录ai,.,n-1之间的最小值 11. minIndex=i;/记录ai,.,n-1之间的最小值的下标 12. for(intj=i+1;j*(a+j)15. 16. minVal=*(a+j);17. minIndex=j;18. 19. 20. /交换ai和ai,.,n-1之间的最小值最小值 21. if(minIndex!=i)22. 23. temp=*(a+i);24. *(a+i)=*(a+minIndex);25. *(a+minIndex)=temp;26. 27. 28. 29. 30. intmain()31. 32. intn,temp;33. coutpleaseinputthenumberofthevaluesthatneedtosort:n;35. int*a=(int*)malloc(n*sizeof(int);36. coutpleaseinputeachvalue:endl;37. for(inti=0;itemp;40. *(a+i)=temp;41. 42. ChoseSort(a,n);43. coutthevaluesaftersort:endl;44. for(inti=0;in;+i)45. cout*(a+i);46. free(a);47. 【3】合并排序采用分治法。将n个元素分成各含n/2个元素的子序列，用合并排序法对两个子序列递归的排序(子序列长度为1时递归结束)，最后合并两个已排序的子序列得到结果。时间复杂度：O(nlogn)，空间复杂度：O(n)。是稳定的排序方法。代码：view plaincopy to clipboardprint?1. /合并排序 2. #include 3. usingnamespacestd;4. 5. #defineMAX_VALUE100000/用于设置哨兵，避免检查是否每一个堆都是空的 6. 7. /合并两个子数组的函数 8. voidMerge(int*a,intp,intq,intr)9. 10. intnum1,num2;11. num1=q-p+1;12. num2=r-q;13. int*a1=(int*)malloc(num1+1)*sizeof(int);14. int*a2=(int*)malloc(num2+1)*sizeof(int);15. for(inti=0;inum1;+i)16. *(a1+i)=*(a+p+i);17. *(a1+num1)=MAX_VALUE;/设置哨兵元素 18. for(inti=0;inum2;+i)19. *(a2+i)=*(a+q+1+i);20. *(a2+num2)=MAX_VALUE;/设置哨兵元素 21. 22. /进行排序 23. intindex1=0;24. intindex2=0;25. for(inti=p;i=r;+i)26. 27. if(*(a1+index1)*(a2+index2)28. 29. *(a+i)=*(a1+index1);30. +index1;31. 32. else33. 34. *(a+i)=*(a2+index2);35. +index2;36. 37. 38. free(a1);view plaincopy to clipboardprint?1. free(a2);view plaincopy to clipboardprint?1. view plaincopy to clipboardprint?1. /递归合并排序算法 2. voidMergeSort(int*a,intp,intr)3. 4. if(pr)5. 6. intq=(p+r)/2;7. MergeSort(a,p,q);8. MergeSort(a,q+1,r);9. Merge(a,p,q,r);10. 11. 12. 13. intmain()14. 15. intn,temp;16. coutpleaseinputthenumberofthevaluesthatneedtosort:n;18. int*a=(int*)malloc(n*sizeof(int);19. coutpleaseinputeachvalue:endl;20. for(inti=0;itemp;23. *(a+i)=temp;24. 25. MergeSort(a,0,n-1);26. coutthevaluesaftersort:endl;27. for(inti=0;in;+i)28. cout*(a+i);29. free(a);view plaincopy to clipboardprint?1. 如果不使用哨兵元素，需要修改Merge函数，如下：view plaincopy to clipboardprint?1. /合并两个子数组的函数(不使用哨兵元素) 2. voidMerge(int*a,intp,intq,intr)3. 4. intnum1,num2;5. num1=q-p+1;6. num2=r-q;7. int*a1=(int*)malloc(num1*sizeof(int);8. int*a2=(int*)malloc(num2*sizeof(int);9. for(inti=0;inum1;+i)10. *(a1+i)=*(a+p+i);11. for(inti=0;inum2;+i)12. *(a2+i)=*(a+q+1+i);13. 14. /进行排序 15. intindex1=0;16. intindex2=0;17. intindex=p;18. while(index1num1&index2num2)19. 20. if(*(a1+index1)*(a2+index2)21. 22. *(a+index)=*(a1+index1);23. +index;24. +index1;25. 26. else27. *(a+index)=*(a2+index2);28. +index;29. +index2;30. 31. 32. while(index1num1)33. 34. *(a+index)=*(a1+index1);35. +index;36. +index1;37. 38. while(index2num2)39. 40. *(a+index)=*(a2+index2);41. +index;42. +index2;43. 44. free(a1);free(a2);view plaincopy to clipboardprint?1. 【4】冒泡排序每一趟都比较相邻两个元素，若是逆序的，则交换。结束的条件应该是“在一趟排序过程中没有进行过交换元素的操作”。时间复杂度：O(n2)，空间复杂度O(1)。是稳定的排序。view plaincopy to clipboardprint?1. #include 2. usingnamespacestd;3. 4. voidBubbleSort(int*a,intn)5. 6. intflag,temp;/标记是否进行过交换操作 7. for(inti=0;in-1;+i)8. 9. flag=0;10. for(intj=0;j*(a+j+1)13. 14. temp=*(a+j);15. *(a+j)=*(a+j+1);16. *(a+j+1)=temp;17. flag=1;18. 19. 20. if(flag=0)break;21. 22. 23. 24. intmain()25. 26. intn,temp;27. coutpleaseinputthenumberofthevaluesthatneedtosort:n;29. int*a=(int*)malloc(n*sizeof(int);30. coutpleaseinputeachvalue:endl;31. for(inti=0;itemp;34. *(a+i)=temp;35. 36. BubbleSort(a,n);37. coutthevaluesaftersort:endl;38. for(inti=0;in;+i)39. cout*(a+i);40. free(a);view plaincopy to clipboardprint?1. 【5】快速排序它是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序元素分成两个部分，其中一部分元素比另一部分元素小。再分别对这两部分元素进行排序。以达到整个元素序列有序。时间复杂度：O(nlogn)，空间复杂度O(logn)，是不稳定的算法。代码：view plaincopy to clipboardprint?1. #include 2. usingnamespacestd;3. 4. intPartition(int*a,intlow,inthigh)5. 6. intPivotKey=*(a+low);/用第一个元素做枢轴 7. while(lo