C++は経典の順序付けのアルゴリズムを実現します(一)——順序付けと泡の順序付けを挿入します

ソートアルゴリズムは、プログラマーが面接するときに必ず聞かれる質問の一つであるはずです.まとめると、次のいくつかの質問について説明します.

どのソートアルゴリズムを知っていますか?

xxソートアルゴリズムの実現原理

を具体的に紹介する

xxソートアルゴリズムの時間複雑度と空間複雑度はそれぞれいくらですか?

xxソートアルゴリズムは安定していますか?

以上のいくつかの問題に直面して、まず、ソートとは何か、時間/空間の複雑さとは何か、安定ソートとは何かを知る必要があります.まず、ソートの問題は、無秩序なデータのセットを秩序化することである(昇順でも降順でもよい).例を挙げると、<3,2,5,4,7,9,0,1>というデータのセットがあなたのコード処理を経て<0,1,2,3,4,5,7,9>になり、ソートプロセスが完了します.次に,時間的複雑さと空間的複雑さの問題である.時間複雑度は,実装コード全体の実行時間を記述するために用いられ,空間複雑度は実行時に消費される空間(レジスタ,メモリ)である.ここではあまり紹介しないで、具体的には私の別のブログを参考にすることができます.最後に、いわゆる安定性であり、並べ替えアルゴリズムの安定性とは、並べ替え対象データに2つの同数a 0==a 1が現れる場合、a 0はa 1の前にあり、並べ替えが完了すると、a 0は必然的にa 1と隣接するが、この場合、a 0はa 1の前になければならない.この場合、この並べ替えは安定であり、そうでなければ不安定な並べ替えと呼ぶ.
以上の基礎知識があれば、まず最初のソートアルゴリズムを紹介します.ソートを挿入します.ソートアルゴリズムを挿入するのはとても理解しやすいので、この文章を必ず見たい人はみな地主と戦ったことがあるでしょう(鉄棒は受け入れず、デフォルトで遊んだことがありますが、遊んだことがない人は今トランプを買って、二人で游びました).私たちがトランプを触るとき、私たちはトランプを一定の順序で並べて、左から右、大きいから小さいか、右から大きいから小さいまで並べます.私たちはいつも1枚のカードを触った後、手のカードと順番に比較して、このカードの適当な位置を見つけて、それを手に入れます.これが伝説の挿入ソート法です.その基本原理を理解したら、次のような偽コードを書くことができます.

void insertionSort(arr[], len){  //              
	for i from 1 to len:  //         ，    0 
		temp = arr[i]  //        
		for j from i to 0 and arr[j - 1] > temp:  //  i                      ，             （  ）    。 
			arr[j] = arr[j - 1]
		arr[j] = temp  //          ，                       ，       。
}

故宮の上の偽コードと同じように、アルゴリズム全体の大まかな構造を決定することができます.では、次の問題は、どのようなタイプのデータを比較する必要がありますか?ここではC++のtemplateテンプレートを参照してください.テンプレートがあれば、クラスを含む比較したいデータ型を比較できます(「>」オペレータを再構築すればいいだけです).
コードは次のとおりです.

#include

using namespace std;

template<typename T>
void insertionSort(T arr[], int len) {  //              
	for (int i = 1; i < len; i++) {  //          
		T temp = *(arr + i);  //            
		int j;
		for (j = i; j > 0 && *(arr + j - 1) > temp; j--)  //  i      ， i - 1     i  ，   。
		//for (j = i; j > 0 && *(arr + j - 1) >= temp; j--)  //       
			*(arr + j) = *(arr + j - 1);
		*(arr + j) = temp;  //             
	}
}

int main() {
	char a[] = { '1','5','3','4','6','5','3', '7', '0', 'a', 'B' };
	insertionSort(a, sizeof(a) / sizeof(char));
	for (auto p : a) {
		cout << p << "\t";
	}
}

いくつかの重要な問題がありますが、このソートアルゴリズムの時間的複雑さと空間的複雑さはいくらですか.私たちは2つの状況を考えています.

の最良の状況は、配列がもともと順番に並んでいるので、これ以上ソートする必要はありません.私たちのコードは一度検出するだけで完了します.すなわち、上記コードのうち最外層ループは実行する、内層ループは実行しないので、時間的複雑度はO(n)

である.

の最悪の場合、配列が逆シーケンスである場合、各数を順次移転する必要があります.これにより,最外層のループはすべて実行されるだけでなく,内層のデータもすべて実行される.従って時間的複雑度はO(n 2)である.

明らかに、ここでの空間複雑度はO(1)である.一般に、挿入ソート法は、データ量が小さい場合に用いられ、データ量が大きすぎると、挿入ソートアルゴリズムの効率が非常に低くなる.このほか,挿入ソートが安定ソートであるか否かを判断する必要がある.上のコードから見ると,挿入ソートは安定ソートアルゴリズムに属し,理由は以下の通りである:<1,5,3,4,6,5,3>の配列があり,ここでは2つの同じ数があると仮定する.挿入ソート法でソートする場合は、現在の数よりも小さい数を見つけてから挿入します.したがって、2番目の5を見つけると、前ではなく最初の5の後ろに置くだけです.従って,挿入ソート法は安定ソートアルゴリズムに属する.もちろん,挿入ソートアルゴリズムは不安定ソートアルゴリズムにもなり,1箇所を修正することで,上記コードの2番目のforループを次の行に置き換えることができ,なぜかを考えることができる.
次に、泡立ちソートを見てみましょう.泡立ちソート法も分かりやすいです.泡立ちとは、大数を下に沈めるたびに小数を上に浮かべ、魚が泡を吐くのと似ている.したがって、泡ソートと呼ばれます.バブルソートの基本的な考え方は、すべてのデータを遍歴し、順次2つ比較し、大きい場合は交換し、そうでない場合は比較を続け、その偽コードは以下の通りである.

void bubbleSort(arr[], int len){
	for i from 0 to len:
		forj from i + 1 to len:
			if arr[i] < arr[j]:
				swap(arr[i], arr[j])
}

したがって、コードによって以下のように実現される.

#include

using namespace std;

template<typename T>
void bubbleSort(T arr[], int len) {  //              
	for (int i = 0; i < len; i++) {  //          
		for(int j = i + 1; j < len; j++)
			if (*(arr + i) > * (arr + j)) {
				T temp = *(arr + j);
				*(arr + j) = *(arr + i);
				*(arr + i) = temp;
			}
	}
}

int main() {
	char a[] = { '1','5','3','4','6','5','3', '7', '0', 'a', 'B' };
	bubbleSort(a, sizeof(a) / sizeof(char));
	for (auto p : a) {
		cout << p << "\t";
	}
}

同様に,バブルソート法の時間的複雑度もO(n),最悪もO(n 2),空間的複雑度O(1)および安定ソートアルゴリズムに属することが望ましい.もちろん不安定になることもできますが、1箇所だけ修正すればいいです.