首页 > itarticle > insert

insert

admin 11月 14, 2020 0

Insert Sort

插入排序是稳定排序,时间复杂度O(n^2),空间复杂度O(1),效率与输入有关,接近有序时效率较高.
这里使用move,假如数组元素是复杂的类型,使用move效率会高.
可以使用折半插入提升效率.

void (int* arr, int n){
  for(int i = 0; i < n - 1; ++ i){
  	int j = i + 1, min_elem = arr[j];
  	for(; j > 0 && min_elem < arr[j - 1]; -- j){
  		arr[j] = move(arr[j - 1]);
  	}
  	arr[j] = move(min_elem);
  }
}