C++希尔排序

绝地灬酷狼 2022-06-15 09:00 147阅读 0赞

三大基本排序：冒泡排序、简单选择排序和直接插入排序的时间复杂度都是O(n\*n)，希尔排序是突破这个时间复杂度的第一批算法之一。

当记录本本身是基本有序或记录比较少时，直接插入排序的优势较为明显。但是这两个条件本身就过于苛刻，现实中记录少，或者基本有序都属于特殊情况。

如何让排序的记录个数较少呢？很容易想到的就是将原本有大量数的记录进行**分组**。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都**基本有序**时，主义只是基本有序时，再对全体记录进行一次直接插入排序。

所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。

实现方法：主要采用跳跃分割的策略，将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

\#include <iostream>

using namespace std;  
\#define MaxSize 10  
typedef struct   
\{  
int r\[MaxSize+1\];  
int length;  
\}SqList;  
  
void ShellSort(SqList \*L)   //直接插入排序,此时传入的SqList参数的值为lengt=6，r\[6\]=\{0,5,3,4,6,2\},  
                                       //其中r\[0\]=0将用于后面起到哨兵的作用。  
\{    
   int len=L->length;  
   int i,j;  
   int increment=L->length;  
   do  
     \{     
int i,j;  
increment=increment/3+1;  
for(i=increment+1;i<=L->length;i++)  
  \{  
  if(L->r\[i\]<L->r\[i-increment\])  
   \{  
L->r\[0\]=L->r\[i\];  
for(j=i-increment;j>0&&L->r\[j\]>L->r\[0\];j=j-increment)  
 \{  
 L->r\[j+increment\]=L->r\[j\];  
 \}  
L->r\[j+increment\]=L->r\[0\];  
   \}  
  \}  
\}while(increment>1);  
\}  
  
void main()  
\{  
   SqList L;  
   SqList \*p=&L;  //定义P为指向SqList数据类型的指针变量，并指向L  
   cin>>L.length;  
   for(int i=1;i<=L.length;i++)  
    \{  
  cin>>L.r\[i\];  
    \}   
   ShellSort(p); //或BubbleSort(&L)  
   for(int j=1;j<=L.length;j++)  
    \{  
cout<<L.r\[j\]<<" ";  
    \}