Javaデータ構造で挿入ソートとヒルソートを実装する方法

1. 本文

1. 並べ替えの概念とその応用

1.1 並べ替えの概念

ソート: いわゆるソートとは、レコードの文字列を、その中の 1 つまたはいくつかのキーワードのサイズに応じて昇順または降順に並べる操作です。

安定性 : 並べ替えるレコード シーケンスに同じキーワードを持つ複数のレコードがあると仮定します。並べ替えても、これらのレコードの相対的な順序は変更されません。つまり、元の順序のままです。シーケンスでは r[i]=r[j] であり、r[i] は r[j] の前にあり、ソートされたシーケンスでは r[i] は依然として r[j] の前にあり、これをソートと呼びます。アルゴリズムが安定している場合、そうでない場合は不安定であると言われます。

内部ソート: すべてのデータ要素がメモリ内に配置されるソート。

外部ソート: 同時にメモリに配置できないデータ要素が多すぎます。ソート プロセスの要件に従って、データを内部と内部の間で移動することはできません。外部メモリ。

1.2 並べ替えの応用

並べ替えの基本的な概念を読んだ後、友人の中には、並べ替えを学んだとしても実生活で役に立つのかと尋ねる人もいるかもしれません。 ?実際、商品のさまざまな側面の選択や大学のランキングなど、

並べ替えは生活のいたるところで行われており、その背後には並べ替えという考え方があります。 上手に分類する方法を学べば、人生のあらゆる側面を別の次元から観察し、人生の問題をより良く解決できるようになることができます。

#1.3 共通の並べ替えアルゴリズム

データ構造には、共通の 4 つのアルゴリズムがあります。ソートアルゴリズム:

①

挿入ソート

: 直接挿入ソート、ヒルソート

②選択ソート: 選択ソート、ヒープソート

③交換ソート: バブルソート、クイックソート

④マージソート: マージソート

2 .挿入ソートの実装アルゴリズム

スペースの都合上、この記事では主に挿入ソートの

直接挿入ソート

と

ヒルソート

を紹介します。挿入ソートと呼ばれます。 2.1 挿入ソート

2.1.1 基本的な考え方

直接挿入ソートは単純な挿入ソート方法です。

その基本アイデアは次のとおりです。

すべてのレコードが挿入され、新しい順序シーケンスが取得されるまで、キー値のサイズに従って、並べ替えるレコードを既にソート済みの順序シーケンスに 1 つずつ挿入します。

実際、ポーカーをプレイするとき、私たちは挿入ソートの考え方を使用します。

新しいカードを引くとき、当然のことながら、それを 1 枚ずつ手札の既存のカードの山と比較し、比較後に配置されるべき場所

に置きます。したがって、私たちは挿入ソートが何であるかを知らないかもしれませんが、私たちの潜在意識のアプローチは挿入ソートとまったく同じです。 2.1.2 直接挿入ソート

直接挿入ソートを説明するには、より記述された言語を使用します。i 番目 (i>=1) 要素を挿入するとき、前 array[0]、array[1]、...、array[i-1]がソートされました このとき、array[i]とarray[i-1]、array[i]のソートコードを使用します-2]、…ソートコードの順序を比較し、挿入位置を見つけて配列[i]を挿入すると、元の位置の要素の順序が戻ります

ただし、一部の友人はそうではないかもしれませんそれは理解できたので、平易な言葉で話しましょう。さて

あなたの目の前には無秩序な配列があります。私たちの目的は、この無秩序な配列を昇順または降順に調整することです。

昇順を例にとると、配列は順序付けされていないため、

配列の 2 番目の要素からソートを開始する必要があります。なぜ最初のものではないのでしょうか? 数値が 1 つしかない場合、他の要素と比較することはできません。当然、無秩序などというものは存在しません。したがって、要素が 1 つしかない場合は、デフォルトで順序付けされます。

2 番目の要素から並べ替えを開始する必要がある理由を理解したら、要素を順番に挿入して並べ替える必要があります。 1 つ目は、2 番目の要素の挿入と並べ替えです。下の図では、2 番目の要素が 44 であることがわかります。44 は最初の要素より 3 大きいため、2 番目の要素を移動する必要はありません。次に 3 番目の要素の挿入と並べ替えです。3 番目の要素 38 が 2 番目の要素 44 より小さいことがわかり、昇順の期待を満たしていません。そのため、44 を 38 の位置に移動し、2 番目の要素 44 を移動します。ソート後、38 は 3 より大きい、つまり 1 番目と 2 番目の要素も順番に並んでいることがわかり、最初の要素の位置を移動する必要はありません。その 38 は array. 要素の 2 番目の要素にあるはずなので、2 番目の要素の位置に 38 を挿入するだけです。これを見た友人は、後続の要素の挿入や並べ替えが簡単にできるはずです。

次のステップは、コードを記述することです。コードの観点から、上記の要素の挿入と並べ替えをどのように実装できるでしょうか? 2 つの主な変数 "des" と "end" を使用しました。des は挿入する要素の最初のインデックスで、end は挿入前のシーケンスを表します。 des の比較を持つ最後の要素、 end は引き続き前進します。そのため、 end の移動がいつ停止するか、つまり 比較の終了は、大きく 2 つの状況 に分けられます。 ①desで表される要素がendで表される要素より大きい ②endが数列の最初の要素に到達した このとき、desは最初の要素か2番目の要素になります。 具体的な図とコードは次のとおりです。

