2021/05/08（第二章：选择排序）

先介绍数组和列表，由于学过，仅看看时间复杂度：

数组的插入和删除都是O(n)是因为考虑到最坏的情况，比如在最开始位置插入一个元素，则后面的元素都得向后移，所以时间复杂度为O(n).如果后面空间不够，还得额外找空间把这个数组复制过去。

选择排序：
一共需要选择n趟，每一趟都进行线性查找，复杂度为O(n)。所以最终复杂度为O(n^2)。但是从严格角度上看，第一趟查找元素为n，第二趟为n-1,最后一趟仅剩一个元素，平均复杂度为O(1/2n).但是大O表示法中一般省略常系数。
选择排序的代码：（时间复杂度O(n^2)体现在两层for循环）

选择排序的执行代码：
#include
using namespace std;
int select_search(int arr[], int len)
{
int min = arr[0];
int min_index = 0;
for(int i=1;i {
if(arr[i] {
min = arr[i];
min_index = i;
}
}
return min_index;
}
int main()
{
int sort[10] = {95,85,65,35,15,25,55,45,115,225};
int length = sizeof(sort)/sizeof(int); //这里采用的是c++最原始的获取数组元素个数的方法
int sorted[10] = {};
for(int i=0;i {
int small_index = select_search(sort,length);
sorted[i] = sort[small_index];
for(int k=small_index;k {
sort[k] = sort[k+1]; //这里是将数组进行挪动以填补删除掉的元素
}
cout< }

return 0 ;
}