排序

快速排序

partition算法

分治算法：整体有序再局部有序

1,1,1,3

1 - 1

+ - +

要点解析

1. 取pivot策略：经验下选择中点是最好的（很少能构造出让他退化成n2的数据）

2. 中心点只能是严格大或严格小才++--，等于的时候要交换，不然的话如果是全部相等的序列每次都不变，左指针走到最右侧，右指针原地不动，会造成无限递归。

3. 必须是left <= right，不然会无限递归，而且要防止左右有交集

public void sortInterger(int[] A) {
    if (A == null || A.length == 0) {
        return;
    }
    
    quickSort(A, 0, A.length - 1);
}

void quickSort(int[] A, int start, int end) {
    if (start == end) {
        return;
    }
    
    int left = start, right = end;
    int pivot = A[(start + end) / 2]; // point 1
    
    // partition算法
    while (left <= right) { // point 2
        while (left <= right && A[left] < pivot) { //point 3
            left++;
        }
        while (left <= right && A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }
    
    quickSort(A, start, right);
    quickSort(A, left, end);
}

三个要点

1. pivot
2. left <= right
3. A[left] < pivot

平均时间复杂度nlogn

最坏n2

空间O1 (Ologn递归栈的隐式空间)

归并排序

合并数组需要额外On的空间，需要合并复制这个序列

开辟和销毁空间很费时，因此而败给快排

分治法：区间分治

public void sortInterger(int[] A) {
    if (A == null || A.length == 0) {
        return;
    }
    
    int[] temp = new int[A.length];
    mergeSort(A, 0, A.length - 1, temp);
}

private void mergeSort(int[] A, int start, int end, int[] temp) {
    if (start == end) {
        return;
    }
    
    mergeSort(A, start, (start + end) / 2, temp);
    mergeSort(A, (start + end) / 2 + 1, end, temp);
    merge(A, start, end, temp);
}

private void merge(int[] A, int start, int end, int[] temp) {
    int middle = (start + end) / 2;
    int left = start, right = middle + 1;
    int index = left;
    
    while (left <= middle && right <= end) {
        if (A[left] < A[right]) {
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
    
    while (left <= middle) {
        temp[index++] = A[left++];
    }
    
    while (right <= end) {
        temp[index++] = A[right++];
    }
    
    for (int i = start; i <= end; i++) {
        A[i] = temp[i];
    }
    
}

对比

稳定排序：merge sort

空间节省：quick sort

qs整体有序再局部有序

ms局部有序再整体有序

快速选择

平均时间复杂度On

算法实现

public void sortInterger(int[] A) {
    if (A == null || A.length == 0) {
        return;
    }
    
    int[] temp = new int[A.length];
    mergeSort(A, 0, A.length - 1, temp);
}

private int quickSelect(int[] A, int start, int end, int  k) {
    // 递归出口
    if (start == end) {
        return A[start];
    }
    
    int left = start, right = end;
    int pivot = A[(start + end) / 2]; // point 1
    
    // partition算法
    while (left <= right) { // point 2
        while (left <= right && A[left] < pivot) { //point 3
            left++;
        }
        while (left <= right && A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }
    
    // quickSort(A, start, right);
    // quickSort(A, left, end);
    // 递归拆解，判断在左或右
    if (start + k - 1 <= right) {
        return quickSelect(A, start, right, k);
    }
    if (start + k - 1 >= left) {
        return quickSelect(A, left, end, k - (left - start));
    }
    
    // 恰好在这之间的位置时，找到直接返回（可能存在多个大小相同的值，返回第一个）
    return A[right + 1];
}

常见题目

1. kth 最大

2. medium

   即第一题的变形

3. medium of two sorted arrays

   hard