C/C++排序篇-希尔排序详解

思想

希尔排序又称为“缩小增量排序”，它是对直接插入排序方法的改进。其基本思想是：先将整个待排序记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

简单来说就是不断缩小增量，按每个增量值可从序列中各取出一组。这样就相当于对若干个子序列先排序。我们称在序列当中某些元素间满足(i+nk)<length（i表示当前位置,k表示增量）。则称由这些元素组成的序列为子序列。

增量为当前位置到下一个目标的位置差。

过程

假设当序列为{5,8,3,1,2,9,6,4,7},我们给定一个增量序列为 4,2,1。

希尔排序过程如下：

5       8       3       1       2       9       6       4       7

当以4为增量时，可以发现过程中5与2需要发生交换。第一轮排序序列为 2 8 3 1 5 9 6 4 7

第二轮以2为增量进行排序时，可以发现8与1先发生交换，由于当前增量下的子序列没有其他元素了，所以只需交换8与1。随后9与4发生交换，在当前增量下的子序列存在其他元素，即1与8。已知在当前子序列中当前位置之前的元素一定是排序好了，故我们这里可以对子序列进行直接插入排序，即将当前元素有序的插入到前部分已经排序好的段当中。

第三轮以1为增量排序，相当于对序列进行一次完整的直接插入排序，故最后一定有序。此前的两轮排序已经使序列基本有序，以至于在最后一轮我们可以尽可能少的进行插入，这就是希尔排序对直接插入排序的优化之处，其时间复杂度为O(n^1.3)，小于直接插入排序的O(n^2)。

实现

#include <iostream>
using namespace std;
void Sorted(int *array,int length,int deltas[],int deltaLength);
void Output(int *array,int length);
int main()
{
    int *array=new int[10]{2,4,1,5,6,3,9,2,11,7};
     Sorted(array,10,new int[3]{4,2,1},3);
    Output(array,10);
    system("pause");
    return 0;
}

void Sorted(int *array,int length,int deltaSquence[],int deltaLen)
{
int k=length,i=0,t;
//length:3 k->1 length:5 k->2 k->1
do
{
k/=2;
deltaSquence[i++]=k;
} while (k>1);
i=0;
//分别处理各个序列
for (size_t i = 0; i < deltaLen; i++)
{
k=deltaSquence[i];
//处理具体序列 根据增量 得到序列 每次向后偏移一个单位
for (size_t j = deltaSquence[i]; j < length; j++)
{
if (array[j] < array[j - k])
{
int temp=array[j];
//直接插入排序 在当前增量序列下该位置与之前已经排序好的序列进行直接插入。
for (t = j-k; t >=0&&array[t]>temp;t-=k)
{
array[t+k]=array[t];
}
array[t+k]=temp;
}
}
} 
}
void Output(int *array,int length)
{
for (size_t i = 0; i < length; i++)
{
cout<<array[i]<<ends;
}
}

示例下载

DS15.排序-希尔排序.zip:

来源：诚通网盘 | 提取码：unitymake

立即下载