1.总起

2.排序算法

2.1选择排序

2.1.1算法原理

找到数组中最小的元素，和第一个元素交换，再在剩余的元素中（未排序元素）找到最小的元素，和第二个元素交换，如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它不断地在剩余元素中选择最小者。

2.1.2算法特点

比较次数为 N22 ，这个是很显然的，交换次数为N运行时间和输入无关，也就是说对于一个有序数组和一个元素随机的数组而言，选择排序耗时相同。其他算法更善于利用输入的初始状态。数据移动最少。选择排序交换次数为N次，交换次数和数组大小是线性关系。其他算法并不具备这个特征。

2.1.3代码（cpp）

#include<iostream> #include<vector> using namespace::std; int main(){ vector<int> a{3, 45, 12, 7, 56, 34, 1, 0, 34, 33, 26, 98, 76}; int min = 0;//存储最小下标 int temp = 0; for (int i = 0; i != a.size()-1; i++){ min = i;//min的初始值必然是当前的i for (int j = i+1; j < a.size(); j++){ if (a[min] > a[j]) { min = j;} //最关键的一步 } temp = a[min]; a[min] = a[i]; a[i] = temp; } for (int i = 0; i != a.size(); i++){ cout << a[i] << endl; } return 0; }

2.2插入排序

2.2.1算法原理

插入排序比较类似与我们生活中给一副乱序的扑克牌排序的过程，从第一张牌开始，第一张牌先放着，第二张牌和第一张牌比较，小的放前面，第三张牌在与前面两张比较，插入到合适的位置，特点是前面的牌是排好顺序的，后面拿出的牌根据大小再去排好位置。具体过程是：新拿到的牌先和排序好的最后一张牌比较，若是新牌大，结束，否则就交换，这样依次交换，直到把新牌放入合适位置。

2.2.2算法特点

和选择排序不同，插入排序所需时间取决于输入元素中的初始顺序，有序数组的排序比乱序数组排序要快。时间复杂度为O(N^2)

2.2.3代码实现

#include<iostream> #include<vector> using namespace::std; int main(){ vector<int> a{ 15, 23, 86, 4, 22, 57, 41 }; int temp = 0; //插入排序，总体思想是将i个元素与前面i-1个元素（已排好顺序）比较，插入合适位置，比较类似与对于一副乱序的扑克牌排序 for (int i = 0; i < a.size(); i++){ for (int j = i; j>0; j--){ if (a[j] >= a[j-1]) break; else{ temp = a[j-1]; a[j-1] = a[j]; a[j] = temp; } } } for (int i = 0; i < a.size(); i++){ cout << a[i] << endl; } return 0; }