首页 > 代码库 > 排序--选择排序
排序--选择排序
Selection Sort 选择排序
基本思想:
在未排序的序列中找到最小元素,放在序列的起始位置,从剩余的未排序的序列中继续寻找最小元素,放在已排序的队列末尾。直到所有的元素都排序完成。
C语言实现:
#include <stdio.h>
#include <stdlib.h>
int lists[5] = { 4,3,1,2,5 };
void selection_sort(int arr[], int len);
int main()
{
printf("\n\n排序之前的样子是这样的:");
for (int i = 0; i < 5; i++)
printf("%d", lists[i]);
selection_sort(lists, 5);
printf("\n\n排序之后的样子是这样的:");
for (int i = 0; i < 5; i++)
printf("%d", lists[i]);
return 0;
}
void selection_sort(int arr[], int len)
{
int i, j, min, temp;
for (i = 0; i < len - 1; i++)
{
min = i; //指定最小点从左边开始
for (j = i + 1; j < len; j++)
{
if (arr[min] > arr[j]) //未排序中存在比最小点小的
min = j; //找到最小值
}
if (min != i) //交换一下最小值和第一个值
{
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
printf("\n\n ---这次:%d找到的最小值是:%d---", i,temp);
}
printf("\n第%d次循环得到的数组的样子是:",i);
for (int i = 0; i < len; i++)
printf("%d", arr[i]);
}
}
算法结果:
排序之前的样子是这样的:43125
---这次:0找到的最小值是:1---
第0次循环得到的数组的样子是:13425
---这次:1找到的最小值是:2---
第1次循环得到的数组的样子是:12435
---这次:2找到的最小值是:3---
第2次循环得到的数组的样子是:12345
第3次循环得到的数组的样子是:12345
排序之后的样子是这样的: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。
参考文献:
- https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
来自为知笔记(Wiz)
排序--选择排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。