当前位置:   article > 正文

冒泡排序、快速排序算法理解及C程序实现_实现冒泡排序和快速排序算法主函数怎么写

实现冒泡排序和快速排序算法主函数怎么写

前言:关于 快速排序算法的相关理解,本文借鉴了 啊哈磊 老师的《常用排序——快速排序》 ,在此向作者 致敬,写的挺好。

目录

 

一、冒泡排序

二、快速排序

三、小结


一、冒泡排序

    冒泡排序是各种教材中 经常提到的一种排序 方法,基本思想就是:

    ① 从数组的头部开始,比较相邻两个数,如果第1个数比第2个数大,就交换他们两个。也就是让较大

  的数逐渐往后 移动,直到数组的末尾,经过第一轮的比较,就可以找到最大的元素,并将它移动到最后一个位置。

   ② 第一轮结束后,继续第二轮,仍然从数组的头部开始比较,直到数组的倒数第2个元素为止,经过第2轮比较,就可以找到次大的元素,并将它放到倒数第二个位置。

   ③ 一次类推,经过n-1轮“冒泡”后,就可以将所有的元素都排列好。

C程序代码如下:

  1. /*
  2. * 冒泡排序函数。
  3. *
  4. * src:数据源指针。
  5. *
  6. * n : 数组大小。
  7. *
  8. * 注意 :经过排序后,会打乱 src 源数组,呈递增排序。
  9. */
  10. void bubbleSort(int *src, int n)
  11. {
  12. int i = 0, j = 0, tmp = 0;
  13. for(i = n - 1; i > 0; --i){
  14. for(j = 0; j < i; ++j){
  15. if(src[j] > src[j + 1]){
  16. tmp = src[j];
  17. src[j] = src[j + 1];
  18. src[j + 1] = tmp; //数据交换
  19. }
  20. }
  21. }
  22. }

二、快速排序

    快速排序是对冒泡排序的一种优化,平均效率较高,为什么说平均效率高呢?如果数组的元素大小是递减排列,那么快速排序法与冒泡法的效率是一样的,只有数组元素随机排列时,其平均效率才比较高。快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法。(分治翻译的不太容易理解,应该是 分段)。

该方法的基本思想是:

① 先从数组中取出一个数作为基准数(一般取第一个数)。

② 分区过程:将比这个数大的数全部放到它的右边,小于或等于它的数,全放到它的左边。

③ 经过步骤②,我们取的那个基数就在整个数组的中间某个位置(不一定正中间),将整个数组分成了两段,左边是小于基数的一段,而右边是大于基数的一段。然后再分别对左右两段区间重复步骤②,直到各个区 间只有一个数。

下面参考 啊哈磊 老师的讲解,再来分析一下,具体操作步骤:

 啊哈磊老师的 C 程序代码,需要定义好全局 数组缓冲 区,我对其进行了修改,可以作为一个通用的“快速排序”函数,程序代码如下:

  1. /*
  2. * 快速排序算法 函数
  3. *
  4. * src : 要进行排序的数据指针。
  5. *
  6. * num :数组元素个数
  7. *
  8. * 说明: 排序完成后,会改变src原来的数据顺序,数组元素呈递增排序。
  9. */
  10. void quick_sort(int *src, int num)
  11. {
  12. int i,j,t,temp;
  13. if(num < 2)
  14. return;
  15. temp = src[0];
  16. i = 0;
  17. j = num - 1;
  18. while(i != j){
  19. //from right to left- first
  20. while((src[j] >= temp) && (i < j))
  21. j--;
  22. //from left to right
  23. while((src[i] <= temp) && (i < j))
  24. i++;
  25. //find ok
  26. if(i < j){
  27. t = src[i];
  28. src[i] = src[j];
  29. src[j] = t;
  30. }
  31. }
  32. src[0] = src[i];
  33. src[i] = temp;
  34. quick_sort(src, i);
  35. quick_sort(&src[i + 1], num - i - 1);
  36. }

 程序测试可用。

三、小结

    快速排序算法的平均效率要高于冒泡排序算法,不过由于使用了递归的思路,所以对于数据量比较小的,还是使用冒泡排序算法,对于数据量比较大的,推荐使用快速排序算法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/806122
推荐阅读
相关标签
  

闽ICP备14008679号