首页 > 代码库 > 【插入排序】直接插入排序
【插入排序】直接插入排序
思想:顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大。当子集合大小最终和集合大小相同时排序完毕。
算法分析:直接插入排序的时间复杂度为O(n2),空间效率为O(1),是一种稳定的排序方法。
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 void InsertSort(vector<int> &vec) 6 { 7 vector<int>::size_type i, j; 8 int key; 9 if (vec.size() == 0)10 {11 return;12 }13 14 for (i = 1; i < vec.size(); i++)15 {16 j = i - 1;17 key = vec[i];18 while (j >= 0 && j < i && vec[j] > key)19 {20 vec[j + 1] = vec[j];21 j--; //j为unsigned,j--可能为大正数22 }23 vec[j + 1] = key;24 }25 26 return;27 }28 29 int main(void)30 {31 vector<int> vec;32 vector<int>::iterator iter;33 int tmp;34 35 while (cin >> tmp)36 {37 vec.push_back(tmp);38 }39 40 InsertSort(vec);41 42 for (iter = vec.begin(); iter != vec.end(); iter++)43 {44 cout << *iter << " ";45 }46 cout << endl;47 48 return 0;49 }
【插入排序】直接插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。