当前位置:   article > 正文

数据结构----C语言八种排序算法(冒泡排序,选择排序,直接插入排序,希尔排序,快速排序,堆排序,二路归并排序,基数排序)_c语言对于以下数组,分别用“希尔排序法”“堆排序法”“归并排序法”“基数排

c语言对于以下数组,分别用“希尔排序法”“堆排序法”“归并排序法”“基数排

一、冒泡排序

思路:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两记录交换,然后比较第二个记录和第三个记录的关键字,依次类推,直到第n-1个记录和第n个记录的关键字比较完毕为止。此过程为第一趟冒泡排序,结果使得最大的关键字被放置到最后一个记录的位置上。

                                                                                  图一   冒泡排序示例

 代码:

  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <malloc.h>
  4. #include <math.h>
  5. typedef struct stack
  6. {
  7. int *data;
  8. int top;
  9. }Stack;
  10. typedef struct Que
  11. {
  12. int *data;
  13. int head;
  14. int tail;
  15. }Que;
  16. void Swap(int *a, int *b)
  17. {
  18. int c = *a;
  19. *a = *b;
  20. *b = c;
  21. }
  22. // O(n^2) O(1) 稳定
  23. void BubbleSort(int *arr, int len)
  24. {
  25. int i = 0;
  26. int j = 0;
  27. for(i=0; i<len-1; ++i)
  28. {
  29. for(j=0; j<len-1-i; ++j)
  30. {
  31. if(arr[j] > arr[j+1])
  32. {
  33. Swap(&arr[j], &arr[j+1]);
  34. }
  35. }
  36. }
  37. }

其中时间复杂度为O(^{n2}),空间复杂度为O(n),稳定性是不稳定

 稳定:如果a原本在b的前面,而a=b, 排序之后a仍然在b的前面。

不稳定:如果a原本在b的前面,a=b, 排序之后a有可能在b的后面。

时间复杂度:对排序数据的总的操作次数。

空间复杂度:指算法在计算机内执行时所需存储空间的度量。

 

二、选择排序

参考本人另一条博客内容,相关链接为https://blog.csdn.net/qq_41026740/article/details/79706790

  1. // O(n^2) O(1) 不稳定
  2. void SelectSort(int *arr, int len)
  3. {
  4. int min = 0;
  5. for (int i = 0; i < len; ++i)
  6. {
  7. min = i;
  8. for (int j = i + 1; j < len; ++j)
  9. {
  10. if (arr[j] < arr[min])
  11. {
  12. min = j;
  13. }
  14. }
  15. if (min != i)
  16. {
  17. Swap(&arr[min], &arr[i]);
  18. }
  19. }
  20. }

三、直接插入排序

思路:以第二个数据开始,

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

闽ICP备14008679号