首页 > 代码库 > 排序--选择排序

排序--选择排序

Selection Sort 选择排序

基本思想:
在未排序的序列中找到最小元素,放在序列的起始位置,从剩余的未排序的序列中继续寻找最小元素,放在已排序的队列末尾。直到所有的元素都排序完成。

C语言实现:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int lists[5] = { 4,3,1,2,5 };
  4. void selection_sort(int arr[], int len);
  5. int main()
  6. {
  7. printf("\n\n排序之前的样子是这样的:");
  8. for (int i = 0; i < 5; i++)
  9. printf("%d", lists[i]);
  10. selection_sort(lists, 5);
  11. printf("\n\n排序之后的样子是这样的:");
  12. for (int i = 0; i < 5; i++)
  13. printf("%d", lists[i]);
  14. return 0;
  15. }
  16. void selection_sort(int arr[], int len)
  17. {
  18. int i, j, min, temp;
  19. for (i = 0; i < len - 1; i++)
  20. {
  21. min = i; //指定最小点从左边开始
  22. for (j = i + 1; j < len; j++)
  23. {
  24. if (arr[min] > arr[j]) //未排序中存在比最小点小的
  25. min = j; //找到最小值
  26. }
  27. if (min != i) //交换一下最小值和第一个值
  28. {
  29. temp = arr[min];
  30. arr[min] = arr[i];
  31. arr[i] = temp;
  32. printf("\n\n ---这次:%d找到的最小值是:%d---", i,temp);
  33. }
  34. printf("\n第%d次循环得到的数组的样子是:",i);
  35. for (int i = 0; i < len; i++)
  36. printf("%d", arr[i]);
  37. }
  38. }
算法结果:
  1. 排序之前的样子是这样的:43125
  2. ---这次:0找到的最小值是:1---
  3. 0次循环得到的数组的样子是:13425
  4. ---这次:1找到的最小值是:2---
  5. 1次循环得到的数组的样子是:12435
  6. ---这次:2找到的最小值是:3---
  7. 2次循环得到的数组的样子是:12345
  8. 3次循环得到的数组的样子是:12345
  9. 排序之后的样子是这样的:12345请按任意键继续. . .
复杂复分析:
   交换操作只发生在需要的情况下,由于i的取值是0-N-1-2,因此,最多可能发生N-1次的 交换操作。
   比较行为存在两次for循环里面,外层0-N-2内层i+1到N-1大约是n(n-1)/2次,也就是1,2,3,...,N-1求和,这个和初始状态无关,是N^2次复杂度。
   赋值操作次数最多发生3*(N-1)次
    总的时间复杂度总是N^2。


参考文献:
  1. https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F



来自为知笔记(Wiz)


排序--选择排序