ソート----ヒルソート

1233 ワード

1、ヒルソート
アルゴリズム思想の簡単な説明:直接挿入ソートアルゴリズムでは、1つの数を挿入するたびに、秩序シーケンスを1つのノードだけ増加させ、次の数を挿入するのに何の役にも立たない.増分と呼ばれる距離が遠い数を比較して、数が移動したときに複数の要素を越えることができるようにすれば、1回の比較で複数の要素交換が解消される可能性があります.D.L.shellは1959年に彼の名前で命名されたソートアルゴリズムでこの考えを実現した.
アルゴリズムは、まず、ソートする一連の数をある増分dでいくつかのグループに分け、各グループに記録された下付きスケールの差d.各グループのすべての要素をソートし、その後、より小さな増分でソートし、各グループでソートする.インクリメントが1に減少すると、ソートする数全体がグループに分けられ、ソートが完了します.次の関数はヒルソートアルゴリズムの実装であり,最初のシーケンスの半分は増分であり,その後は増分が1になるまで毎回半減する.ヒルの順位は不安定だ.
2、ヒルソートコード:
#include "stdafx.h"
#include "iostream.h"

//    
void ShellSort(int *x, int n)
{	
	int h, j, k, t;	
	/*    */
	for (h=n/2; h>0; h=h/2) 		
	{		
		/*      */
		for (j=h; j<n; j++) 			
		{
			t = *(x+j);		
			for (k=j-h; (k>=0 && t<*(x+k)); k-=h)				
			{			
				*(x+k+h) = *(x+k);						
			}
			*(x+k+h) = t;	
		}	
	}	
}

int main()
{
	int a[11]={240,41,1242,1324,29423,3424,445,46,547,59,36};
	ShellSort(a,11);
	for (int i=0;i<11;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
	return 0;
}