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

排序--选择排序

2024-08-20 22:58:42   226人阅读

Selection Sort 选择排序

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

C语言实现：
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. int lists[5] = { 4,3,1,2,5 };
  6. void selection_sort(int arr[], int len);
  8. int main()
  9. {
  10. 	printf("\n\n排序之前的样子是这样的：");
  11. 	for (int i = 0; i < 5; i++)
  12. 		printf("%d", lists[i]);
  13. 	selection_sort(lists, 5);
  14. 	printf("\n\n排序之后的样子是这样的：");
  15. 	for (int i = 0; i < 5; i++)
  16. 		printf("%d", lists[i]);
  17. 	return 0;
  18. }
  20. void selection_sort(int arr[], int len)
  21. {
  22. 	int i, j, min, temp;
  23. 	for (i = 0; i < len - 1; i++)
  24. 	{
  25. 		min = i;					  //指定最小点从左边开始
  26. 		for (j = i + 1; j < len; j++)
  27. 		{
  28. 			if (arr[min] > arr[j])	   //未排序中存在比最小点小的
  29. 				min = j;				//找到最小值
  30. 		}
  31. 		if (min != i)					//交换一下最小值和第一个值
  32. 		{
  33. 			temp = arr[min];
  34. 			arr[min] = arr[i];
  35. 			arr[i] = temp;
  36. 			printf("\n\n   ---这次:%d找到的最小值是:%d---", i,temp);
  37. 		}
  38. 		printf("\n第%d次循环得到的数组的样子是：",i);
  39. 		for (int i = 0; i < len; i++)
  40. 			printf("%d", arr[i]);
  41. 		
  42. 	}
  43. }
算法结果：
  2. 排序之前的样子是这样的：43125
  4.    ---这次:0找到的最小值是:1---
  5. 第0次循环得到的数组的样子是：13425
  7.    ---这次:1找到的最小值是:2---
  8. 第1次循环得到的数组的样子是：12435
  10.    ---这次:2找到的最小值是:3---
  11. 第2次循环得到的数组的样子是：12345
  12. 第3次循环得到的数组的样子是：12345
  14. 排序之后的样子是这样的：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)


排序--选择排序


联系
我们