##

//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}

注:

ソート特性の概要

①要素セットの順序が近いほど、直接挿入ソート アルゴリズムの時間効率が高くなります。

②時間計算量: O(N^2 )

③ 空間複雑度: O(1)、安定したソート アルゴリズムです。

④ 安定性: 安定した

2.1.3 ヒル ソート (増分を減らす) )

ヒルソート法は、減少増分法とも呼ばれます。

Hill ソート法の基本的な考え方は次のとおりです。まず整数を選択し、ソートするファイル内のすべてのレコードを整数グループに分割し、すべてのレコードを の距離で配置します。レコードはソートされます。その後、上記のグループ化とソートの作業を繰り返し、整数が 1 に等しい場合、すべてのレコードが同じグループにソートされます。

一般に、

Hill ソートは複数の直接挿入ソート

ですが、最後の直接挿入ソート以外のソートは、本来の直接挿入ソートとは異なります。したがって、これを見た友人は、なぜ複数の挿入ソートが実行されるのかと尋ねるかもしれません。単一の挿入ソートと通常の挿入ソートの違いは何ですか?心配しないでください。以下で 1 つずつ答えていきます。

まず、なぜ複数回挿入ソートが必要なのでしょうか? 挿入ソートの特徴に関する上記の概要を読むと、 要素のコレクションが順序に近づくと、時間効率が向上することがわかります。挿入ソートの値は

の方が高くなります。したがって、ヒル ソートの目的は、最後のソートが通常の挿入ソートであることを除き、要素のセットを

継続的に調整して、常に順序付けに近づくようにすることです 。 次のステップは、ヒル ソートと最後の挿入ソートを除く通常の挿入ソートの違いです。上記の挿入ソートの研究を通じて、不規則な配列の場合、要素が正しい位置に到達したい場合は、他の要素と 1 つずつ比較する必要がある、つまり、段階的に移動する必要があることがわかります。配列内の要素の数が少ない場合はこれで問題ありませんが、配列内の要素の数が昇順で多い場合は、配列内の最大の要素が配列の最初の位置にあると考えてください。この要素は、配列内の他の要素と 1 つずつ比較しなければ配列の最後の位置に到達できませんが、比較のペースを上げる、つまり比較する 2 つの要素間の距離を増やすと、次に、要素はより速く到達できるかどうかを確認します。フライングチェスの状況に置くと、挿入ソートは毎回 1 をスローし、最後の挿入ソートを除いてハッシュ ソートはポイント 1 をスローし、残りの挿入ソートはすべて 1 より大きいため、ハッシュ ソートは次のようになると考えられます。ソートの最後までより早く到達できます。

友人の理解を容易にするために、コードのこの部分は 2 つの部分に分かれています: ① 固定ステップ直接挿入ソート ② ハッシュ ソート。

先是固定步伐的直接插入排序，先让我们通过图片来直观的看到数组数组内的元素通过这种操作后的变化。

//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}

接着就是希尔排序

上述的代码是gap=3的情况下的直接插入排序，那么对于希尔排序而言，我们该对gap该如何选择呢？对于不同gap值的插入排序来说，我们会发现：gap越大，元素跳得越快，数组越不接近有序；而gap越小，元素跳的越慢，数组越接近有序。由于数组的大小不定，因此希尔排序也没有一个合适gap值适用于所有数组，显然，这个gap值一定是动态变化的。

对于gap的动态变化，常见的有两种：

①令gap等于数组的元素个数，每次插入排序后令gap除等2

②另一种则是令gap等于数组的元素个数，不过每次插入排序后令gap除以3再加1

无论哪种处理都能使gap动态变化并最后等于1，对数组进行一次插入排序，达到最后想要的效果。

代码如下：

//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}

二、测试代码

为了方便小伙伴们测试排序后的效果，为大家提供了测试的代码并包含排序的具体代码和包含的头文件。

#include 
#include 
#include 
 
//插入排序[升序]
int* InsertSort(int* arr, int n)
{
 
	//整体排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int des = arr[i];
		//单趟排序
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			arr[end+1] = des;
		}
	}
}
 
//固定步伐的直接插入排序[升序]
void ShellSort(int* arr, int n)
{
	int gap = 3;
	int end;
	//有两种写法，看你要控制end，还是des
	/*for (int i=0; i < n-gap; i++)
	{
		int end = i;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}*/
 
	for (int i = gap; i < n ; i++)
	{
		int end = i-gap;
		int des = arr[end + gap];
		while (end >= 0)
		{
			if (des >= arr[end])
				break;
			if (des < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = des;
		}
	}
}
 
 
//希尔排序
void ShellSortPlus(int* arr, int n)
{
	int gap=n;
	int end;
	while (gap > 1)
	{
	gap = gap / 2;
		
		for (int i=0; i < n - gap;i++)//有两种写法，看你要控制end，还是des
		{
			int end = i;
			int des = arr[end + gap];
			while (end >= 0)
			{
				if (des >= arr[end])
					break;
				if (des < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				arr[end + gap] = des;
			}
		}
 
	}
}
 
//打印排序好的数组
void PrintSort(int*arr,int n)
{
	for(int i=0;i
ログイン後にコピー

以上がJavaデータ構造で挿入ソートとヒルソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。