欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

选择排序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;
}