排序算法之插入排序、希尔（shell）排序及其时间复杂度和空间复杂度

浏览数：24 / 时间：2015年06月08日

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

希尔排序是一种插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。

算法分析

插入排序的思想：

从第二个元素开始往后，依次选择哨兵元素和前面的元素比较，如果前一个元素大于该哨兵元素（从小到大排序），则把前面那个元素移动到后一个位置；继续往前比较，直到找某个元素不大于该哨兵元素，则把哨兵元素插入到位置上；

插入排序的步骤：

1、第二个元素开始外后选择一个哨兵元素；

2、让哨兵元素和前面的元素进行比较，找到合适的位置插入；

3、循环上面两步，直到选择完所有元素；

shell排序的思想：

shell排序是相当于把一个数组中的所有元素分成几部分来排序；先把几个小部分的元素排序好，让元素大概有个顺序，最后再全面使用插入排序。一般最后一次排序都是和上面的插入排序一样的；

shell排序的步骤：

比如：

数组有10个元素，增量 d = 5；则比较元素为：array[0] array[0+d] array[0+2d] array[0+3d]；（当然 d 会改变的，d = d/2 或者 d = d -2）

第一次 d = 5 比较的元素为：array[0] , array[5]

第二次 d = d/2 = 2 比较元素为：array[0] , array[2] , array[4] , array[6] , array[8]

第三次 d = d/2 = 1 比较元素为：从array[0] 到 array[9]

其实上面的插入排序可以看作是增量 d = 1的shell排序；当然同理，shell排序最后增量 d = 1时，就是插入排序了；

代码实现

#include<stdio.h>
 #include<stdlib.h>
 
 void print_array(int *array, int length)
 {
     int index = 0;
     printf("array:\n");
     for(; index < length; index++){
         printf(" %d,", *(array+index));
     }   
     printf("\n\n");
 }
 
 void insertSort(int *array, int length)
 {
     int index_i, index_j, tmp;
     
     for (index_i = 1; index_i < length; index_i++){ // 从第二个元素往后得到哨兵元素
         tmp = array[index_i];
         for (index_j = index_i - 1; index_j >= 0 ; index_j--){ // 和前面有序的元素进行比较 调整
             if (array[index_j] > tmp) array[index_j + 1] = array[index_j];
             else break;
         }   
         array[index_j + 1] = tmp;// 找到合适的位置插入
     }   
 }
 
 void shellSort(int *array, int length)
 {
     int d = 5;
     int i , j, tmp;
     while(d){ // 判断增量
         for ( i = d; i < length; i = i + d){ // 从第一个增量值往后  得到哨兵元素 
             tmp = array[i];
             for (j = i -d ; j >= 0; j = j - d){ // 和前面有序的元素进行调整
                 if (array[j] > tmp) array[j+d] = array[j];
                 else break;
             }
             array[j+d] = tmp;
         }
         d = d/2; // 缩小增量的值
     }
 }
 
 int main(void)
 {
     //int array[] = {12, 1, 32, 201, 9987, 5, 10, 10090, 123, 453};
     int array[] = {2, 1, 3, 201, 987, 5, 10, 90, 13, 45};
     int length = (sizeof(array)) / (sizeof(array[1]));
     
     print_array(array, length);
     insertSort(array, length);
     print_array(array, length);
     
     printf("\n\n======================\n\n");
     shellSort(array, length);
     print_array(array, length);
 
     return 0;
 }

运行结果

技术分享