排序算法

1. 快速排序

1. 平均时间复杂度: O(\(nlog_{2}{n}\))
2. 空间复杂度: O(\(1\))

代码实现

Java

快速排序.java

void quick_sort(int[] a, int low, int high) {
    if (low >= high)    return;
    int l = low, r = high;
    int pivot = a[low];
    while(low < high) {
        while(low < high && a[high] >= pivot)   high --;
        a[low] = a[high];
        while(low < high && a[low] <= pivot)    low ++;
        a[high] = a[low];
    }
    a[low] = pivot;
    quick_sort(a, l, low - 1);
    quick_sort(a, low + 1, r);
}

2. 归并排序

1. 时间复杂度: O(\(nlog_{2}{n}\))
   最好最坏平均时间复杂度都为: O(\(nlog_{2}{n}\))
2. 空间复杂度: 辅助数组O(\(n\)) + 递归栈空间O(\(n\)) = 抓大头O(\(n\))
3. 稳定性: 稳定

代码实现

归并排序.cpp

int t[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] < q[j])    t[k++] = q[i++];
        else    t[k++] = q[j++];
    }
    while (i <= mid)    t[k++] = q[i++];
    while (j <= r)  t[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        q[i] = t[j];
}

3.待续

由于学业繁忙还未完成，后续一定会完成