返回
勤能补拙

排序算法

几种经典排序

常见的几种排序算法

快速排序

概念：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。主要采用分治法和挖坑填数等方法，分治法就是大问题分解成各种小问题，对小问题求解，使得大问题得以解决。

步骤

定义一个无序数组

1

int[] arr={4,2,8,0,5,7,1,3,9};

第一步，取基准数

基准数（枢轴），取数组的第一个元素，此时基准数：arr[0]=4

并定义两个变量i和j分别指向无序数组的第一个元素start和最后一个元素end

1
2
3
4
5

//起始
int i=start;
int j=end;
//获取基准数
int temp=arr[start];

第二步，分区过程

分区过程，将比基准数大的数全放到它的右边，比基准数小的或者相等的数全放到它的左边。

我们首先把第一个元素arr[0]=4定义为基准元素，此时数组第一个位置就是坑，那么我们要从数组的右边向左开始查找小于基准数的元素，并与坑互换位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

while(i<j){
    //从右向左去找比基准数小的
    while(i<j&&arr[j]>=temp){
        j--;
    }
    //判断相等，填坑
    if(i<j){
        arr[i]=arr[j];
        i++;
    }
}

换好位置之后，现在转换，从数组的左边向右边查找比基准数大的元素：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

while(i<j){
    //从右向左去找比基准数小的
    while(i<j&&arr[j]>=temp){
        j--;
    }
    //判断相等，填坑
    if(i<j){
        arr[i]=arr[j];
        i++;
    }
    //从左向右去找比基准数大的
    while(i<j&&arr[i]<temp){
        i++;
    }
    //判断相等，填坑
    if(i<j){
        arr[j]=arr[i];
        j--;
    }
}

换好位置之后，现在又重新开始从数组右边向左边开始查找，比基准数小的元素：

不断重复此类操作，直到分成左右两个分区，再把基准数填入坑中，这样第一趟排序完成。如下：

1
2

//把基准数放到i=j的位置
arr[i]=temp;

第三步，对两个区间进行分区操作

这里，我们对分好的两个区间重复进行上述分区操作，直到每个区间只有一个元素为止。

重复进行以上操作，直到左右两边分区都是有序排列，整个排序过程也就完成了：

1
2
3
4

//对左半边部分进行快排
QuickSort(arr,start,i-1);
//对右半边部分进行快排
QuickSort(arr,i+1,end);

完整代码

 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

import java.util.Arrays;

public class Quick_Sort {
    public static void main(String[] args) {
        int[] arr=new int[]{4,2,8,0,5,7,1,3,9};
        System.out.println(Arrays.toString(QuickSort(arr,0,arr.length-1)));
    }

    public static int[] QuickSort(int[] arr,int start,int end){
        //起始
        int i=start;
        int j=end;
        //获取基准数
        int temp=arr[start];
        //i<j为循环条件
        if(i<j){
            while(i<j){
                //从右向左去找比基准数小的
                while(i<j&&arr[j]>=temp){
                    j--;
                }
                //判断相等，填坑
                if(i<j){
                    arr[i]=arr[j];
                    i++;
                }
                //从左向右去找比基准数大的
                while(i<j&&arr[i]<temp){
                    i++;
                }
                //判断相等，填坑
                if(i<j){
                    arr[j]=arr[i];
                    j--;
                }
            }
            //把基准数放到i=j的位置
            arr[i]=temp;
            //对左半边部分进行快排
            QuickSort(arr,start,i-1);
            //对右半边部分进行快排
            QuickSort(arr,i+1,end);
        }
        return arr;
    }
}

拓展：TOPK个数

单纯快排的话时间复杂度为$$O(nlogn)$$

基于快排的数组划分：参考LeetCode题解剑指 Offer 40. 最小的 k 个数（基于快速排序的数组划分，清晰图解） - 最小的k个数 - 力扣（LeetCode）

题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标。

根据快速排序原理，如果某次哨兵划分后 基准数正好是第 k+1 小的数字 ，那么此时基准数左边的所有数字便是题目所求的 最小的 k 个数 。

根据此思路，考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于 k ，若 true 则直接返回此时数组的前 k 个数字即可。

