Javaでクイックソートを実装する方法

次のコラム Java 入門学習 では、Java でクイック ソートを実装する方法を紹介します。このアルゴリズムのソートが皆さんのお役に立てれば幸いです。

クイック ソートの時間計算量は固定されていません。最悪の場合 (元々逆ソートされた配列の基本要素として最初の要素を選択する場合)、速度は比較的遅く、O(n^2 に達します) ) (選択ソートと同様の効率) ただし、理想的な状況下で時間計算量が O(nlogn) の場合。

クイック ソートを実装するための鍵は、まず配列内の数値を選択し、次に配列内の数値を 2 つの部分に分割することです。選択した数値より小さい数値は、選択された数値の左側に移動されます。選択した数値より小さい数値は配列の左側に移動し、大きい数値は配列の右側に移動します。 これは分割統治の考え方を反映しています。

この関数を実装しましょう:

int Partition(int data[],int length,int start,int end)
{
	if(data == nullptr || length <= 0 || start < 0 || end >=length)
		throw new std::exception("Invalid Parameters");
	int index = RandomInRange(start,end);
	Swap(&data[index],&data[end]);
	int small = start - 1;
	for(index = start; index < end; index++)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				Swap(&data[index],&data[small]);
		}
	}
	++small;
	Swap(&data[small],&data[end]);
	return small;
}
int RandomInRange(int min, int max)
{
	int random = rand()%(max - min +1) +min;
	return random;
}
int Swap(int *num1, int *num2)
{
	int temp = *num1;
	*num1 = num2;
	*num2 = temp;
}

上記のコードの関数 RandomInRange は開始と終了の間の乱数を生成するために使用され、関数 Swap は次の目的で使用されます。 2 つの番号を交換します。

以下では、再帰を使用してクイックソートコードを実装します:

void QuickSort(int data[], int length, int start, int end)
{
	if(start == end)
		return;
	int index = Partition(data, length, start, end);
	if(index > start)
		QuickSort(data, length, start, index -1);
	if(index < end)
		QuickSort(data, length, index + 1, end);
}

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