一般的なソートアルゴリズムc++のまとめ

挿入ソート、バブルソート、高速ソートなど、一般的なソートアルゴリズムをまとめます.
1.ソートの直接挿入
シーケンス全体を秩序領域と無秩序領域に分け、最初の要素を初期秩序領域として取り、次に2番目の開始を秩序領域の適切な位置に順次挿入し、順序が整うまで挿入します.
次に、具体的なコード実装を示します.

void InsertSort2(vector &num){
    for(int i = 1;i < num.size();++i){
        for(int j = i;j > 0;--j){
            if(num[j] < num[j - 1]){
                int temp = num[j];
                num[j] = num[j-1];
                num[j-1] = temp;
            }
        }
    }
}

挿入ソートの時間的複雑度が最も良いのは,既に正規のシーケンスであり,(n−1)回,時間的複雑度がO(n),最悪の場合は逆シーケンスのシーケンスであり,n(n−1)/2回,時間的複雑度がO(n^2),平均すると時間的複雑度がO(n^2)である.
ソートを挿入するのは安定したソート方法で、ソート要素が少ない場合はよく、大量の要素は効率が低下します.
2.泡立ちソート
隣接する要素を比較し、逆順序で交換すると、プロセスも秩序化領域と無秩序領域に分けられ、初期は秩序化領域が空で、すべての要素が無秩序領域にあり、1回目を通過すると最大の要素を見つけることができ、それから繰り返すことができます.
バブルソート感覚は非常によく理解され、第1のforサイクルはすべての要素を遍歴し、第2のforサイクルは要素を遍歴するたびに無秩序領域の隣接する2つの要素を1回比較し、逆シーケンスであれば交換する.
時間複雑度が最悪の場合は逆シーケンスであり,n(n−1)/2回を比較し,時間複雑度はO(n^2)であり,最良の場合は正シーケンスであり,(n−1)回の比較のみを行い,移動を必要とせず,時間複雑度はO(n)であり,平均時間複雑度はO(n^2)である.
しかし、最初の比較が終わって交換がなければ、順序が整っていることを示し、次の遍歴を行うべきではないもっと良い方法があります.また,部分的に秩序あるシーケンスを遍歴した後も,その部分を遍歴する必要はなく,すなわち交換が発生した場所の後の場所を遍歴する必要はない.

void BubbleSort(int arr[], int len){
 int i,temp;
 //    ，                
 int current,last = len - 1;
 while(last > 0) {
  for(i = current = 0;i < last;++i){
   if(arr[i] > arr[i+1]){
    temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
    //       ，        current  for      0
    current = i;
   }
  }
  // current = 0             ，      
  last = current;
 }
}

バブルソートも安定したソートアルゴリズムであり,元素が少ない場合の効率が高い.
3.クイックソート
クイックソートでは、まず軸値(pivot、データムとも呼ばれる)を選択し、ソートされるレコードを独立した2つの部分に分割し、左側の要素は軸値より小さく、右側の要素は軸値より大きいか等しいかを選択し、シーケンス全体が整列するまで繰り返します.プロシージャは二叉探索ツリーに似ており,再帰的なプロシージャである.

//    ;
#include
#include
using namespace std;

void Quick_sort(int a[],int left,int right) //    ;
{
    if(left > right)    return;
    int i = left,j = right;
    int base = a[left];     //     ;
    while(i != j)
    {
        while(i < j && a[j] >= base)    //           ;
            j--;
        while(i < j && a[i] <= base)    //      ;
            i++;
        if(i < j)               // i j    ;
            swap(a[i],a[j]);    //     ;
    }
    swap(a[left],a[i]);         //      ;
    Quick_sort(a,left,i-1);     //     ;
    Quick_sort(a,i+1,right);    //     ;
}

この図は普通の棒じゃない!!Wikipediaから来ました.
高速ソート時間の複雑度の最良の場合は平均と同様にO(nlog 2 n),最悪の場合O(n^2)であり,これは前の2つのソートよりも良好に見えるが,これは不安定なアルゴリズムであり,空間的複雑度が少し高い(O(nlog 2 n)).また、クイックソートは要素が多い場合に適しています.
未完待続...
 
転載先:https://www.cnblogs.com/FrankChen831X/p/10326088.html