ステップ書きアルゴリズム(再帰的でないソート)

原文:
ステップ書きアルゴリズム(再帰的でないソート)
【声明:著作権所有、転載歓迎、商業用途に使用しないでください.連絡ポスト:[email protected]】
  
上記のブログでは、通常の検索とソート検索のパフォーマンスの違いが大きいことがわかりました.100万のデータとして、普通の検索方法を使えば、1つのデータを平均すると数十万回かかるので、二分法の検索は、20回以上でできます.この中間の差は非常に明らかだ.ソートがこんなに効果的である以上、このブログでは、ソート計算をまとめてみましょう.
私の個人的な理解によると、ソートは2つに分けることができます:1つは非再帰ソートで、それは主に非再帰的な方法でデータをソートして、つまり主要なデータのシフトと循環によって完成します;もう1つは、現在のデータを並べ替えるときに、まずサブデータを並べてから、現在のデータを並べ替える再帰的な方法です.このような繰り返し呼び出しの方法は、再帰ソートである.
非再帰的なソートの方法は多く、ここでは主にバブルソート、挿入ソート、ヒルソートを紹介する.再帰的な方法も少なくありません.ここで紹介する方法は、高速ソート、集計ソート、スタックソートです.ソートの内容は多く、このブログでは主に非再帰ソートを紹介し、再帰ソートの内容は主に次の節で解決します.
(1)発泡ソート
バブルソートの内容は複雑ではありません.n個のデータがソートされる必要があると仮定すると、n個の大きいデータから小さいデータを決定し、毎回n番目のデータがどれだけ大きいかを選択し、対応する位置を拡大する必要がある.すべてのデータが整列するまで、私たちのソートは終わります.

void bubble_sort(int array[], int length)

{

	int inner = 0, outer = 0;

	int median = 0;



	if(NULL == array || 0 == length)

		return;



	for(outer = length-1; outer >= 1; outer --){

		for(inner = 0; inner < outer; inner ++){

			if(array[inner] > array[inner + 1]){

				median = array[inner];

				array[inner] = array[inner + 1];

				array[inner + 1] = median;

			}

		}

	}

}

では、このプログラムには何か改善点がありますか?もちろん、1回の遍歴サイクルの中でシフトが発生していないことが発見されたら、このソートが終了したと判断できるのではないでしょうか.友達はこの問題をよく考えてもいいですか?

void bubble_sort(int array[], int length)

{

	int inner = 0, outer = 0;

	int median = 0;

	int flag = 1;



	if(NULL == array || 0 == length)

		return;



	for(outer = length-1; outer >= 1 && flag; outer --){

		flag = 0;



		for(inner = 0; inner < outer; inner ++){

			if(array[inner] > array[inner + 1]){

				median = array[inner];

				array[inner] = array[inner + 1];

				array[inner + 1] = median;



				if(flag == 0)

					flag = 1;

			}

		}

	}

}

    
(2)ソートの挿入
ソートを挿入するということは、データを2つの部分に分けて、一部はすでにソートされたデータで、一部は現在ソートが完了していないデータです.では、ソートのプロセスは、ソートされていないデータを順番に並べられたキューに1つずつ挿入するプロセスではないでしょうか.みんなは自分で先に試して、それから私のコードを見てもいいですか?

void insert_sort(int array[], int length)

{

	int inner = 0;

	int outer = 0;

	int median = 0;

	if(NULL == array || 0 == length)

		return;



	for(outer = 1; outer <length; outer ++){

		for(inner = outer; inner >= 1; inner --){

			if(array[inner] < array[inner -1]){

				median = array[inner];

				array[inner] = array[inner -1];

				array[inner -1] = median;

			}else{

				break;

			}

		}

	}

}

では、挿入ソートは泡ソートのような改善方法がありますか?実はありません.ソートを挿入するたびに位置が局所的に比較されるため,バブルソートのたびに内容がグローバルに最適である.これはデータ比較の回数から分かる.
(3)ヒルソート
ヒルソートは、個人的にはバブルソートの変種と見なすことができると思います.その基本思想は、まず1つのシーケンスで減少する方法で徐々にソートすることである.例えば10個のデータがあり,シーケンス5,3,1の順に並べ替えた.まず5です.では、1と6、2と7、3と8、4と9、5と10を並べます.第2ラウンドは3で、データ1、4、7、10を並べ、さらに2、5、8を並べ、3、6、9を並べます.第3ラウンドはバブルソートと同じように、各データを並べ替えます.その利点は、キュー全体を基本的に秩序化し、データの移動回数を減らし、アルゴリズムの計算の複雑さを低減することです.

void shell_sort(int array[], int length, int step)

{

	int inner = 0;

	int outer = 0;

	int median = 0;



	if(NULL == array || 0 == length)

		return;



	for(; step >= 1; step -=2){

		for(int index = 0; index < step; index ++){

			if((length -1) < (index + step))

				continue;

			else{

				outer = index + step;

				while( (outer + step) <= (length - 1))

					outer += step;

			}



			for(;  outer >= (index + step);  outer -= step){

				for(inner = index; inner <= outer - step; inner += step){

					if(array[inner] >= array[inner + step]){

						median = array[inner];

						array[inner] = array[inner + step];

						array[inner + step] = median;

					}

				}

			}

		}

	}

}

まとめ:
(1)上のソートはすべて非再帰プログラムであり,理解は難しくないが,細部の問題,特に長さの問題に注意が必要である.
(2)コード作成の際は必ずテストケースの設計に注意する
(3)可能な場合は,検証済みのコードと関数を多く用いる.
【予告:次のブログではクイックソートの内容をご紹介します】