算法流程

getLeastNumbers()函数：

1.若k大于数组长度，则直接返回整个数组

2.执行并返回quick_sort()即可

quick_sort()函数：

注意，此时quick_sort()函数的功能并不是排序整个数组，而是搜索并返回最小的k个数

  1. 哨兵划分：
    • 划分完毕后，基准数为arr[i]，在/右子数组区间分别为$$[l,i-1]，[i+1,r]$$
  2. 递归或返回
    • 若 k*<*i，代表第 k+1 小的数字在 左子数组 中，则递归左子数组
    • 若k>i ，代表第k+1 小的数字在 右子数组 中，则递归右子数组
    • 若 k=i ，代表此时 arr[k] 即为第k+1 小的数字，则直接返回数组前 k 个数字即可

时间复杂度：$\Theta(\ N)$

其中 $N$ 为数组元素数量；对于长度为 $N$ 的数组执行哨兵划分操作的时间复杂度为 $\Theta(N)$ ；每轮哨兵划分后根据 $k$ 和 $i$ 的大小关系选择递归，由于 $i$ 分布的随机性，则向下递归子数组的平均长度为 $\frac{N}{2}$ ；因此平均情况下，哨兵划分操作一共有 $N+\frac{N}{2}+\frac{N}{4}+…+\frac{N}{N}=\frac{N-\frac{1}{2}}{1-\frac{1}{2}}=2N-1$（等比数列求和） 空间复杂度 $\Theta(\log N)$ ： 划分函数的平均递归深度为 $\Theta(\log N)$ 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

归并排序

  • 归并排序是典型的分治的应用

算法思路

归并排序两个基本操作，一个是分，也就是把原数组划分为两个子数组的过程，另一个是治，将两个有序数组合并成一个更大的有序数组。

  1. 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  2. 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

动画演示

时间复杂度：$$O(nlogn)$$仅次于快排

空间复杂度：$$O(N)$$

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public static int[] mergeSort(int[] nums, int l, int h) {
    if (l == h)
        return new int[] { nums[l] };

    int mid = l + (h - l) / 2;
    int[] leftArr = mergeSort(nums, l, mid); //左有序数组
    int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
    int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组

    int m = 0, i = 0, j = 0; 
    while (i < leftArr.length && j < rightArr.length) {
        newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length)
        newNum[m++] = leftArr[i++];
    while (j < rightArr.length)
        newNum[m++] = rightArr[j++];
    return newNum;
}

拓展：数组中的逆序对

代码实现：

 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
54
55
56
57
58
59
60
61

class Solution {
    //利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
    //计算公式； mid-left+1
    //定义一个全局的计数器变量
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums,int left,int right){
        //当只有一个节点的时候，直接返回，退出递归
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        //左拆分
        mergeSort(nums,left,mid);
        //右拆分
        mergeSort(nums,mid+1,right);
        //合并
        merge(nums,left,mid,right);
    }
    public void merge(int[] nums,int left,int mid,int right){
        //定义一个临时数组
        int[] temp = new int[right-left+1];
        //定义一个指针，指向第一个数组的第一个元素
        int i = left;
        //定义一个指针，指向第二个数组的第一个元素
        int j = mid+1;
        //定义一个指针，指向临时数组的第一个元素
        int t = 0;
        //当两个数组都有元素的时候，遍历比较每个元素大小
        while(i <= mid && j <= right){
            //比较两个数组的元素，取较小的元素加入到，临时数组中
            //并将两个指针指向下一个元素
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                //当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
                //此时这个数就是，逆序数
                //定义一个计数器，记下每次合并中存在的逆序数。
                count += mid-i+1;
                temp[t++] = nums[j++];
            }
        }
        //当左边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        //当右边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(j <= right){
            temp[t++] =nums[j++];
        }
        //将新数组中的元素，覆盖nums旧数组中的元素。
        //此时数组的元素已经是有序的
        for(int k =0; k< temp.length;k++){
            nums[left+k] = temp[k];
        }
    }
}
© 2022 - 2024 Climbing Mouse

Built with Hugo
主题 Stack 由 Jimmy 设计
本博客已稳定运行