C++各種共通ソートアルゴリズム
6143 ワード
1.泡立ちソート
<1>バブルソートの本質は,各サイクルが配列の先頭から末尾まで最大値を見つけて右端に置き,次のサイクルは残りのn−1個数から最大値を探して右端に置くことにある.最後の2つの数が比較交換されるまで終了する.
<2>比較方式も分かりやすく、昇順を例にa[i]とa[i+1]で比較すると、a[i]>a[i+1]、swap(a[i],a[i+1])、もちろん、10個の数を並べ替えて9回比較すると、この10個の数のうち最大値が確定します.簡単なコード実装は、void BubbleSort(int*a,int size){assert(a);for(int i=0;ia[j+1])swap(a[j],a[j+1]);}
2.ソートの挿入
<1>挿入ソートの思想は自然に挿入を主とし、もちろん最も主要なソート構想は必然的に単回してから循環し、第一歩はまず単回ソートの過程を把握する.ソートを挿入して、現在の位置の数を新しい順序に調整します.<2>2つの数を並べ替え、昇順を例に2,1を第1の数と第2の数で比較し、第2の位置の値temp=a[end+1]を保存してa[second]に大きな値を付与し、第2の位置の値を事前に保存していないと元の第2の位置の値が見つからない.次にやるべきことは自然にa[end]=tempであり,これにより2つの数のソートが完了する.3>しかし複数の数を並べ替えた場合、例えば、3,4,5,1,2を並べ替えた場合、3番目の数に進んだ場合、i=end=2となり、2と1が交換された後、–end,end<0が循環終了し、全体の過程は、1と5が比較された後、1が4と比較交換され、3と比較交換され、このときend<0,循環が終了し、このソートを完了します.<4>以上から分かるように、n-1横になるようなソートが必要であり、全体コードは以下の通りである:void InsertSort(int*a,int size)/挿入ソート{assert(a);for(int i=0;i=0){if(a[end]>temp){a[end+1]=a[end];end-;}else { break; } } a[end + 1] = temp;
}
3.ヒルソート
<1>ヒルソートは、ソートを挿入したアップグレードバージョンのように、主に膨大な要素間のソートに使用されます.並べ替えが必要なオブジェクトをgap個数が1組の順序のシーケンスに並べ替え、初期値をnとし、徐々にgap値を小さくします.gapが1の場合、挿入並べ替えと同じになります.<2>通常、gap=gap/3+1とするので、gapが1の場合、ソートの目的を達成する.<3>外層サイクル条件の制御は理解されるべきであり,挿入ソートはgapが1に相当し,自然にn−1回,すなわちn−gap回である.各グループがgap個数の複数の秩序配列に分割するため、a[end]はa[end+gap]と比較すべきである.コードは以下の通りである:void ShellSort(int*a,int size)/ヒルソート{assert(a);int gap=size;while(gap>1){gap=gap/3+1;for(int i=0;i=0){if(a[end]>temp){a[end+gap]=a[end];end-=gap;else { break; } a[end + gap] = temp; } } } }
4.ソートの選択
<1>ソートの選択のポイントは、現在のシーケンスの最大値と最小値の配置を単一のソートで完了する方法です.<2>リアルタイムの最小値と最大値を格納するためにmaxを使用する2つの変数minを定義し、すぐにa[left]とa[right]、left++、right–に配置し、leftまで、rightと出会った後に比較して終了し、ソートを完了します.コードは以下の通りです:void SelectSort(int*a,int size)/ソート{assert(a);int left=0;int right=size-1;
}
5.ヒープのソート
<1>スタックを利用してソートし,自然にまずスタックを構築する.昇順キーの山、降順に小さな山を建てます.スタックを構築するプロセスにはアルゴリズムを調整する必要があり、調整回数は最後の非葉接点の位置に依存する.pos=(n−2)/2も,ルートノードがスタックを完成するまでこの位置から調整を開始する.2>スタックトップデータは自然にスタックの中で最大の数であり、それを最後の位置の値と交換し、もう一度調整し、前のn-1の数を調整する.nが0未満になるまでこの過程を続ける.コードは以下の通りである:void AdJustDown(int*a,int size,int root){int parent=root;int child=2*parent+1;while(childa[child])child+;if(a[child]>a[parent]){swap(a[child],a[parent]);
} void HeapSort(int *a, int size) { for (int i = (size - 2)/2; i >= 0; i–) AdJustDown(a, size, i); int end = size - 1; while (end>=0) { swap(a[0], a[end]); AdJustDown(a, end,0); –end; } }
6.クイックソート
<1>高速ソートは、配列内のkey値を分割点とし、左の値を小さくし、右の値を大きくするたびに、適用面も広くソートする方法です.2つの部分に分けた後,1つの値が残る秩序空間になるまでサブ問題に移行して分割する.2>したがって,高速ソートの鍵はどのように分割するかであり,配列の最後の位置のデータをkey値とするのが一般的であるが,もちろんこの位置の値が最大または最小であれば効率を低下させ,乱数を取るか,あるいは三数取中法で高速排出時間の複雑度をnlgnに制御することもできる.3>key値を取得して1回目のソートを行うには,左右ポインタ法,ピット法,2つのポインタ追従法の3つの方式がある.①左右のポインタ:key=a[right]をとり、左はleftから、右はrightから、それぞれkey値と比較し、左はkeyより大きいものに出会って止まり、右は歩き始め、keyより小さいものに出会ってa[begin]とa[end]を交換する.ループ終了a[begin]またはa[end]まで歩いてa[right]と交換し、最初のソートを完了します.②ピット掘削法:key=a[right]を取り、同様にa[begin]を後ろに歩いてkey値より大きい停止に遭遇し、a[end]=a[begin];a[end]前に進むとkey値より小さい停止に遭遇し,a[begin]=a[end],サイクル終了,a[begin]=key,1回目のソートを完了する.③2つのポインタの追従法:key=a[right],cur=left,prev=left-1,curはkey値より小さい,prev++,cur++に遭遇し,key値より大きい停止に遭遇した場合++prev!=Cur,swap(a[cur],a[++prev]),そうでなければcur++は,cur=right,swap(a[prev],a[right])まで,1回目のソートを完了する.4>単一ソート戻り値を受け入れ、再帰呼び出しを行う.コードは、int Sort 2(int*a,int left,int right)/2つのポインタ法{int cur=left;int prev=left-1;int key=a[right];while(cur
}int Sort 1(int*a,int left,int right)/ピット掘削法{if(left= key) { end–; } a[begin] = a[end]; } a[begin] = key; return begin; } }
int Sort 3(int*a,int left,int right)/左右ポインタ法{assert(a);int begin=left;int end=right;int key=a[right];while(begin7.集計ソート
<1>集計ソートの主な考え方は,n個のm個のデータを含む秩序配列を結合し,絶えず二分してmを1にし,ソートの目的を達成することである.2>だから1組のデータを手に入れた後、先に分けてから合わせて、ここではまず元の空間と同じ大きさの空間を開いて、分けたデータを新しい空間にコピーして並べ替えを完成します.コードは、void Merge(int*a,int*temp,int begin 1,int end 1,int begin 2,int end 2){assert(a&&temp);size_t pos=begin 1;size_t index=begin 1;while(begin 1<=end 1&&begin 2<=end 2){if(a[begin 1]>a[begin 2]){temp[index+]=a[begin 2+];}else { temp[index++] = a[begin1++]; } } while (begin1 <= end1) { temp[index++] = a[begin1++]; } while (begin2 <= end2) { temp[index++] = a[begin2++]; } memcpy(a + pos, temp + pos, sizeof(int)*(end2 - pos + 1)); }
void _MergeSort(int *a, int*temp, int left, int right) { assert(a&&temp); int mid = left + (left - right)/2; _MergeSort(a, temp, left, mid ); _MergeSort(a, temp, mid + 1, right); Merge(a, temp, left, mid , mid + 1, right);
} void MergeSort(int*a, int size) { assert(a); int*temp = new int[size]; _MergeSort(a, temp, 0, size - 1); delete[] temp; }
<1>バブルソートの本質は,各サイクルが配列の先頭から末尾まで最大値を見つけて右端に置き,次のサイクルは残りのn−1個数から最大値を探して右端に置くことにある.最後の2つの数が比較交換されるまで終了する.
<2>比較方式も分かりやすく、昇順を例にa[i]とa[i+1]で比較すると、a[i]>a[i+1]、swap(a[i],a[i+1])、もちろん、10個の数を並べ替えて9回比較すると、この10個の数のうち最大値が確定します.簡単なコード実装は、void BubbleSort(int*a,int size){assert(a);for(int i=0;i
2.ソートの挿入
<1>挿入ソートの思想は自然に挿入を主とし、もちろん最も主要なソート構想は必然的に単回してから循環し、第一歩はまず単回ソートの過程を把握する.ソートを挿入して、現在の位置の数を新しい順序に調整します.<2>2つの数を並べ替え、昇順を例に2,1を第1の数と第2の数で比較し、第2の位置の値temp=a[end+1]を保存してa[second]に大きな値を付与し、第2の位置の値を事前に保存していないと元の第2の位置の値が見つからない.次にやるべきことは自然にa[end]=tempであり,これにより2つの数のソートが完了する.3>しかし複数の数を並べ替えた場合、例えば、3,4,5,1,2を並べ替えた場合、3番目の数に進んだ場合、i=end=2となり、2と1が交換された後、–end,end<0が循環終了し、全体の過程は、1と5が比較された後、1が4と比較交換され、3と比較交換され、このときend<0,循環が終了し、このソートを完了します.<4>以上から分かるように、n-1横になるようなソートが必要であり、全体コードは以下の通りである:void InsertSort(int*a,int size)/挿入ソート{assert(a);for(int i=0;i
}
}
3.ヒルソート
<1>ヒルソートは、ソートを挿入したアップグレードバージョンのように、主に膨大な要素間のソートに使用されます.並べ替えが必要なオブジェクトをgap個数が1組の順序のシーケンスに並べ替え、初期値をnとし、徐々にgap値を小さくします.gapが1の場合、挿入並べ替えと同じになります.<2>通常、gap=gap/3+1とするので、gapが1の場合、ソートの目的を達成する.<3>外層サイクル条件の制御は理解されるべきであり,挿入ソートはgapが1に相当し,自然にn−1回,すなわちn−gap回である.各グループがgap個数の複数の秩序配列に分割するため、a[end]はa[end+gap]と比較すべきである.コードは以下の通りである:void ShellSort(int*a,int size)/ヒルソート{assert(a);int gap=size;while(gap>1){gap=gap/3+1;for(int i=0;i
4.ソートの選択
<1>ソートの選択のポイントは、現在のシーケンスの最大値と最小値の配置を単一のソートで完了する方法です.<2>リアルタイムの最小値と最大値を格納するためにmaxを使用する2つの変数minを定義し、すぐにa[left]とa[right]、left++、right–に配置し、leftまで、rightと出会った後に比較して終了し、ソートを完了します.コードは以下の通りです:void SelectSort(int*a,int size)/ソート{assert(a);int left=0;int right=size-1;
while (left < right)
{
size_t min = left;
size_t max = right;
for (int i = left; i <= right; i++)
{
if (a[i] < a[min])
{
min = i;
}
if (a[i]>a[max])
{
max = i;
}
}
swap(a[left], a[min]);
if (max == left)/* left ， ， 。*/
{
max = min;
}
swap(a[max], a[right]);
left++;
right--;
}
}
5.ヒープのソート
<1>スタックを利用してソートし,自然にまずスタックを構築する.昇順キーの山、降順に小さな山を建てます.スタックを構築するプロセスにはアルゴリズムを調整する必要があり、調整回数は最後の非葉接点の位置に依存する.pos=(n−2)/2も,ルートノードがスタックを完成するまでこの位置から調整を開始する.2>スタックトップデータは自然にスタックの中で最大の数であり、それを最後の位置の値と交換し、もう一度調整し、前のn-1の数を調整する.nが0未満になるまでこの過程を続ける.コードは以下の通りである:void AdJustDown(int*a,int size,int root){int parent=root;int child=2*parent+1;while(child
parent = child;
child = parent * 2 + 1;
}
else
break;
}
} void HeapSort(int *a, int size) { for (int i = (size - 2)/2; i >= 0; i–) AdJustDown(a, size, i); int end = size - 1; while (end>=0) { swap(a[0], a[end]); AdJustDown(a, end,0); –end; } }
6.クイックソート
<1>高速ソートは、配列内のkey値を分割点とし、左の値を小さくし、右の値を大きくするたびに、適用面も広くソートする方法です.2つの部分に分けた後,1つの値が残る秩序空間になるまでサブ問題に移行して分割する.2>したがって,高速ソートの鍵はどのように分割するかであり,配列の最後の位置のデータをkey値とするのが一般的であるが,もちろんこの位置の値が最大または最小であれば効率を低下させ,乱数を取るか,あるいは三数取中法で高速排出時間の複雑度をnlgnに制御することもできる.3>key値を取得して1回目のソートを行うには,左右ポインタ法,ピット法,2つのポインタ追従法の3つの方式がある.①左右のポインタ:key=a[right]をとり、左はleftから、右はrightから、それぞれkey値と比較し、左はkeyより大きいものに出会って止まり、右は歩き始め、keyより小さいものに出会ってa[begin]とa[end]を交換する.ループ終了a[begin]またはa[end]まで歩いてa[right]と交換し、最初のソートを完了します.②ピット掘削法:key=a[right]を取り、同様にa[begin]を後ろに歩いてkey値より大きい停止に遭遇し、a[end]=a[begin];a[end]前に進むとkey値より小さい停止に遭遇し,a[begin]=a[end],サイクル終了,a[begin]=key,1回目のソートを完了する.③2つのポインタの追従法:key=a[right],cur=left,prev=left-1,curはkey値より小さい,prev++,cur++に遭遇し,key値より大きい停止に遭遇した場合++prev!=Cur,swap(a[cur],a[++prev]),そうでなければcur++は,cur=right,swap(a[prev],a[right])まで,1回目のソートを完了する.4>単一ソート戻り値を受け入れ、再帰呼び出しを行う.コードは、int Sort 2(int*a,int left,int right)/2つのポインタ法{int cur=left;int prev=left-1;int key=a[right];while(cur
}
swap(a[right], a[++prev]);
return prev;
}int Sort 1(int*a,int left,int right)/ピット掘削法{if(left
int Sort 3(int*a,int left,int right)/左右ポインタ法{assert(a);int begin=left;int end=right;int key=a[right];while(begin
<1>集計ソートの主な考え方は,n個のm個のデータを含む秩序配列を結合し,絶えず二分してmを1にし,ソートの目的を達成することである.2>だから1組のデータを手に入れた後、先に分けてから合わせて、ここではまず元の空間と同じ大きさの空間を開いて、分けたデータを新しい空間にコピーして並べ替えを完成します.コードは、void Merge(int*a,int*temp,int begin 1,int end 1,int begin 2,int end 2){assert(a&&temp);size_t pos=begin 1;size_t index=begin 1;while(begin 1<=end 1&&begin 2<=end 2){if(a[begin 1]>a[begin 2]){temp[index+]=a[begin 2+];}else { temp[index++] = a[begin1++]; } } while (begin1 <= end1) { temp[index++] = a[begin1++]; } while (begin2 <= end2) { temp[index++] = a[begin2++]; } memcpy(a + pos, temp + pos, sizeof(int)*(end2 - pos + 1)); }
void _MergeSort(int *a, int*temp, int left, int right) { assert(a&&temp); int mid = left + (left - right)/2; _MergeSort(a, temp, left, mid ); _MergeSort(a, temp, mid + 1, right); Merge(a, temp, left, mid , mid + 1, right);
} void MergeSort(int*a, int size) { assert(a); int*temp = new int[size]; _MergeSort(a, temp, 0, size - 1); delete[] temp; }