选择排序C++实现
程序员文章站
2024-03-16 16:48:58
...
选择排序的思想:
假设要从小到大排序n个数,第一步首先在这n个数中找到最大的那一个数,然后将其和arr[n-1]也就是数组最后一个元素交换,接下来再在0~n-2之间找剩下的元素中最大的,再将其和n-2也就是倒数第一个位置的元素交换,以此类推。
选择排序的时间复杂度最好的情况是O(n^2) ,平均时间也是 O(n^2),最坏时间也是O(n^2),它是一个不稳定的排序算法。
可以看做是冒泡排序的plus版本,冒泡排序的交换是在内循环做,每一次比较如果条件成立都得交换一次,而选择排序的交换是在外循环做的,一次遍历只交换一次,在原数组不出现非常极端的情况:已经完全有序 的情况下,选择排序理论上肯定是比冒泡排序效率高的。
代码:
#include <iostream>
#include <stdlib.h>
using namespace std;
void selectionSort(int arr[], int len){
int cFound = 0;
for (int i = len -1; i >= 0; --i){
int maxIndex = i;
int maxVal = -1;
for (int j = i; j >= 0; --j){
if (maxVal < arr[j]){
maxIndex = j;
maxVal = arr[j];
}
}
int tmp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = tmp;
}
}
int main(){
int arr[] = { 4, 2, 1, 3, 9, 7, 8, 0, 6, 5 };
int len = 10;
selectionSort(arr,len);
for (int i = 0; i < len; ++i){
cout << arr[i] << endl;
}
system("pause");
return 0;
}
上一篇: Hello Box2D
下一篇: 碰撞检测怎么用不了?