排序算法——插入排序
程序员文章站
2024-02-28 23:54:58
...
插入排序
拥有一个无序的数组,我们只需先拿一个数(一般拿第一个),把它先当作一个有序的数组。然后把这个无序数组中其它数分别插入到已经有序的数组中即可。
代码构造思路:首先得考虑要用什么数据结构,是链表还是顺序表。在下面的代码中,我使用的是顺序表,其实就是普通的数组。然后因为我拿第一个数做为已经有序的数组,剩下只需要把其它在无序数组中的数,插入到有序数组中即可,所以外循环其实只需要循环n-1
次。而每次循环的nums[i]
其实就是代rug表当前要插入的数,然后构造内循环,内循环所循环的其实就是已经有序的数组,从尾到头进行遍历,至于为什么是从尾到头,当然是因为在顺序表中执行插入操作,不管插入到哪里,插入位置后面的数组自然都需要往后移一个位置,而在插入排序中,从尾到头的遍历的时候,在比较的同时,也在移动数组中数的位置。就是需要插入的数需要排在当前遍历到的有序数组的数的前面,自然需要把这个数后移,而因为是从尾到头的遍历,所以每一次的比较的位置不是正确的位置,都会把当前有序数组的数往后一位,直到找到合适的位置,进行插入。而这个合适的位置就是nums[j + 1] = insertNum
。
时间复杂度:
平均情况 | 最好情况 | 最坏情况 |
---|---|---|
空间复杂度:
辅助存储 |
---|
class Solution {
public:
Solution() {}
~Solution() {}
vector<int> sortArray(vector<int>& nums) {
int len = nums.size();
for (int i = 1; i < len; ++i) {
int insertNum = nums[i];
int j;
for (j = i - 1; j >= 0 && insertNum < nums[j]; --j) {
nums[j + 1] = nums[j];
}
nums[j + 1] = insertNum;
}
return nums;
}
};