希爾演算法簡介
① 希爾排序
希爾排序是希爾（Donald Shell）於1959年提出的一種排序演算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序，同時該演算法是沖破O(n^2）的第一批演算法之一。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
第一輪排序：設置step步長為4，根據步長將數組分為四組，{1,3}， {4,2}，{6,5}，{0,9} 進行兩兩比較。
將i=step，開始往後遍歷。如果a[i]>a[i-step]交換數據。得到第一輪排序結果：1 2 5 0 3 4 6 9
第二輪排序：設置step步長為2，根據步長繼續兩兩分組，比較數據大小。得到第二輪排序結果：1 0 3 2 5 4 6 9
第三輪排序：設置step步長為1，根據步長繼續兩兩分組，比較數據大小。得到第三輪排序結果：0 1 2 3 4 5 6 9
輸出結果：
Shell sort:
0, 1, 2, 3, 4, 5, 6, 9,
希爾排序的關鍵並不是隨便分組後各自排序，而是將相隔某個step 的記錄組成一個子序列， 實現跳躍式的移動，使得排序的效率提高。
希爾排序的時間復雜度是O（nlogn），效率上比冒泡排序，直接插入排序，簡單選擇排序的O（n^2）要高。
② 希爾密碼原理
希爾密碼（Hill Cipher）是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果MOD26。
中文名
希爾密碼
外文名
Hill Cipher
原理
基本矩陣論
類別
替換密碼
提出者
Lester S. Hill
快速
導航
產生原因
原理
安全性分析
例子
簡介
希爾密碼是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。
每個字母當作26進制數字：A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再將得出的結果模26。
注意用作加密的矩陣（即密匙）在必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26互質，才是可逆的。
產生原因
隨著科技的日新月異和人們對信用卡、計算機的依賴性的加強，密碼學顯得愈來愈重要。密碼學是一門關於加密和解密、密文和明文的學科。若將原本的符號代換成另一種符號，即可稱之為廣義的密碼。狹義的密碼主要是為了保密，是一種防止竊文者得知內容而設的另一種符號文字，也是一般人所熟知的密碼。
使用信用卡、網路賬號及密碼、電子信箱、電子簽名等都需要密碼。為了方便記憶，許多人用生日、電話號碼、門牌號碼記做密碼，但是這樣安全性較差。
為了使密碼更加復雜，更難解密，產生了許多不同形式的密碼。密碼的函數特性是明文對密碼為一對一或一對多的關系，即明文是密碼的函數。傳統密碼中有一種叫移位法，移位法基本型態是加法加密系統C=P+s(mod m)。一般來說，我們以1表示A，2表示B，……，25表示Y，26表示Z，以此類推。由於s=0時相當於未加密，而0≤s≤m-1（s≥m都可用0≤s≤m-1取代），因此，整個系統只有m-1種變化。換言之，只要試過m-1次，機密的信息就會泄漏出去。
由此看來，日常生活中的密碼和傳統的密碼的可靠性較差，我們有必要尋求一種容易將字母的自然頻度隱蔽或均勻化，從而有利於統計分析的安全可靠的加密方法。希爾密碼能基本滿足這一要求。
原理
希爾加密演算法的基本思想是，將d個明文字母通過線性變換將它們轉換為d個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。[1]
希爾密碼是多字母代換密碼的一種。多字母代換密碼可以利用矩陣變換方便地描述，有時又稱為矩陣變換密碼。令明文字母表為Z，若採用L個字母為單位進行代換，則多碼代換是映射f：Z→Z。若映射是線性的，則f是線性變換，可以用Z上的L×L矩陣K表示。若是滿秩的，則變換為一一映射，且存在有逆變換K。將L個字母的數字表示為Z上的L維矢量m，相應的密文矢量c，且mK=c，以K作為解密矩陣，可由c恢復出相應的明文c·K=m。
在軍事通訊中，常將字元（信息）與數字對應（為方便起見，我們將字元和數字按原有的順序對應，事實上這種對應規則是極易被破解的）：
abcde…x y z
12345…242526
如信息「NOSLEEPPING」對應著一組編碼14,15,19,12,5,5,16,16,9,14,7。但如果按這種方式直接傳輸出去，則很容易被敵方破譯。於是必須採取加密措施，即用一個約定的加密矩陣K乘以原信號B，傳輸信號為C=KB（加密），收到信號的一方再將信號還原（破譯）為B=KC。
③ 希爾排序法特點
希爾排序的實質就是分組插入排序，該方法又稱縮小增量排序，因希爾於1959年提出而得名。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列，由相隔某個「增量」的元素組成的，分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序，增量足夠小時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下，接近最好情況，效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。希爾排序法屬於插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。希爾排序的特點
希爾排序演算法與步長有直接關系。步長依次遞減，數組的局部越來越有序了。希爾排序演算法思想
因為希爾排序是通過比較相距一定間隔的元素來工作的。所以先要自定義步長的范圍。然後選擇一個當前元素，依次按照步長來尋找指定步長的元素進行比較，比較選擇出最小的元素，如果比當前元素小於指定步長的元素，就進行交換，相反就退出當前的循環查找比較。
④ 希爾排序法原理
希爾排序法(縮小增量法) 屬於插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。
演算法思想簡單描述
在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，
並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為
增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除
多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現
了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中
記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量
對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成
一組，排序完成。
下面的函數是一個希爾排序演算法的一個實現，初次取序列的一半為增量，
以後每次減半，直到增量為1。
希爾排序是不穩定的。
⑤ 希爾排序演算法
修改如下:
添加了shellsort()函數.
對main()函數,paixu()函數,rangerand()函數作了修改
修改後的程序如下:
//---------------------------------------------------------------------------
#include<stdio.h> //printf,scanf
#include<stdlib.h> //system,srand,rand
#include<time.h>
void main(){
//================================子函數聲明及說明=================================//
void head(); //操作提示
void print(long R[],long n);//輸出數組中的元素
void insertsort(long R[],long n,long *bj1,long *yd1); //直接插入排序函數
void shellsort(long a[],long n,long *bj5,long *yd5); //Shell排序函數
void Bubblesort(long R[],long n,long *bj2,long *yd2); //冒泡排序函數
void quicksort(long R[], long low, long high,long *bj3,long *yd3); //快速排序函數
void selectsort(long R[],long n,long *bj4,long *yd4); //簡單選擇排序函數
void paixu(long R1[],long R2[],long R3[],long R4[],long N); //進行排序並計時
void rangerand(long *n); //產生隨機數，並排序
int ensure(); //退出確認函數
void knowledge(); //演算法相關知識
void help(); //程序使用說明
//==================================聲明結束======================================//
head();
long N;
char xz;
int flag=1,c;
while(flag)
{
scanf("%c%*c",&xz);
switch(xz)
{
case '0':
system("cls");
head();
break;
case '1':
rangerand(&N);
head();
break;
case '2':
knowledge();
head();
break;
case '3':
help();
head();
break;
case '4':
c=ensure();
if(c) head();
else flag=c;
break;
default:
printf("\n !提示：請輸入一位0~4的數字！\n 請重新輸入選擇的操作：");
break;
}
}//while循環結束
}
void head(){
//軟體使用交互部分
printf(" \n =========================================================\n");
printf(" 排序演算法的比較\n ——直接插入、冒泡、快速、簡單選擇排序\n");
printf(" =========================================================\n");
printf(" 可執行的操作：\n");
printf(" 0．清屏 \n");
printf(" 1．生成隨機數並排序 \n");
printf(" 2．相關演算法知識 \n");
printf(" 3．使用說明 \n");
printf(" 4．退出\n");
printf(" 請選擇(0~4):");
}
void print(long R[],long n){
//輸出數組中的元素
for(long i=0;i<n;i++)
{
printf("%7ld",R[i]);
if(i%10==9) printf("\n");
}
printf("\n");
}
//===============四個排序演算法核心，排序並記錄比較次數============================//
void insertsort(long R[],long n,long *bj1,long *yd1){
//以下為直接插入排序.待排序元素用一個數組R表示,數組有n個元素
for(long i=1;i<n;i++) //i表示插入次數,共進行n-1次插入
{
int temp=R[i]; //把待排序元素賦給temp
long j=i-1;
while((j>=0)&&(temp<R[j]))
{
(*bj1)++;
(*yd1)++;
R[j+1]=R[j];
j--; //順序比較和移動
}
R[j+1]=temp;
(*bj1)++;
}
}
void Bubblesort(long R[],long n,long *bj2,long *yd2){
//以下為冒泡排序
int flag=1; //當flag為0,則停止排序
for(long i=1;i<n;i++) //i表示趟數,最多n-1趟
{
flag=0; //開始時元素未交換
for(long j=n-1;j>=i;j--)
{
if(R[j]<R[j-1]) //發生逆序
{
int t=R[j];
R[j]=R[j-1];
R[j-1]=t;flag=1; //交換,並標記發生了交換
(*yd2)++;
}
(*bj2)++;
}
if(flag==0) break;
}
}
void quicksort(long R[], long low, long high,long *bj3,long *yd3) {
//以下為快速排序
long i, j, pivot;
if (low < high)
{
pivot=R[low];
i=low;
j=high;
while(i<j)
{
while (i<j && R[j]>=pivot)
{
j--;
(*bj3)++;
}
if(i<j)
{
R[i++]=R[j];
(*yd3)++;
} //將比樞軸記錄小的記錄移到低端
while (i<j && R[i]<=pivot)
{
i++;
(*bj3)++;
}
if(i<j)
{
R[j--]=R[i]; //將比樞軸記錄大的記錄移到高端
(*yd3)++;
}
}
R[i]=pivot; //樞軸記錄移到最終位置
quicksort(R,low,i-1,bj3,yd3);
quicksort(R,i+1,high,bj3,yd3);
}
}
void selectsort(long R[],long n,long *bj4,long *yd4){
//以下為簡單選擇排序
long i,j,m;int t;
for(i=0;i<n-1;i++)
{
m=i;
for(j=i+1;j<n;j++)
{
if(R[j]<R[m]) m=j; //用m定位最小值
(*bj4)++;
}
if(m!=i) //逆序，移動
{
t=R[i];
R[i]=R[m];
R[m]=t;
(*yd4)++;
}
}
}
void shellsort(long a[],long n,long *bj5,long *yd5)
{
long i, j, gap, temp;
while (gap * 3 + 1<=n)
{
gap=gap * 3 + 1;
}
while (gap > 0)
{
for ( i = gap; i < n; i++ )
{
j = i - gap;
temp = a[i];
while (( j >= 0 ) && ( a[j] > temp ))
{
a[j + gap] = a[j];
j = j - gap;
(*bj5)++;
(*yd5)++;
}
a[j + gap] = temp;
(*yd5)++;
}
gap = ( gap - 1 ) /3;
}
}
//==================================================================//
void paixu(long R1[],long R2[],long R3[],long R4[],long R5[],long N){
//排序並計時
char tj;
clock_t start, finish;
long t1,t2,t3,t4,t5;
long bj1=0,bj2=0,bj3=0,bj4=0,bj5=0;
long yd1=0,yd2=0,yd3=0,yd4=0,yd5=0;
start = clock(); //記錄初始時間
insertsort(R1,N,&bj1,&yd1); //執行演算法
finish = clock(); //記錄終止時間
t1 = (finish - start) ; //計算演算法執行時間
printf("排序結果：\n");
printf(" 直接插入排序：\n");
print(R1,N);
system("pause"); //屏幕顯示"請按任意鍵繼續…"
start = clock();
shellsort(R5,N,&bj5,&yd5);
finish = clock();
t5 = (finish - start) ;
printf(" Shell排序：\n");
print(R5,N);
system("pause"); //屏幕顯示"請按任意鍵繼續…"
start = clock();
Bubblesort(R2,N,&bj2,&yd2);
finish = clock();
t2 = (finish - start) ;
printf(" 冒泡排序：\n");
print(R2,N);
system("pause");
start = clock();
quicksort(R3,0,N-1,&bj3,&yd3);
finish = clock();
t3 = (finish - start) ;
printf(" 快速排序：\n");
print(R3,N);
system("pause");
start = clock();
selectsort(R4,N,&bj4,&yd4);
finish = clock();
t4 = (finish - start) ;
printf(" 簡單選擇排序：\n");
print(R4,N);
printf(" 按回車鍵查看統計信息...\n");
scanf("%*c",&tj);
printf(" 統計：此次共對%ld個隨機數進行了排序\n",N);
printf(" 排序用時 比較次數 移動次數 \n");
printf( " 直接插入 排序 |%5d 毫秒|%10ld次|%10ld次|\n", t1,bj1,yd1);
printf( " Shell 排序 |%5d 毫秒|%10ld次|%10ld次|\n", t5,bj5,yd5);
printf( " 冒 泡 排序 |%5d 毫秒|%10ld次|%10ld次|\n", t2,bj2,yd2);
printf( " 快 速 排序 |%5d 毫秒|%10ld次|%10ld次|\n", t3,bj3,yd3);
printf( " 簡單選擇 排序 |%5d 毫秒|%10ld次|%10ld次|\n\n", t4,bj4,yd4);
system("pause");
}
void rangerand(long *n){
//對隨機數進行排序
long m;int pd=1;char px;
long Origine[32767],R1[32767],R2[32767],R3[32767],R4[32767],R5[32768];
printf(" 請輸入產生隨機數的個數(1~32767): ");
while(pd)
{
scanf("%ld%*c",n);
printf("\n");
if((*n)>0&&(*n)<32768) pd=0;
else printf("提示：請輸入1~32767之間的數字！\n請重新輸入產生隨機數的個數(1~32767)： ");
}
srand((unsigned)time(NULL));
for(m=0;m<*n;m++)
{
Origine[m]=rand();//產生隨機數
R1[m]=Origine[m];
R2[m]=Origine[m];
R3[m]=Origine[m];
R4[m]=Origine[m];
R5[m]=Origine[m];
}
printf(" 產生的隨機數為：\n");
print(Origine,*n); //輸出隨機數
printf(" 按回車鍵開始排序...");
scanf("%*c",&px);
paixu(R1,R2,R3,R4,R5,*n);
}
int ensure(){
//確認退出
char qr;
printf(" 確定要退出本程序？(y/n)");
scanf("%c%*c",&qr);
if(qr=='y') return 0;
else return 1;
}
void knowledge(){
//演算法的簡要說明
printf("\n 直接插入、冒泡、快速、簡單選擇排序相關知識：\n");
printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf(" 直接插入、冒泡、簡單選擇排序的平均時間、最壞情況均為O(n^2),\n\
快速排序的平均時間為O(nlogn),最壞時間為O(n^2)；\n\
一般待排序數較少時用前三種排序，而隨機數較多時，快速排序的優勢明顯；\n\
這四種排序中只有快速排序是不穩定的。\n\n\n");
system("pause");
}
void help(){
//使用說明
printf("\n 程序說明：\n\
~~~~~~~~~\n\
設計目的：通過對相關參數的比較加深對排序演算法的理解；\n\
輸入：操作號；待排序隨機數的個數；確認操作等\n\
輸出：各演算法的排序時間、比較次數、移動次數。\n\n\n");
system("pause");
}
//---------------------------------------------------------------------------