【データ構造】-内部並べ替え(並べ替え選択)
23819 ワード
内部並べ替え→並べ替えの選択は前に書いてあります. 1.ヘッダファイルおよびタイプ定義 .関数宣言 .基本動作 3.1簡単な選択順序 3.1.1交換 3.1.2簡単にメインプロセスを選択する 3.1.3出力試験 3.2ヒープ並べ替え 3.2.1ヒープ調整 3.2.2大きい根山 を創立します. 3.2.3スタックの主プロセス 3.2.4出力試験 .main関数 .小結 前に書く
【説明】以下のコードは最終的にはインクリメントシーケンスであり、小さい順から大きい順に並べ替えられます.
1.ヘッダファイルとタイプ定義
3.1並べ替えを簡単に選択する
3.1.1交換
3.2.1ヒープ調整
一、順序選択の概念は、整列されている要素の中で、キーワードの最小(または最大)を選択する要素に、順序付けられたシーケンスを加える毎に、n−1回が必要である. 二、二種類の選択順序の性能分析について並べ替え空間複雑度を簡単に選択する:O(1)時間複雑度:O(n 2)安定性:不安定適用性:順序記憶とチェーン記憶に適用される線形テーブル スタックの並べ替え空間複雑度:O(1)時間複雑度:O(nlog 2 n)安定性:不安定適用:順序格納に適した線形テーブル、チェーンテーブルもいいが、 は不便である.
三、その他の説明簡単な選択順序は比較的簡単で、要点は積み上げ順序を把握し、そして手書きコードです. 順序付けの重要な特徴(1)は、単純な選択順序付けおよび積み上げ順序にとって、選択された順序付け毎に、最終的な位置に要素が置かれている必要がある.この特徴は、単純な選択順序または積み上げ順序が行われているかどうかを判断する根拠としてもよいし、(2)による高速化のための①大きいルートスタックの順序に基づいて、インクリメントシーケンス①小さなルートスタックによる積み上げ順序付けであり、結果としては、逓減シーケンス である.スタックの並べ替えに関わるジグザグツリーに関する知識スタックの並べ替えは、一般的に順序格納された線形テーブルによって実現され、一次元配列を完全な二叉ツリーと見なすことができ、順序格納されている完全な二叉樹にとっては、(1)n個の結点の完全な二叉樹高h＝⌊log2n＿logn＋1(2)の順序はiの子供であり、左の順序は2 iであるという結論がある.右の子供の順序は2 i＋1で、両親の結点は⌊i/2⌋(3)i≦⌊n/2⌋であれば、結点iは分岐点であり、そうでなければ、葉結点の説明:①樹高は時間の複雑度を計算するために用いられる.②子供を山で調整するための判断③スタック調整は分岐点の調整 である.
四、ヒープの挿入削除とキーワードの比較回数について挿入①まず新しい元素を表の最後に置く②大きさの根の山の要求によって、新しい元素は絶えず上昇して、上昇し続けることができないまで、 .①削除された要素は、表の末尾(山の底)の要素で代替されます.②大きさの根山の要求により、代替元素は次々と落下しています. キーワードの比較回数(常考)①上昇:キーワードを比較するだけで②下降:子供を左右する場合、2回比較する;左の子供だけであれば、一回比較します.(完全に二叉の木の中で右の子供だけ左の子供がいないわけがないです.)
【説明】以下のコードは最終的にはインクリメントシーケンスであり、小さい順から大きい順に並べ替えられます.
1.ヘッダファイルとタイプ定義
#include<stdio.h>
#define ElemType int
/* */
void swap(int& a, int& b); //1-1.
void SelectSort(ElemType A[], int n); //1-2.
void PrintA(ElemType A[], int len); //1-3.
void HeadAdjust(ElemType A[], int k, int len); //2-1. ( )
void BuildMaxHeap(ElemType A[], int len); //2-2.
void HeapSort(ElemType A[], int len); //2-3.
void PrintB(ElemType B[], int len); //2-4.
3.1並べ替えを簡単に選択する
3.1.1交換
//1-1.
void swap(int& a, int& b) { // ，
int temp = a;
a = b;
b = temp;
}
//1-2.
void SelectSort(ElemType A[], int n) {
for (int i = 0; i < n - 1; i++) { // n-1
int min = i; //
for (int j = i + 1; j < n; j++) // A[i...n-1]
if (A[j] < A[min])
min = j; //
if (min != i)
swap(A[i], A[min]); // swap 3
}
}
//1-3.
void PrintA(ElemType A[], int len) {
for (int i = 0; i < len; i++)
printf("%d\t", A[i]);
printf("%
");
}
3.2.1ヒープ調整
//2-1. ( )
void HeadAdjust(ElemType A[], int k, int len) {
// HeadAdjust k
A[0] = A[k]; //A[0]
for (int i = 2 * k; i <= len; i *= 2) { // key
if (i < len && A[i] < A[i + 1]) //
i++; // key
if (A[0] >= A[i])
break; // ，
else { //
A[k] = A[i]; //A[i]
k = i; // k ，
}
}
A[k] = A[0]; //
}
//2-2.
void BuildMaxHeap(ElemType A[], int len) {
for (int i = len / 2; i > 0; i--) // i=[n/2]~1,
HeadAdjust(A, i, len);
}
//2-3.
void HeapSort(ElemType A[], int len) {
BuildMaxHeap(A, len); //
for (int i = len; i > 1; i--) { //n-1
swap(A[i], A[1]); // ( )
HeadAdjust(A, 1, i - 1); // ， i-1
}
}
//2-4.
void PrintB(ElemType B[], int len) {
for (int i = 1; i < len + 1; i++)
printf("%d\t", B[i]);
printf("%
");
}
int main() {
/*1、 */
ElemType A[] = { 49,38,65,97,76,13,27,49 };
SelectSort(A, 8);
printf("
");
PrintA(A, 8);
/*2、 */
ElemType B[] = { -1,53,17,78,9,45,65,87,32 };
//2-1.
BuildMaxHeap(B, 8);
printf("
");
PrintB(B, 8);
//2-2.
HeapSort(B, 8);
printf("
");
PrintB(B, 8);
return 0;
}
一、順序選択の概念
三、その他の説明
四、ヒープの挿入削除とキーワードの比較回数について