作者:天涯使者2602921991 | 来源:互联网 | 2023-06-06 16:22
选择排序是不稳定排序,时间复杂度为O(n^2)。选择排序类似插入排序,把数组分为两部分,一部分已经排好序,一部分未排序。刚开始的时候所有的元素都未排序,已排序的部分为空。就好像你手
选择排序是不稳定排序,时间复杂度为O(n^2)。
选择排序类似插入排序,把数组分为两部分,一部分已经排好序,一部分未排序。
刚开始的时候所有的元素都未排序,已排序的部分为空。就好像你手里有十张牌,左手有零张,右手有10张。每次从右手的牌中取最小的一张插入到左手的牌末尾,右手的牌插完了,排序也完成了。
选择排序虽然和冒泡排序同为时间复杂度O(n^2)级别的排序,但是它的移动次数少,最多交换n-1次,所以适合尽可能少移动元素的排序,比方说码头集装箱排序,移动集装箱的成本很高,要尽可能少移动。
选择排序代码如下:
#include
void choseSort(int arr[], int n) {
int i, j;
int min, temp;
// 每次从未排序的部分选出一个最小的元素,最后一次只剩一个元素未排序
// 此时实际上已经排好序,故只需要n-1次外层大循环
for (i = 0; i 1; ++i) {
min = i; // 假定未排序部分的第一个元素为最小的元素
// 遍历剩下的部分,找到最小的元素
for (j = i + 1; j j) {
if (arr[j] < arr[min]) {
min = j;
}
}
// 如果第一个元素就是最小的元素,就不需要交换了
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
int main() {
int i = 0;
int arr[10] = {5, 2, 3, 8, 1, 2, 6, 9, 3, 7};
choseSort(arr, 10);
for (i = 0; i <10; ++i) {
printf("%d ", arr[i]);
}
return 0;
}
选择排序,C语言实现