合併排序

記不記得之前談到快速排序法(Quick Sort)可以加快排序
但是切半要怎麼切才可以

版本1

空間複雜度

$O(n\log (n))$(因為陣列開固定大小，所以實作為

$O(n^2)$

//naive merge sort(for small case)
#include <iostream>
#define INF 100000009;
using namespace std;

void merge_sort(int A[], int n){
    if(n <= 1)
        return;
    //Divide
    int m = n/2;
    int nL = m, nR = n-m;
    int L[501] = {0}, R[501] = {0};
    for(int i = 0; i < nL; i++)
        L[i] = A[i];
    for(int i = 0; i < nR; i++)
        R[i] = A[m+i];
    //Conquer
    merge_sort(L, nL);
    merge_sort(R, nR);
    //Merge
    L[nL] = INF;
    R[nR] = INF;
    for(int iL = 0, iR = 0, i = 0; i < n; i++){
        if(L[iL] <= R[iR])
            A[i] = L[iL++];
        else
            A[i] = R[iR++];
    }
    return;
}

int main(){
    int A[1000] = {3,1,4,5,9,2,6,10,8,7};
    int n = 10;
    merge_sort(A, n);
    for(int i = 0; i < n; i++){
        if(i < n-1)
            cout << A[i] << ' ';
        else
            cout << A[i] << endl;
    }
    return 0;
}

版本2

空間複雜度

$O(n)$

#include <iostream>
#include <algorithm>
#define INF 999999999

using namespace std;

int L[50001] = {0};
int R[50001] = {0};

void merge(int A[], int l, int r, int m){
    int nL = m-l, nR = r-m;
    for(int i = 0; i < nL; i++)
        L[i] = A[l+i];
    for(int i = 0; i < nR; i++)
        R[i] = A[m+i];
    L[nL] = INF;        //sentinal
    R[nR] = INF;        //sentinal
    for(int i = l, li = 0, ri = 0; i < r; i++){
        if(L[li] < R[ri])
            A[i] = L[li++];
        else
            A[i] = R [ri++];
    }
}

void mergesort(int A[], int l, int r){
    //cout << l << ' ' << r << endl;
    if(r-l == 1)
        return;
    //Divide
    int m = (r+l)/2;
    //Conquer
    mergesort(A, l, m);
    mergesort(A, m, r);
    //Merge
    merge(A, l, r, m);
}

int main(){
    int A[100001] = {0};
    int n = 100000;
    for(int i = 0; i < n; i++)
        A[i] = rand() % 10000000;
    mergesort(A, 0, n);
    //  for(int i = 0; i < n; i++){
    //          cout << A[i] << " \n"[i== n-1];
    //  }
}

版本3

空間複雜度

$O(n)$ (因其他部分與版本2相同，只顯示merge)

int tmp[1000000] = {0};
void merge(int A[], int l, int r, int m){
    int ri = m, k = 0;
    for(int li = l; li < m; li++){
        while(ri < r && A[ri] < A[li])
            tmp[k++] = A[ri++];
        tmp[k++] = A[li];
    }
    for(int i = 0; i < k; i++)
        A[l+i] = tmp[i];
    return;
}

---

快速排序法

版本1

(空間複雜度O(nlog(n)))

#include <iostream>
using namespace std;

int L[100000], R[100000];
void quicksort(int A[], int l, int r){
    if(r-l <= 1) return;
    int pivot = A[l];
    int nL = 0, nR = 0;
    for(int i = l+1; i < r; i++){
        if(A[i] < pivot)
            L[nL++] = A[i];
        else
            R[nR++] = A[i];
    }
    for(int i = 0; i < nL; i++){
        A[i+l] = L[i];
    }
    A[l+nL] = pivot;
    for(int i = 0; i < nR; i++){
        A[i+l+nL+1] = R[i];
    }

    quicksort(A, l, l+nL);
    quicksort(A, l+nL+1, r);
    return;
}

int main(){
    int A[100] = {5,10,3,1,9,6,2,4,8,7};
    int n = 10;
    quicksort(A, 0, n);
    for(int i = 0; i < n ; i++){
        cout << A[i] << " ";
    }
    cout << '\n';
}

版本 2

#include <iostream>
#include <algorithm>
using namespace std;

void quicksort(int A[], int l, int r){
    if(r <= l) return;
    int pivot = A[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (A[j] < pivot) {
            swap(A[i], A[j]);
            i++;
        }
    }
    swap(A[i], A[r]);
    int pi = i;
    //cout << l << ' ' << r << ' ' << pi << '\n';
    for(int i = l; i <= r; i++)
        cout << A[i] << ' ';
    cout << '\n';

    quicksort(A, l, pi-1);
    quicksort(A, pi+1, r);
    return;
}

int main(){
    int A[100] = {5,10,3,1,9,6,2,4,8,7};
    int n = 10;
    for(int i = 0; i < n ; i++){
        cout << A[i] << " ";
    }
    cout << '\n';
    quicksort(A, 0, n-1);
    for(int i = 0; i < n ; i++){
        cout << A[i] << " ";
    }
    cout << '\n';
}

版本3

#include <iostream>
using namespace std;

void quicksort(int A[], int l, int r){
    if(r-l <= 1) return;
    int pivot = A[l];
    int li = l+1, ri = r-1;
    while(li != ri){
        while(li != ri &&A[ri] >= pivot)
            ri--;
        while(li != ri && A[li] < pivot)
            li++;
        if(li != ri)
            A[li] ^= A[ri] ^= A[li] ^= A[ri];
        else if(pivot > A[li])
            A[l] ^= A[li] ^= A[l] ^= A[li];
        else
            li = ri = l;
    }
    cout << l << ' ' << r << ' ' << li << '\n';
    for(int i = l; i < r; i++)
        cout << A[i] << ' ';
    cout << '\n';

    quicksort(A, l, li);
    quicksort(A, li+1, r);
    return;
}

int main(){
    int A[100] = {5,10,3,1,9,6,2,4,8,7};
    int n = 10;
    quicksort(A, 0, n);
    for(int i = 0; i < n ; i++)
        cout << A[i] << " ";
    cout << '\n';
}