快排,归并

归并排序

---

模板：

public static void mergeSort(int q[],int l,int r) {
    if (l >= r) return;
    int mid = l + r >>1;

    mergeSort(q, l, mid);
    mergeSort(q, mid+1, r);

    int k = 0,i = l,j = mid + 1;
    int t[] = new int[q.length];

    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 (int j2 = 0,j3 = l; j3 <= r ; j2 ++,j3 ++) {
        q[j3] = t[j2];
    }
}

时间复杂度分析：

用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆log8次，值为3，所以树共有3层,那么自顶向下第k层有2^ k个子数组，每个数组的长度为2^( 3 - k)，归并最多需要2^ (3-k)次比较。因此每层的比较次数为2^k * 2^ (3-K)=2^ 3,那么3层总共为3* 2^3。

假设元素的个数为n，那么使用归并排序拆分的次数为log2(n)，所以共log2(n)层，那么使用log2(n)替换上面3 * 2^3中 的3这个层数，最终得出的归并排序的时间复杂度为:log2(n) * 2^(log2(n))=log2(n)n,根据大O推导法则，忽略底数，最终归并排序的时间复杂度为*o(nlogn)

快速排序

---

模板：

public static void quickSort(int q[],int l,int r){
    if (r <= l)return;
    int standard = q[l];

    int left = l - 1;
    int right = r + 1;

    while(left < right){
        while (q[++ left] < standard);
        while (q[-- right] > standard);

        if (left < right){
            int t = q[left];
            q[left] = q[right];
            q[right] = t;
        }
    }
    quickSort(q,l,right);
    quickSort(q,right+1,r);
}

时间复杂度分析：

快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n)但整个快速排序的时间复杂度和切分的次数相关。

最优情况∶每一次切分选择的基准数字刚好将当前序列等分。

如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为o(nlogn);

最坏情况∶每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);

上面说的最优时间复杂度和最差时间复杂度都是比较极端的情况，更多普遍的情况是 平均时间复杂度。有趣的是，在快速排序中，平均时间复杂度等于最优时间复杂度，它们都是O(nlogn)