本文主要是介绍插入排序(直接插入+希尔排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
直接插入排序是将元素按顺序插入已经排好序的序列中。对于待插入的元素，如果比最后一个元素还大，则不用处理。否则，从后边元素开始比较，并顺次后移，直到碰到元素小于或者等于该元素。
设置第一个元素位置为哨兵，用来存放待插入元素。
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
#define maxn 20typedef struct SqList
{int r[maxn];int Length;
} SqList;void InitSqList(SqList &L,int n)
{int num;for(int i=0; i<maxn; i++)L.r[i] = 0;for(int i=1; i<=n; i++){cin>>num;L.r[i] = num;}L.Length = n;
}void InsertSort(SqList &L)
{int i,j;for( i=2; i<=L.Length; i++)if(L.r[i]<L.r[i-1]){L.r[0] = L.r[i];L.r[i] = L.r[i-1];for( j=i-2; L.r[j]>L.r[0]; j--)L.r[j+1] = L.r[j];L.r[j+1] = L.r[0];}
}void PrintSqList(SqList L)
{for(int i=1; i<=L.Length; i++)cout<<L.r[i]<<" ";
}int main()
{SqList L;int n;cin>>n;InitSqList(L,n);InsertSort(L);PrintSqList(L);return 0;
}
可以发现，当序列基本有序时，直接插入排序要处理的元素就大大减少，效率就会很高。希尔排序就利用了这一特点。
希尔排序的思想是将待排序列分割为小的子序列，分别进行直接插入排序，当整个序列基本有序时，对整体进行一次直接插入排序。当然，子序列是通过增量划分出来的，相隔某个增量的元素属于一个子序列。排序时，增量逐渐减小。
//dk为增量
void ShellInsert(SqList &L,int dk)
{int i,j;for( i=dk+1; i<=L.Length; i++)if(L.r[i]<L.r[i-dk]){L.r[0] = L.r[i];for( j=i-dk; j>0&&L.r[j]>L.r[0]; j-=dk)L.r[j+dk] = L.r[j];L.r[j+dk] = L.r[0];}
}//d[]为增量序列
void ShellSort(SqList &L,int d[],int t)
{for(int k=0; k<t; k++)ShellInsert(L,d[k]);
}int main()
{int d[10] = {10,9,8,7,6,5,4,3,2,1};SqList L;int n;cin>>n;InitSqList(L,n);ShellSort(L,d,10);PrintSqList(L);return 0;
}
这篇关于插入排序(直接插入+希尔排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
