选择排序

选择排序

选择排序作为基础的排序算法，它的时间复杂度是O（n^2）级别的

特性：

1、在任何时候不管什么有序无序序列，它都要经过两次for循环

2、不会相等的值之间的原有的顺序

3、是原地算法

一、选择排序算法的整型数组的基本实现

#includeusing namespace std;void SelectionSort(int arr[],int n){ for (int i = 0; i < n; i++) { //设置最小值的索引依次为待排序的第一个元素的索引 int minindex = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minindex]) //查找待排序数组的中的最小值，并将最小值的索引交换 minindex = j; //C++11标准库swap交换函数就在std命名空间中，老的标准在#include中 //这一步使得选择排序不是稳定的排序 swap(arr[i], arr[minindex]); }}/* void Chose_sort(vector&nums){ assert(!nums.empty()); for (int i = 0; i < nums.size(); i++) { int min_index = i;//初始最小值的索引 for (int j = i + 1; j < nums.size(); j++) if (nums[j] < nums[min_index]) min_index = j; swap(nums[i], nums[min_index]); }}*/int main(){ int arr[] = { 6, 4, 2, 8, 1, 3, 9, 5, 4, 7 }; SelectionSort(arr, 10); for (int i = 0; i < 10; i++) cout << arr[i];}

二、选择排序的扩展（包括模板，多类型，随机数组）

1、student.h

#pragma once#includeusing namespace std;struct student{ string name; int score; //< 号的重载，排序算法中当比较student时会用到 bool operator<(const student &otherstudent) { return score != otherstudent.score ? score < otherstudent.score: name < otherstudent.name; } //<< 输出号的重载 friend ostream& operator<<(ostream &os, const student &student) { os << "student:" << student.name << "　" << student.score<< endl; return os; }};

2、SortTestHelper.h

#pragma once#include#include#includeusing namespace std;namespace SortTestHelper{ //生成N个元素的随机数组，每个元素元素的随机数返回为[rangeL,rangeR] int* generateRandArray(int n,int rangeL,int rangeR) { assert(rangeL<=rangeR); //定义一个动态数组，分配n个整型空间，arr是指向这个数组的第一元素指针 int *arr = new int[n]; //利用当前的时间作为随机的种子，进行设置 包含#include srand(time(NULL)); for (int i = 0; i < n; i++) arr[i] = rand() % (rangeR - rangeL + 1) + 1; return arr; }}

#include#include#include"student.h"#include"SortTestHelper.h"using namespace std;void SelectionSort(int arr[],int n){ for (int i = 0; i < n; i++) { //设置最小值的索引依次为待排序的第一个元素的索引 int minindex = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minindex]) //查找待排序数组的中的最小值，并将最小值的索引交换 minindex = j; //C++11标准库swap交换函数就在std命名空间中，老的标准在#include中 swap(arr[i], arr[minindex]); }}templatevoid SelectionSort(T arr[], int n){ for (int i = 0; i < n; i++) { //设置最小值的索引依次为待排序的第一个元素的索引 int minindex = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minindex]) //查找待排序数组的中的最小值，并将最小值的索引交换 minindex = j; //C++11标准库swap交换函数就在std命名空间中，老的标准在#include中 swap(arr[i], arr[minindex]); }}int main(){ int n = 100; int *arr = SortTestHelper::generateRandArray(n,0,50); SelectionSort(arr, n); for (int i = 0; i < n; i++) cout << arr[i]<<" "; cout << endl; delete [] arr; float b[] = { 6, 4, 2, 8, 1, 3, 9, 5, 4, 7 }; SelectionSort(b, 10); for (int i = 0; i < 10; i++) cout << b[i]; cout << endl; string c[] = {"g","a","r","b" }; SelectionSort(c, 4); for (int i = 0; i < 4; i++) //加了#include string库中<<的重载函数 cout << c[i]; cout << endl; student d[4] = { {"d",45},{"c",56}, {"b",56}, {"a",98} }; SelectionSort(d, 4); for (int i = 0; i < 4; i++) cout << d[i]; cout << endl; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。