排序

[thyecust]

选择排序

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void SelectSort(int A[], int N) {
    int i,j,k;
    for (i = 0; i < N - 1; i++) {
        k = i;
        for (j = i + 1; j < N; j++){
            if (A[j] < A[k]) {
                k = j;
            }
        }
        swap(&A[i], &A[k]);
    }
}

void show(int A[], int N) {
    int i;
    for (i = 0; i < N; i++) {
        std::cout << A[i] << " ";
    }
    std::cout << endl;
}

int main() {
    int A[5] = {1,3,2,4,5};
    SelectSort(A, 5);
    show(A, 5);
}

考虑 2,2,1，可见选择排序是不稳定的。

时间复杂度是 O(n^2)，空间复杂度 O(1)。

插入排序

void InsertSort(int A[], int N) {
    int p, i;
    int ap;
    for (p = 1; p < N; p++) {
        ap = A[p];
        for (i = p; i > 0 && A[i-1] > ap; i--){
            A[i] = A[i-1];
        }
        A[i] = ap;
        show(A, N);
    }
}

int main() {
    int A[6] = {5,4,3,7,2,1};
    InsertSort(A, 6);
}

输出：

4 5 3 7 2 1
3 4 5 7 2 1
3 4 5 7 2 1
2 3 4 5 7 1
1 2 3 4 5 7

是稳定排序。

希尔排序

void ShellSort(int A[], int N) {
    int si, d, p, i;
    int tmp;
    int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

    for (si = 0; Sedgewick[si] < N; si++);
    for (d = Sedgewick[si]; d > 0; d = Sedgewick[++si]) {
        for (p = d; p < N; p++) {
            tmp = A[p];
            for (i = p; i >= d && A[i-d] > tmp; i -= d) {
                A[i] = A[i-d];
            }
            A[i] = tmp;
            show(A, N);
        }
    }
}

冒泡排序

void BubbleSort(int A[], int N) {
    int p, i;
    bool flag;

    for (p = N - 1; p >= 0; p--) {
        flag = true;
        for (i = 0; i < p; i++) {
            if (A[i] > A[i+1]) {
                swap(&A[i], &A[i+1]);
                flag = false;
            }
        }
        show(A, N);
        if (flag) break;
    }
}

[thyecust]

快速排序

def InsertSort(arr: list):
    isorted = 1
    while isorted < len(arr):
        tmp = arr[isorted]
        i = isorted - 1
        while i >= 0 and tmp < arr[i]:
            arr[i + 1] = arr[i]
            i -= 1
        arr[i+1] = tmp
        isorted += 1

def Isort(arr: list, left: int, right: int):
    a = arr[left:right+1]
    InsertSort(a)
    arr[left:right+1] = a

def median3(arr: list, left: int, right: int):
    center = (left + right) // 2
    # make arr[left] <= arr[center] <= arr[right]
    if arr[left] > arr[center]:
        arr[left],arr[center] = arr[center],arr[left]
    if arr[center] > arr[right]:
        arr[center],arr[right] = arr[right],arr[center]
    if arr[left] > arr[right]:
        arr[left],arr[right] = arr[right],arr[center]
    # move arr[center] to right end
    arr[center],arr[right] = arr[right],arr[center]
    return arr[right]

def Qsort(arr: list, left: int, right: int):
    if right - left > 5:
        pivot = median3(arr, left, right)
        lo, hi = left, right - 1
        while True:
            if arr[lo] < pivot:
                lo += 1
            if arr[hi] > pivot:
                hi -= 1
            if lo < hi:
                arr[lo], arr[hi] = arr[hi], arr[lo]
            else:
                arr[lo], arr[-1] = arr[-1], arr[lo]
                break
        Qsort(arr, left, hi)
        Qsort(arr, hi, right)
    else:
        Isort(arr, left, right)


def QuickSort(arr: list):
    Qsort(arr, 0, len(arr) - 1)

if __name__ == "__main__":
    arr = [35,12,7,36,43,44,94,59,85,52,62,8,11,3,4,5,2]
    QuickSort(arr)
    print(arr)