当前位置:   article > 正文

【数据结构-C语言】冒泡排序,插入排序,选择排序

【数据结构-C语言】冒泡排序,插入排序,选择排序

1、基本概念

排序是处理数据的一种最常见的操作。所谓排序就是将数据按某字段规律排列,所谓字段就是数据节点的其中一个属性。比如一个班级的学生,其字段就有学号、姓名、班级、分数等等,我们既可以针对学号排序,也可以针对分数排序。

稳定性:在一组无序数据中,若两个待排序字段一致的数据,在排序前后相对位置不变,则成排序算法是稳定的,否则是不稳定的。

内排序与外排序:如果待排序数据量不大,可以一次性全部装进内存进行处理,则称为内排序,若数据量达到无法一次性全部装进内存,而需要将数据暂存外存,分批次读入内存进行处理,则称为外排序。

2、性能分析

不同的排序算法性能不同,详细性能数据如下表所示

排序算法平均T(n)最坏T(n)最好T(n)空间复杂度稳定性
选择排序

O(n²)

O(n²)O(n²)O(1)不稳定
插入排序O(n²)O(n²)O(n)O(1)稳定
希尔排序O(n1.3)O(n²)O(n)O(1)不稳定
冒泡排序O(n²)O(n²)O(n)O(1)稳定
快速排序O(nlog2​n)O(n²)O(nlog2​n)O(nlog2​n)不稳定

从表中可以得到一些简单的指导思路:

  1. 选择排序、插入排序和冒泡排序思路简单,但时间效率较差,只适用于数据样本较小的场合,这几种算法的好处是不需要额外开辟空间,空间复杂度是常量。
  2. 希尔排序是插入排序的改进版,在平均情况下时间效率要比直接插入法好很多,也不需要额外开辟空间,要注意的是希尔排序是不稳定排序。
  3. 快速排序是所有排序算法中时间效率最高的,但由于快排是一种递归运算,对内存空间要求较高,当数据量较大时,会消耗较多的内存。

3、冒泡排序

在了解排序算法之前,首先引入两个该概念

顺序:如果两个数据的位置符合排序的需要,则称他们是顺序的。

逆序:如果两个数据的位置不符合排序需要,则称他们是逆序的。

冒泡排序基于这样一种简单的思路:从头到尾让每两个相邻的元素进行比较,顺序就保持位置不变,逆序就交换位置。可以预料,经过一轮比较,序列中具有“极值”的数据,将被挪至序列的末端。

假如序列中有n个数据,那么在最极端的情况下,只需要经过n−1轮的比较,则一定可以将所有的数据排序完毕。冒泡法排序的时间复杂度是O(n²)

 4、冒泡排序核心思想

从第一个元素开始遍历比较,用需要排序的元素与除第一个元素的其他数组元素遍历比较,第一趟排序的次数为数组长度LEN-1,第二趟排序的次数为数组长度LEN-1-第i个元素,根据自身需要排序顺序来进行if判断,建立一个临时变量来进行数组元素的交换

5、冒泡排序功能函数

  1. //冒泡排序,data为数组,len为数组长度
  2. void bubbleSort(int* data,int len)
  3. {
  4. int i,j
  5. for(i = 0;i < len - 1;i++)
  6. {
  7. for(j = 0;j < len - 1 - i;j++)
  8. {
  9. if(data[j] <= data[j + 1]) //从大到小是顺序
  10. {
  11. int tmp;
  12. tmp = data[j]; //可以将这里的几行代封装成swap()函数,让代码看起来更高级,逼格更高
  13. data[j] = data[j + 1]
  14. data[j + 1] = tmp;
  15. }
  16. }
  17. }
  18. }

注意:
上述冒泡排序中,对算法做了优化,主要有两点:
1.由于每一趟比较后,都至少有1个“极值”被移至末端,因此第i趟比较只需n−i次
2.当发现某一趟比较中全部为顺序时,则意味着序列已经有序,则可以提前退出

6、插入排序

