首页 > itarticle > shell

shell

admin 11月 14, 2020 0

Shell Sort

希尔排序是不稳定排序算法,时间复杂度：平均O(NlogN)，最坏情况O（N^1.5）,空间复杂度：O(1),运行时间和输入有关,逆序最慢，有序最快。
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…).
在本代码中选择步长tep = tep/2.

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