快速排序

参考资料

全网最好懂的快速排序的原理

基本思想

通过枢轴将元素序列划分成左右两个子序列 left 和 right，其中 left 比枢轴小，right 比枢轴大，然后再对枢轴左右两侧递归执行快速排序

荷兰旗思路

quickSort

1
2
3
4
5
6
public void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}
1
2
3
4
5
6
7
8
9
10
public void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // 等概率随机选一个位置，把他跟最右边的数字交换
        swap(arr, left + (int)(Math.random() * (right - left + 1)), right);
        // 进行partition，返回数组长度为2，划分值等于区域范围的左右边界
        int[] p = partition(arr, left, right);
        quickSort(arr, left, p[0] - 1); // p[0] - 1：小于区域右边界
        quickSort(arr, p[1] + 1, right); // p[1] + 1：大于区域左边界
    }
}

partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] partition(int[] arr, int left, int right) {
    int lessZoneRightBoundary = left - 1; // 小于区域右边界
    int moreZoneLeftBoundary = right + 1; // 大于区域左边界

    while (left < moreZoneLeftBoundary) { // 小于区域右边界
        if (arr[left] < arr[right]) { // 当前数小于划分值
            swap(arr, ++lessZoneRightBoundary, left++); // 把当前数和小于区域的下一个数交换，小于区域右括，left++
        } else if (arr[left] > arr[right]) { // 当前数大于划分值
            swap(arr, --moreZoneLeftBoundary, left); // 把当前数和大于区域的前一个数交换，大于区域左扩，left不变，因为数从右边区域交换完没有检查
        } else { // 等于区域
            left++; // 直接跳下一个
        }
    }

    return new int[] {lessZoneRightBoundary + 1 , moreZoneLeftBoundary - 1}; // 等于区域的左右边界
}

一般思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 参考 ：https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842
/**
 * 双边指针（交换法）
 * 思路：
 * 记录分界值 pivot，创建左右指针（记录下标）。
 * （分界值选择方式有：首元素，随机选取，三数取中法）
 *
 * 首先从右向左找出比pivot小的数据，
 * 然后从左向右找出比pivot大的数据，
 * 左右指针数据交换，进入下次循环。
 *
 * 结束循环后将当前指针数据与分界值互换，
 * 返回当前指针下标（即分界值下标）
 */
public void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = doublePointerSwap(array, start, end);
        // 用分界值下标区分出左右区间，进行递归调用
        quickSort(array, start, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, end);
    }

public int doublePointerSwap(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex];
    int leftPoint = startIndex;
    int rightPoint = endIndex;

    while (leftPoint < rightPoint) {
        // 从右向左找出比pivot小的数据
        while (leftPoint < rightPoint
                && arr[rightPoint] > pivot) {
            rightPoint--;
        }
        // 从左向右找出比pivot大的数据
        while (leftPoint < rightPoint
                && arr[leftPoint] <= pivot) {
            leftPoint++;
        }
        // 没有过界则交换
        if (leftPoint < rightPoint) {
            int temp = arr[leftPoint];
            arr[leftPoint] = arr[rightPoint];
            arr[rightPoint] = temp;
        }
    }
    // 最终将分界值与当前指针数据交换
    arr[startIndex] = arr[rightPoint];
    arr[rightPoint] = pivot;
    // 返回分界值所在下标
    return rightPoint;
}

数组中第 K 大的值

215. 数组中的第K个最大元素

问题

【LeetCode 215】：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

基于快速排序的选择方法

选取 pivot，把小于 pivot 的元素都移到 pivot 之前，这样 pivot 所在位置就是第 pivot index 小的元素。

只要找到当前 pivot 的位置是否是在第 $n-k$ 小的位置，如果是，找到第 $k$ 大的数直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 基于快速排序的选择方法
public int findKthLargest(int[] _nums, int k) {
    // 第 K 大 --> 第 N - K 小
    return search(_nums, 0, _nums.length - 1, _nums.length - k);
}

public int search(int[] nums, int begin, int end, int k) {
    int pivotIndex = partition(nums, begin, end);

    if (pivotIndex == k) {
        return nums[pivotIndex];
    } else if (pivotIndex > k) {
        return search(nums, begin, pivotIndex - 1, k);
    } else {
        return search(nums, pivotIndex + 1, end, k);
    }
}

public int partition(int[] nums, int startIndex, int endIndex) {
    int pivot = nums[startIndex];
    int leftPoint = startIndex;
    int rightPoint = endIndex;

    while (leftPoint < rightPoint) {
        while (leftPoint < rightPoint
                && nums[rightPoint] > pivot) {
            rightPoint--;
        }
        while (leftPoint < rightPoint
                && nums[leftPoint] <= pivot) {
            leftPoint++;
        }
        if (leftPoint < rightPoint) {
            int temp = nums[leftPoint];
            nums[leftPoint] = nums[rightPoint];
            nums[rightPoint] = temp;
        }
    }
    // 最终将分界值与当前指针数据交换
    nums[startIndex] = nums[rightPoint];
    nums[rightPoint] = pivot;
    // 返回分界值所在下标
    return rightPoint;
}

基于堆排序的选择方法

使用大根堆做 k−1 次删除操作后堆顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 大根堆
public int findKthLargest(int[] nums, int k) {
    int heapSize = nums.length;
    buildMaxHeap(nums, heapSize);
    for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
        swap(nums, 0, i);
        --heapSize;
        maxHeapify(nums, 0, heapSize);
    }
    return nums[0];
}

// 构造大根堆
public void buildMaxHeap(int[] a, int heapSize) {
    for (int i = heapSize / 2; i >= 0; --i) {
        maxHeapify(a, i, heapSize);
    }
}

public void maxHeapify(int[] a, int i, int heapSize) {
    int l = i * 2 + 1, r = i * 2 + 2, largest = i;
    if (l < heapSize && a[l] > a[largest]) {
        largest = l;
    }
    if (r < heapSize && a[r] > a[largest]) {
        largest = r;
    }
    if (largest != i) {
        swap(a, i, largest);
        maxHeapify(a, largest, heapSize);
    }
}

public void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = 0;
    int p1 = left;
    int p2 = mid + 1;

    // 当左右两部分都有剩余元素
    while (p1 <= mid && p2 <= right) {
        temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }

    // 当左部分有剩余元素
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }

    // 当右部分有剩余元素
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }

    // 重新拷贝回原始数组对应位置
    for (int j = 0; j < temp.length ; j++) {
        arr[left + j] = temp[j];
    }
}

public void mergeSort(int[] arr, int left, int right) {
    if (left == right) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    // 递归归并左部分
    mergeSort(arr, left, mid);
    // 递归归并右部分
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

public void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}