插入排序-希尔排序

直接插入排序

直接插入排序的过程可以理解为一个固定长度的数组被分为两个集合，即已排序集合和未排序。

开始时已排序集合为空，而未排序集合即为整个数组。当排序开始后插入一个对象，已排序集合元素数目加1，相应地未排序集合元素数目减1，重复插入过程直至将未排序集合清空为止，这时排序集合就是最终结果。如下图：

插入排序-希尔排序

希尔排序是一种按照增量排序的方法。其中增量值是小于n的正整数。

shell排序的基本思想[1]是：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

可以根据百度百科中提供的图来直观的看一下：

插入排序-希尔排序

（1）初始增量为3，该数组分为三组分别进行排序。（初始增量值原则上可以任意设置（0<gap<n），没有限制）

（2）将增量改为2，该数组分为2组分别进行排序。

（3）将增量改为1，该数组整体进行排序

#include<iostream>

int a[9] = { 9, 3, 1, 4, 2, 7, 8, 6, 5 };
void InsertSort(int a[], int n);
void Print(int a[],int n);
void shell_sort(int a[], int n);
int main()
{
   int a[9] = { 9, 3, 1, 4, 2, 7, 8, 6, 5 };

   InsertSort(a, 9);
   Print(a,9);
   std::cout << std::endl;
   shell_sort(a, 9);
   Print(a, 9);
   return 0;
}
//插入排序直插
void InsertSort(int a[], int n){
   for (int i = 1; i < n; i++){
       for (int j = i; j>0 && a[j] < a[j - 1]; j--){
           int temp;
           temp = a[j];
           a[j] = a[j - 1];
           a[j - 1] = temp;
       }
   }
}
void Print(int a[],int n){
   for (int i = 0; i < n; i++){
       std::cout << a[i] << " ";
   }
   //std::cout << "sdjkf:" << sizeof(a);

}

//shell 插入排序
void shell_sort(int a[], int n){
   for (int gap = 3; gap>0; gap--){
       for (int i = 0; i < gap; i++){
           //插入排序
           for (int j = i + gap; j < n; j = j + gap){
               for (int k = j; a[k]<a[k - gap] && k>0; k = k - gap){
                   int temp;
                   temp = a[k];
                   a[k] = a[k - gap];
                   a[k - gap] = temp;
               }
           }
       }
   }
}

插入排序-希尔排序

相关推荐