Fivelike
0%

Sort2

Posted on Edited on In

排序部分知识点Part2。

荷兰国旗问题

image-20200910214746938

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Code_08_NetherlandsFlag {
    public static int[] partition(int[] arr, int l, int r, int p) {
        int less = l - 1;
        int more = r + 1;
        while (l < more) {
            if (arr[l] < p) {
                swap(arr, ++less, l++);
            } else if (arr[l] > p) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //swap 写成异或形式的话，要考虑i==j的情况，否则如果i==j，异或交换会将索引处的值变为0 *——*
}

随机快速排序

可以用荷兰国旗问题来改进快速排序，经典快排一次partition只搞定一个数

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
public class Code_04_QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  • 时间复杂度：O(N*logN)
  • 额外空间复杂度：O(logN) 因为每次partition需要记住索引

堆排序

堆——完全二叉树 {大根堆，小根堆} 以0开始数组存储
左孩子：2×i+1
右孩子：2×i+2
父节点：(i-1)/2

堆结构非常重要：

  1. 堆结构的 heapInsert 和 heapify
  2. 堆结构的增大和减小
  3. 如果只是建立堆的过程，时间复杂度为O(1)
  4. 优先级队列结构，就是堆结构

  • heapInsert 操作 ：O(log(N-1))
    建立大根堆复杂度：log1+log2+…+log(N-1) ->O(N)

  • heapify 操作：
    堆排序经历N次heapify：log1+log2+…+logN -> O(N*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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Code_03_HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
  • 堆排序的时间复杂度：O(N*logN)
  • 空间复杂度：O(1)

排序算法的稳定性汇总

  • O(n^2)
  1. 冒泡排序 可以实现成稳定的 遇到相等的不交换
  2. 插入排序 可以实现成稳定的 遇到相等的不往前交换
  3. 选择排序 不可以实现成稳定的 555503
  • O(nlogn)
  1. 归并排序 可以实现成稳定的 merge过程中先copy左边的
  2. 快速排序 不可以实现成稳定的 partition过程不能实现稳定性
  3. 堆排序 不可以实现成稳定的 44455 仅仅建立大根堆的过程就不能维持稳定性

有关排序问题的补充

  1. 归并排序的额外空间复杂度可以变成O(1)，但非常难，可以搜“归并排序 内部缓存法”
  2. 快排可以做到稳定性，但非常难，可以搜“01 stable sort”
  3. 有一道搞人题目，奇数放在数组左边，偶数放在数组右边，还要求维持原始的相对次序不变，O(N)时间复杂度，O(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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package basic_class_01;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Code_09_Comparator {
    public static class Student {
        public String name;
        public int id;
        public int age;

        public Student(String name, int id, int age) {
            this.name = name;
            this.id = id;
            this.age = age;
        }
    }

    public static class IdAscendingComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            //返回负数，第一个排前面，返回正数，第二个排前面，返回0，不变
            return o1.id - o2.id;
        }
    }

    public static class IdDescendingComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            //返回负数，第一个排前面，返回正数，第二个排前面，返回0，不变
            return o2.id - o1.id;
        }
    }

    public static class AgeAscendingComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.age - o2.age;
        }
    }

    public static class AgeDescendingComparator implements Comparator<Student> {
        @Override
        public int compare(Student o1, Student o2) {
            return o2.age - o1.age;
        }
    }

    public static void printStudents(Student[] students) {
        for (Student student : students) {
            System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
        }
        System.out.println("=============================");
    }

    public static void main(String[] args) {
        Student student1 = new Student("A", 1, 23);
        Student student2 = new Student("B", 2, 21);
        Student student3 = new Student("C", 3, 22);

        Student[] students = new Student[]{student1, student2, student3};
        printStudents(students);

        Arrays.sort(students, new IdAscendingComparator());
        printStudents(students);

        Arrays.sort(students, new IdDescendingComparator());
        printStudents(students);

        Arrays.sort(students, new AgeAscendingComparator());
        printStudents(students);

        Arrays.sort(students, new AgeDescendingComparator());
        printStudents(students);

        // 优先级队列——堆
        PriorityQueue<Student> heap = new PriorityQueue<>(new IdAscendingComparator());

        heap.add(student3);
        heap.add(student2);
        heap.add(student1);

        while (!heap.isEmpty()) {
            Student student = heap.poll();
            System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
        }

        //TreeMap() 红黑树
    }
}

桶排序、计数排序、基数排序

  1. 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不常用
  2. 时间复杂度O(N),额外空间复杂度O(N)
  3. 稳定的排序

桶排序是一个大的逻辑概念，计数排序和基数排序是桶排序的一种实现。

image-20200923202829478

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
package basic_class_01;
import java.util.Arrays;

public class Code_11_MaxGap {
    public static int maxGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int len = nums.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (min == max) {
            return 0;
        }
        boolean[] hasNum = new boolean[len + 1];
        int[] maxs = new int[len + 1];
        int[] mins = new int[len + 1];
        int bid = 0;
        for (int i = 0; i < len; i++) {
            bid = bucket(nums[i], len, min, max);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }
        int res = 0;
        int lastMax = maxs[0];
        for (int i = 1; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }

    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }
}

工程中的综合排序算法

先判断数据类型，基础类型->快排, 定义类型->比较器,归并排序；
数组长度很短（小于60）-> 不管什么类型都用插入排序，因为插入排序常数项很低；
归并或快排过程中，L part和R part 长度一旦小于60，插入排序；
基础数据类型不需要考虑稳定性，相同值无差异，所以选择快排；
而定义类型需要考虑稳定性。