十大排序之选择排序(Selection Sort)
汇总在这里 十大排序汇总
选择排序
算法介绍:
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
代码实现:
void selection_sort(int arr[],int len) {//len表示数组长度
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++)//遍历当前索引后面的所有索引
if (arr[j] < arr[min])//找到最小的记录下来
min = j;
swap(arr[i], arr[min]);//替换
}
}
选择排序的优化(说实话没必要,但还是了解一下,总有好处)
选择排序的优化思路一般是在一趟遍历中,同时找出最大值与最小值,放到数组两端,这样就能将遍历的趟数减少一半。第一次选择最大值与最小值
void selection_sort(int arr[],int len) {
int l = 0;//l为数组左端
int r = len - 1;//r为数组右端
while (l < r){
int min = l;//初始化最小值的索引
int max = r;//初始化最大值元素的索引
for (int i = l; i <= r; i++){
/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
if (arr[i] < arr[min])
min = i;
if (arr[i] > arr[max])
max = i;
}
/*最大值放在最右端*/
int temp = arr[max];
arr[max] = arr[r];
arr[r] = temp;
/*此处是先排最大值的位置,所以得考虑最小值(arr[min])在最大位置(r)的情况*/
if (min == r)
min = max;
/*最小值放在最左端*/
temp = arr[min];
arr[min] = arr[l];
arr[l] = temp;
/*每趟遍历,元素总个数减少2,左右端各减少1,left和right索引分别向内移动1*/
l++;
r--;
}
}
稳定性:
在选择排序中,每趟都会选出最大元素与最小元素,然后与两端元素交换,若待排序序列中如果存在与原来两端元素相等的元素,稳定性可能会被破坏。如数组arr[1,2,1,3,5],在arr[0]与arr[3]元素交换时,序列的稳定性就会被破坏,所以选择排序是一种不稳定的排序算法。
时间复杂度:
选择排序的时间复杂度为O(n²)。
空间复杂度:
选择排序的空间复杂度为O(1)。
适用场景:
待排序序列中,元素个数较少时。