插入排序的思路也很简单:假设前面已经有i节点是有序的,那么就从第i+1个节点开始,插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的,因此从第2个开始,不断插入前面的有序序列,直到全部排列完毕。

7、插入排序核心思想

判断特殊情况数组长度小于1,直接返回;从第i个元素开始遍历比较,建立一个临时变量tmp存放data【i】的数组,从第i-1个元素开始遍历比较,根据自身需要的顺序进行if判断,成立则进行下次循环,不成功则数组元素往后顺延一位,然后数组的第j+1个元素存放临时变量里面的值

8、插入排序实现代码

  1. void insertionSort(int *data, int len)
  2. {
  3. if(len <= 1)
  4. return;
  5. int i, j;
  6. for(i=1; i<LEN; i++)
  7. {
  8. int tmp = data[i];
  9. for(j=i-1; j>=0; j--)
  10. {
  11. if(data[j] < tmp)
  12. {
  13. break;
  14. }
  15. else
  16. {
  17. data[j+1] = data[j];
  18. }
  19. }
  20. data[j+1] = tmp; //难理解点,因为退出循环的时候j减去了1,所以j+1才是最后需要要覆盖的位置
  21. }
  22. }

9、改良版插入排序

核心思想:从第i个元素开始遍历,建立一个临时变量tmp存放data【i】;使用二分法找出合适的位置pos,判断特殊情况,如果数组长度等于0,直接退出,小于数组首元素则返回0,大于数组尾元素则返回len;使用二分法找到插入下标的值pos;然后从第i-1的元素开始遍历,数组中从第i-1到pos的元素往后面移动一位,data【pos】赋值为tmp

实现代码:

  1. void new_insertionSort(int *data, int len)
  2. {
  3. if (len <= 1)
  4. return;
  5. int i;
  6. for (i = 1; i < LEN; i++)
  7. {
  8. //采用二分法找到合适的位置
  9. int pos;
  10. pos = findPos(data, i, data[i]);
  11. //批量移动数据
  12. int tmp = data[i];
  13. int k;
  14. for (k = i - 1; k >= pos; k--)
  15. {
  16. data[k + 1] = data[k];
  17. }
  18. data[pos] = tmp;
  19. }
  20. }
  21. int findPos(int* data, int len, int a)
  22. {
  23. if (len == 0)
  24. return 0;
  25. //处理掉特殊情况
  26. if (a < data[0])
  27. return 0;
  28. else if (a > data[len - 1])
  29. return len;
  30. //处理一般情况(len >= 1)
  31. int pos = 0;
  32. int i = 0, j = len - 1;
  33. for (pos = (i + j) / 2; i < j; pos = (i + j) / 2)
  34. {
  35. if (data[pos - 1] < a && a < data[pos])
  36. {
  37. return pos;
  38. }
  39. if (a < data[pos])
  40. j = pos;
  41. else
  42. i = pos;
  43. if (pos == i) //if(i == j-1)
  44. i++;
  45. }
  46. return pos;
  47. }

10、选择排序

选择排序的思路非常简单,就是依次从头到尾挑选合适的元素放到前面。如果总共有n个节点,那么选择一个合适的节点需要比较n次,而总共要选择n次,因此总的时间复杂度O(n²)

11、选择排序核心思想

从第一个元素开始遍历,建立一个最小(大)值的变量min(max),第二次遍历从下一个数组元素的开始,根据自身需要的大小顺序,if判断出数组最小(最大)值的下标,设计一个交换两个数的函数(swap)

12、选择排序实现代码

  1. void swap(int* a, int* b)
  2. {
  3. int tmp;
  4. tmp = *a;
  5. *a = *b;
  6. *b = tmp;
  7. }
  8. void selectionSort(int *data, int len)
  9. {
  10. for (int i = 0; i < LEN; i++)
  11. {
  12. int min = i;
  13. for (int j = i + 1; j < LEN; j++)
  14. {
  15. if (data[j] < data[min])
  16. min = j;
  17. }
  18. swap(&data[i], &data[min]);
  19. }
  20. }

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

闽ICP备14008679号