C++基本アルゴリズムバブル法、交換法、選択法、実装コード集合
これは最も原始的で、よく知られている最も遅いアルゴリズムです.彼の名前の由来は、その仕事が泡のように見えるからです.
#include
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;ifor(int j=Count-1;j>=i;j--) {
if(pData[j]iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main() {
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
逆順(最悪の場合)第1ラウンド:10,9,8,7−>10,9,7,8−>10,7,9,8−>10,7,9,8−>7,10,10,9,8(交換3回)第2ラウンド:7,10,9,9,8,9,8,10,8,10,9,>7,8,10(交換2回)第1ラウンド:7,8,10,9−>7,10,9,9,8,10,9−>7,10,9,8,10,9,10,9,9,8,10,9,(交換1回)サイクル回数:6回交換回数:6回交換回数:6回その他:第1ラウンド:8,10,7,7,7,9,9−>8,10,9,9,9,>,10,9−>7,8,10,9−>7,8,10,9(交換0回)第1ラウンド:7,8,10,9->7,8,9,10(交換1回)サイクル数:6回交換回数:3回上にプログラムセグメントを与えたが,ここではアルゴリズムの性能に影響する主な部分はサイクルと交換であり,明らかに回数が多ければ多いほど性能が悪くなる.上のプログラムからループの回数が固定されていることがわかります.1+2+...+n-1.公式に書くと1/2*(n-1)*nです.ここで,n>=n 0のときにf(n)<=K*g(n)があるとf(n)=O(g(n))となるように,O法の定義を与える.ここでは、K=1/2,n 0=1,g(n)=n*nの場合、1/2*(n−1)*n<=1/2*n*n=K*g(n)となる1/2*(n−1)*n<=1/2*n*n=n*n=K*g(n)とする.従ってf(n)=O(g(n)=O(n*n)となる.したがって,我々のプログラムサイクルの複雑さはO(n*n)である.また交換を見ます.プログラムの後ろに付いている表から,2つのケースのループが同じで,交換が異なることがわかる.実は交換自体はデータソースの秩序度と大きく関係しており,データが逆順序にある場合,交換回数はループと同様(ループ判定のたびに交換される),複雑度はO(n*n)である.データが正の場合、交換はありません.複雑度はO(0)である.乱順時は中間状態にある.このような理由から,アルゴリズムをループ回数で比較することが多い.2.交換法:交換法のプログラムは最もはっきりしていて簡単で、毎回現在の要素で一つ一つ後の要素と比較して交換します.
#include
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i{
for(int j=i+1;j{
if(pData[j]{
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
逆順(最悪)第1ラウンド:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3回)第2ラウンド:7,10,9,8->7,9,10,8->7,8,10,9(交換2回)第1ラウンド:7,8,10,9->7,9(交換1回)サイクル回数:6回交換回数:6回
その他:第1ラウンド:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交換1回)第2ラウンド:7,10,8,9->7,8,10,9->7,8,10,9(交換1回)第1ラウンド:7,8,10,9->7,8,9,10(交換1回)サイクル回数:6回交換回数:3回
実行している表から見ると、交換はほとんど泡のように悪い.事実は確かにそうだ.サイクル数も発泡と同様に1／2＊(n−1)＊nであるため,アルゴリズムの複雑さはO(n＊n)のままである.私たちはすべての状況を与えることができないので、交換の上でも同じように悪いことを直接伝えるしかありません(場合によってはやや良く、場合によってはやや悪い).p#サブタイトル#e#
3.選択方法:
今、私たちはやっといくつかの希望を見ることができます:選択法、この方法は少し性能を高めました(場合によっては)この方法は私たちの人為的なソート習慣に似ています:データの中から最小の同じ第1の値を選択して交換して、省の下の部分の中から最小の第2の交換を選択して、このように往復します.
#include
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i{
iTemp = pData;
iPos = i;
for(int j=i+1;j{
if(pData[j]{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData;
pData = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
逆順(最悪の場合)第1ラウンド:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1回)第2ラウンド:7,9,8,10,10->7,9,8,10->7,9,8,8,8,10(iTemp=8)->(iTemp=8)7,8,8,9,10(交換1回)第1ラウンド:7,8,9,10->(iTemp=9)7,8,9,9,9,10,9,10(交換0回)サイクル回数:6回交換1回(交換0回)サイクル回数:6回:6回:交換1回回数:2回
その他:第1ラウンド:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1回)第2ラウンド:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,8,9->(iTemp=8)7,8,10,10,10,10,10,10,8,10,10,8,9,(交換1回)7,8,9,9,9,9,10(交換1回)サイクル回数:6回の交換回数:3回残念なことにアルゴリズムに必要なサイクル回数は依然としてアルゴリズムに必要なサイクル数である1/2*(n-1)*n.したがってアルゴリズムの複雑さはO(n*n)である.私たちは彼の交換を見に来た.外層サイクルのたびに交換は1回のみ発生するため(最小値は1つのみ).だからf(n)<=nなのでf(n)=O(n)があります.したがって,データが乱れている場合には,一定の交換回数を減らすことができる.4.挿入法:挿入法は複雑で、その基本的な動作原理はカードを引き出して、前のカードの中で相応の位置を探して挿入して、それから次のカードに続きます
#include
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i{
iTemp = pData;
iPos = i-1;
while((iPos>=0) && (iTemp{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
逆順(最悪)第1ラウンド:10,9,8,7->9,10,8,7(交換1回)(サイクル1回)第2ラウンド:9,10,8,7->8,9,10,7(交換1回)(サイクル2回)第1ラウンド:8,9,10,7->7,8,9,10(交換1回)(サイクル3回)サイクル回数:6回交換回数:3回
その他:第1ラウンド:8,10,7,9->8,10,7,9(交換0回)(サイクル1回)第2ラウンド:8,10,7,9->7,8,10,9(交換1回)(サイクル2回)第1ラウンド:7,8,10,9->7,8,9(交換1回)(サイクル1回)サイクル回数:4回交換回数:2回
上の最後の挙動解析は事実上,このアルゴリズムが単純なアルゴリズムの中で最も優れていると考えられるが,実際にはそうではない.そのサイクル数は固定されていないが,O法を用いることができるからである.以上の結果から,ループの回数f(n)<=1/2*n*(n−1)<=1/2*n*nであることが分かる.したがって,その複雑さはO(n*n)である(ここでは,これらの単純なソートの違いを示すためでなければ,交換回数は依然としてこのように導くことができることを説明する).ここで交換を見ると,外観的には交換回数はO(n)(類似選択法を導く)であるが,我々は毎回内層サイクルと同じ回数の'='操作を行う.正常な交換には3回'='が必要ですが、ここは明らかに多くなったので、時間を無駄にしました.結局、個人的には、単純なソートアルゴリズムの中で、選択法が一番だと思います.ソートの挿入
#include
using namespace std;
void coutstream(int a[],int n){
for(int i=0;i!=n;i++)
cout<}
void insertsort(int a[],int n){
int temp;
for(int i=1;i{
int j=i;
temp=a; // a
while(j>0&&temp{a[j]=a[j-1];j--;}a[j]=temp;}}
int main()
{
int a[5]={1,6,4,8,4};
insertsort(a,5);//
coutstream(a,5);//
return 0;
}
二、高級ソートアルゴリズム:高級ソートアルゴリズムの中で私たちはこれだけを紹介し、同時に現在私が知っている(私が見た資料の中で)最も速いです.その仕事は依然として二叉木のように見えます.まず、中間値middleプログラムを選択し、配列の中間値を使用し、それより小さいものを左に、大きいものを右に置きます(具体的には、両側から探して、ペアを見つけて交換します).そして両側にそれぞれこの過程(最も容易な方法――再帰)を用いる.1.クイックソート:
#include
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //
do{
while((pDatai++;
while((pData[j]>middle) && (j>left))//
j--;
if(i<=j)//
{
//
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);// ， （ ）
// (leftif(leftrun(pData,left,j);
// (right>i)，
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
ここで私は行為の分析を与えていません.これは簡単なので、私たちは直接アルゴリズムを分析します.まず、最も理想的な状況を考えます.配列の大きさは2のべき乗で、このように分けて常に2で除去することができます.2と仮定したk次方,すなわちk=log 2(n)である.2.私たちが選択する値がちょうど中間値であるたびに、配列が等分されます.第1層再帰,サイクルn回,第2層サイクル2*(n/2)......従ってn+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log 2(n)*nなのでアルゴリズムの複雑度がO(log 2(n)他の場合はこの場合より劣るだけで、最悪の場合は選択されるmiddleごとに最小値または最大値であると、彼は交換法になります(再帰が使用されているため、状況はさらに悪い).しかし、このような状況が発生する確率はどのくらいだと思いますか?ほほほ、この問題を心配する必要はありません.多くの場合、迅速なソートが常に最良であることが実証されています.この問題を心配する場合は、安定したO(log 2(n)*n)アルゴリズムですが、通常は高速ソートよりも速度が遅い(スタックを再編成するため)
三、その他の順序1.双方向バブル:通常のバブルは一方向であり、ここでは双方向であり、つまり逆方向の作業を行う.コードが複雑に見えるので、よく整理するとわかりますが、振動を繰り返す方法です.このコードを書いた著者は、バブルに基づいて交換を減らすことができると考えています(私はそう思いません.私は間違っているかもしれません).どうせ面白いコードだと思うので、見る価値があります.
#include
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//
for(int i=right;i>=left;i--)
{
if(pData{
iTemp = pData;
pData = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//
for(i=left;i{
if(pData{
iTemp = pData;
pData = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<cout<}
クイックソート
#include
using namespace std;
class QuickSort
{
public:
void quick_sort(int* x,int low,int high)
{
int pivotkey;
if(low {
pivotkey=partion(x,low,high);
quick_sort(x,low,pivotkey-1);
quick_sort(x,pivotkey+1,high);
}
}
int partion(int* x,int low,int high)
{
int pivotkey;
pivotkey=x[low];
while(low {
while (low =pivotkey)
--high; // while
x[low]=x[high];
while (low ++low; // while
x[high]=x[low];
}
x[low]=pivotkey;
return low;
}
};
int main()
{
int x[10]={52,49,80,36,14,58,61,97,23,65};
QuickSort qs;
qs.quick_sort(x,0,9);
cout <for (int i=0;i <10;i++)
{
printf("%d ",x);
}
return 0;
}
2.SHELLソート
このソートはとても複雑で、プログラムを見ればわかります.まず、9、5、3、1を使用します(最後のステップは1でなければなりません).動作原理は、まず9〜1個の要素を隔てたすべての内容を並べ替え、その後、同じ方法で5〜1個の要素を並べ替えて二次的に類推することである.
#include
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step;
s = -k;
for(int j=k;j{
iTemp = pData[j];
w = j-k;// step
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<cout<}
プログラムが少し頭が痛いように見えます.しかし、難しくはありません.s=0のブロックを外すと楽になります.ここでは、0ステップでプログラムが異常になるのを避けるために書かれたコードです.このコードは見応えがある.このアルゴリズムの名前は、その発明者の名前D.L.SHELLに由来する.参考資料によると、「複雑な数学的理由で2のべき乗ステップ長を避けることで、アルゴリズムの効率を低下させることができる」という.さらにアルゴリズムの複雑さはnの1.2乗である.同様に非常に複雑で「本書の議論の範囲を超えている」ため(私も過程を知らない)、私たちは結果しかありません.バブルソート性能最適化版include
using namespace std;
void maopao(int *list,int n)
{
int i=n,j,temp;
bool exchange;// ，
for(i=0;i{
exchange=false;
for (j=0;j{
if (list[j]>list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
exchange=true;
}
}
if (!exchange)
{
return;
}
}
}
int main()
{
int a[7]={32,43,22,52,2,10,30};
maopao(a,7);
for(int i=0;i<7;i++)
cout<return 0;}