插入排序

张威小于 1 分钟

//insertSort.h
#ifndef _INSERT_SORT_H_
#define _INSERT_SORT_H_

#include <vector>

using std::vector;
using std::swap;

void insertSort(vector<int> &nums);

#endif //_INSERT_SORT_H_

#include "insertSort.h"

void insertSort(vector<int>& nums) {
    for(int i = 1; i < nums.size(); ++i) {  
		int x = nums[i];  
         int j;  
         for(j = i - 1; j >= 0 && nums[j] > x; --j) {  
             nums[j + 1] = nums[j];  
         }  
         nums[j + 1] = x;  
    }  
}

时间复杂度O(n²)