データ構造とアルゴリズムの交換ソート

交換ソートは、その名の通り、2つの数またはいくつかの数の比較と交換によってソートの目的を達成するに違いない.交換ベースのソートには主にバブルソートと高速ソートがある.
1、泡立ち順
2つの間の比較と交換により、最大の記録(昇順)または最小の記録(降順)が毎回出てくる.

void bubbleSort(int arr[],int n){
    int outer,inner;
    for(outer=1;outer<=n;outer++){
        for(inner=1;inner<=n-outer;inner++){
            if(arr[inner+1]<arr[inner]){
                arr[0] = arr[inner];
                arr[inner] = arr[inner+1];
                arr[inner+1] = arr[0];
            }
        }
    }
}

上記は従来のバブルソートであるが、最後尾のいくつかの記録が交換されていない、すなわち、後のいくつかの記録が秩序化されている場合、従来のバブルソートでは、どうしてもバブルが発生し、自然にソート時間が増加する.従って、上記従来の発泡ソートを改良することができる.次のように、交換のたびに最後の位置をexchangeIndexで記録します.

void bubbleSortModified(int arr[],int n){
    int outer,inner;
    int exchangeIndex = n;
    int exchange;
    while(exchangeIndex>1){
        exchange = 1;
        for(inner=1;inner<=exchangeIndex;inner++){
            if(arr[inner+1]<arr[inner]){
                arr[0] = arr[inner];
                arr[inner] = arr[inner+1];
                arr[inner+1] = arr[0];
                exchange = inner;
            }
        }
        exchangeIndex = exchange;
    }
}

2、クイックソート
クイックソート:シーケンス内のレコードを基準に、シーケンス全体を左右の2つのグループに分け、左のシーケンスは基準より小さく、右のシーケンスは基準より大きい.次に、左右のシーケンスに対してもう1つの基準区分を選択し、左右のシーケンスの記録数が0になるまで順次下ります.

int _quickSort(int arr[],int begin,int end){
    arr[0] = arr[begin];
    while(begin < end){
        while(begin<end && arr[end]>arr[0])
          end --;
        if(begin<end)
          arr[begin] = arr[end],arr[end] = arr[0],begin ++;
        else 
          return begin;
        while(begin<end && arr[begin]<arr[0])
          begin ++;
        if(begin<end)
          arr[end] = arr[begin],arr[begin] = arr[0],end --;
        else
          return end;
    }    
}


void quickSort(int arr[],int begin,int end){
    int middle;
    if(begin < end){
        middle = _quickSort(arr,begin,end);
        quickSort(arr,begin,middle-1);
        quickSort(arr,middle+1,end);
    }
}

3、まとめ
バブルソート:時間複雑度o(n 2)は、安定したソートアルゴリズムである.
高速ソート:時間複雑度o(nlog 2 n)は、不安定なソートアルゴリズムであり、すべてのソートアルゴリズムの中で平均性能が最も優れている.
しかし、並べ替えられるシーケンスが本来秩序化されているか、またはほぼ秩序化されていると、高速並べ替えの性能が悪くなり、時間的複雑度o(n 2)に劣化する.したがって、高速ソートはランダムなシーケンスのソートに適しています.