#include<iostream>
#include<vector>
#include<time.h>
#include<algorithm>
using namespace std;
void insert_sort(vector<int> &arr){//插入排序
 for (int i = 1; i < arr.size(); ++i){
  int temp = arr[i];
  int pos = i;
  for (int j = i - 1; j >= 0 && temp<arr[j]; --j){
   arr[j + 1] = arr[j];
   pos = j;
  }
  arr[pos] = temp;
 }
}
void shell_sort(vector<int> &arr){//希尔排序
 int increasement = arr.size();
 int i, j, k;
 while (increasement > 1){
  increasement = increasement / 3 + 1;
  for (i = 0; i < increasement; ++i){//一共有increasement组数据排序
   for (j = i + increasement; j < arr.size(); j += increasement){//每组有几个数据
    int temp = arr[j];
    int pos = j;
    for (k = j - increasement; k >= 0 && arr[k]>temp; k -= increasement){
     arr[k + increasement] = arr[k];
     pos = k;
    }
    arr[pos] = temp;
   }
  }
 }
}
int main(){
 srand((unsigned int)time(NULL));
 //定义数组
 vector<int> arr;
 for (int i = 0; i < 10; ++i){
  int num = rand() % 100;
  arr.push_back(num);
 }
 for (auto i : arr)
  cout << i << ' '; cout << endl;
 shell_sort(arr);
 //输出
 for (auto i : arr)
  cout << i << ' ';
 cout << endl;
 system("pause");
 return 0;
}