3.希尔排序

 1 #include "pch.h"
 2 #include <iostream>
 3 void shellSort(int *a, int n)
 4 {
 5     int d;
 6     int j;
 7     int i;
 8     int k;
 9     int temp;
10     for (d = n / 2; d >= 1; d = d / 2) {     //每次要分多少个子序列，以及总共进行了多少次划分，在每一次划分下
11         for (j = 0; j < d; j++) {  //每一次划分，都又d个子序列，而且恰好，for的每次操作对应一个序列的首元素
12             for (i = j + d; i < n; i = i + d) {   //每一个首元素为初始已排序序列，从第二个元素出发
13                 temp = a[i];
14                 k = i - d;
15                 while (k >= 0 && a[k] > temp)
16                 {
17                     a[k + d] = a[k];
18                     k = k - d;
19                 }
20                 a[k + d] = temp;
21             }
22         }
23     }
24     /*for (int j = 1; j < n; j++)
25     {
26         int key = a[j];              //从第二个元素开始，左边为已排序序列
27         int i = j - 1;               //记录已排序序列最后一个元素的下标
28         while (i >= 0 && a[i] > key) //从后往前，使下一个选择的元素与每一个已排序元素比较
29         {                            //只要比选择的元素大就后移，直到首次小于它的元素，插入该位置
30             a[i + 1] = a[i];
31             i--;
32         }
33         a[i + 1] = key;
34     }*/
35 }
36 int main() {
37     int a[8] = { 4,2,3,7,6,9,8,5 };
38     shellSort(a, 8);
39     for (int k = 0; k < 8; k++) {
40         std::cout << a[k] << " ";
41     }
42 }