排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
先上图：
我先从上往下挨个介绍：
1->插入排序：
问题：给定一个整数序列，按照从小到大的顺序（确切地说，是非递减的顺序）排列序列中的整数。输入：一个整数序列。输出：整数序列，其中的整数升序排列。
插入排序时间复杂度最优为 O(n) 情况是数组为已经排好的顺序；最差为O(n^2) 情况为数组为排好的逆序；平均时间复杂度为O(n^2)。空间复杂度为O(1)。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
插入排序是稳定的排序算法。
代码：
#include <iostream> #include <vector> using namespace std; template<class T> //模板 void insertSort(vector<T>&arr) { for(unsigned int i=1;i<arr.size();i++) { T temp=arr[i]; int j=i; for(;j>0&&temp<arr[j-1];j--) { arr[j]=arr[j-1]; } arr[j]=temp; } } int main() { int a[10]={6,2,1,9,3,4,0,2,7,8}; vector<int>arr(a,a+10); insertSort<int>(arr); for(int i=0;i<10;i++) { cout<<arr[i]<<endl; } return 0; }
下一篇博客会介绍希尔排序算法
