首页 > 代码库 > 【插入排序】直接插入排序

【插入排序】直接插入排序

2024-10-23 06:59:39   211人阅读

思想：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大。当子集合大小最终和集合大小相同时排序完毕。

算法分析：直接插入排序的时间复杂度为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 }

【插入排序】直接插入排序


联系
我们