02-荷兰国旗，堆排序，各种排序-白红宇

02-荷兰国旗，堆排序，各种排序

阅读量：5020 次

发布时间：2019-06-12

本文共 12976 字，大约阅读时间需要 43 分钟。

1、荷兰国旗

1、数组分开

给定一个数组arr，和一个数num，请把小于等于num的数放在数

组的左边，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

2、荷兰国旗

流程：

= num ，cur跳下一个

<num，cur交换小于区域的下一个，

less++，cur++

>num，cur交换大于区域的上一个

　　 more--，cur不变

cur==more 停止

java版本

package basic_class_01;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 {   // == num                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;    }        // for test    public static int[] generateArray() {        int[] arr = new int[10];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) (Math.random() * 3);        }        return arr;    }    // for test    public static void printArray(int[] arr) {        if (arr == null) {            return;        }        for (int i = 0; i < arr.length; i++) {            System.out.print(arr[i] + " ");        }        System.out.println();    }    public static void main(String[] args) {        int[] test = generateArray();        printArray(test);        int[] res = partition(test, 0, test.length - 1, 1);        printArray(test);        System.out.println(res[0]);        System.out.println(res[1]);    }}

python版本

2、快速排序

1、经典快排

每次搞定一个x

2、荷兰问题改进经典快排

每次搞定一片X

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 };   // 返回 ==num 的左右边界    }    public static void swap(int[] arr, int i, int j) {        int tmp = arr[i];        arr[i] = arr[j];        arr[j] = tmp;    }

3、经典快排的问题

1、每次搞定一个数

2、与数据状况有关系

4、随机快排

时间复杂度O(N*logN)，额外空间复杂度O(logN)

每次随机选择一个数

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 };   // 返回 ==num 的左右边界    }    public static void swap(int[] arr, int i, int j) {        int tmp = arr[i];        arr[i] = arr[j];        arr[j] = tmp;    }

5、随机快排的优势

1、常数项只while一次

2、空间复杂度 O(logN) 保存划分点

3、堆排序 :完全二叉树

1、满二叉树、完全二叉树

2、完全二叉树与数组

3、大根堆与小根堆

大根堆：任何一个子树的最大值都是子树的头部

小根堆：任何一个子树的最小值都是子树的头部

4、建立大根堆算法

1、流程：

与父节点的数比较，父（i-1）/2

if cur比父大，则交换，cur来到父位置，继续比较

else 不交换

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

2、建立一个大根堆的复杂度

每次一调整

当有N个节点已经存在，进来一个数N+1,需要调整O(logN)次

总共调整的复杂度

5、heapInsert 与 heapify

heapInsert：较大的值，往上升的操作

heapify：较小的值，往下沉的操作，与左右孩子最大的交换

max(2*i+1, 2*i+2)

public static void heapify(int[] arr, int index, int size) {        int left = index * 2 + 1;        while (left < size) {   // 不越界            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  // 左右孩子最大值 与 我比较            largest = arr[largest] > arr[index] ? largest : index;            if (largest == index) {                break;            }            swap(arr, largest, index);   // lagest ！= index            index = largest;            left = index * 2 + 1;        }    }

6、寻找流中的中位数

1、笨办法

temp = [] 收集数据O(1)，每次求值，都要排序O(logN)

2、堆

弹出堆顶

BAT 起码5个堆的问题

优先级队列

堆什么时候都不能忘了

被火车撞了都不能忘

所有的贪心问题

非常重要，一定要会

堆头部与最后一个数交换，

heapsize -1，

调整堆

堆排序的细节和复杂度分析

时间复杂度O(N*logN)，额外空间复杂度O(1)

堆结构非常重要

1，堆结构的heapInsert与heapify

2，堆结构的增大和减少heapSize

3，如果只是建立堆的过程，时间复杂度为O(N)

4，优先级队列结构，就是堆结构

public static void heapSort(int[] arr) {        if (arr == null || arr.length < 2) {            return;        }        for (int i = 0; i < arr.length; i++) {            heapInsert(arr, i);   // 0~i          }        int size = arr.length;        swap(arr, 0, --size);        while (size > 0) {            heapify(arr, 0, size);            swap(arr, 0, --size);        }    }    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 size) {        int left = index * 2 + 1;        while (left < size) {   // 不越界            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;  // 左右孩子最大值 与 我比较            largest = arr[largest] > arr[index] ? largest : index;            if (largest == index) {                break;            }            swap(arr, largest, index);   // lagest ！= 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;    }

3、排序算法的稳定性及其汇总

相同的值，相对顺序是否被打乱

为什么要追求稳定性？

业务过程中，保留原始数据的次序

先height排序，在age排序，需要保持height的原始次序。稳定性

4、工程中的综合排序算法

1、首先看数据类型

从稳定性出发的

基础类型：int,double,char,float,string

选择快排序

自己定义的类型 stu:name:age

选择归并排序

2、在看，数组长度

数组长度较短，使用插入排序，飞快

样本量<60时，常数项很低，直接使用，插排

sort(Left,Right)

if (len<60) {插入排序}

有关排序问题的补充：

1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不

需要掌握，可以搜“归并排序内部缓存法”

2，快速排序可以做到稳定性问题，但是非常难，不需要掌握，

可以搜“01 stable sort”

3，有一道题目，是奇数放在数组左边，偶数放在数组右边，还

要求原始的相对次序不变，碰到这个问题，可以怼面试官。面试

官非良人。

diss面试

Question：

维持相对次序

快排一般情况实现不了，但是01 stable sort可以做到稳定性

01标准

奇偶标准，一类的

“ 01 stable sort”

01稳定排序

荷兰国旗做不到稳定性，只能分层

5、认识比较器

package basic_class_01;import java.util.Arrays;import java.util.Comparator;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
     
       {        @Override        public int compare(Student o1, Student o2) {            return o1.id - o2.id;        }    }    public static class IdDescendingComparator implements Comparator
      
        {        @Override        public int compare(Student o1, Student o2) {            return o2.id - o1.id;        }    }    public static class AgeAscendingComparator implements Comparator
       
         {        @Override        public int compare(Student o1, Student o2) {            return o1.age - o2.age;        }    }    public static class AgeDescendingComparator implements Comparator
        
          {        @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[] { student3, student2, student1 };        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);    }}

1、自定义比较器（C语言重载大于号，运算符）

if (o1.id>o2.id)

return -1

elif o1.id<o2.id

return 1

else

return 0

等价于

id升序排列

return o1.id-o2.id

2、堆==优先级队列

堆也可以用比较器

建堆方法<自定义比较器>

3、TreeMap<> 红黑树

基于比较的排序是重点

lambda表达式可以实现

6、桶排序，计数排序，基数排序

不基于比较的排序

桶 ---- 容器

桶排序是基础

计数排序，基数排序是桶排序的具体实现。

1，非基于比较的排序，与被排序的样本的实际数据状况很有关系，所

以实际中并不经常使用

2，时间复杂度O(N)，额外空间复杂度O(N)

3，稳定的排序

数组的词频---计数排序

必考问题：补充问题

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时

间复杂度O(N)，且要求不能用非基于比较的排序。

借用了桶排序的概念

等分为

0~99分成10份

鸽笼原理

中间必存在一个空桶

否定最大差值不来自同一个桶

max最大差值一定来自与两个桶

只存，

这个桶是否进来过数

这个桶的最小，最大值

当前桶的最小值min，与它前一个桶的最大max

最大差值一定在 max-min 差值中

空桶只是：否定最大差值不来自同一个桶的相邻数

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 min = Integer.MAX_VALUE;        int max = Integer.MIN_VALUE;                // 找到array的最小值，最大值        for (int i = 0; i < len; i++) {            min = Math.min(min, nums[i]);            max = Math.max(max, nums[i]);        }        if (min == max) {            return 0;        }                // 每个桶的 3个信息        boolean[] hasNum = new boolean[len + 1];          int[] maxs = new int[len + 1];        int[] mins = new int[len + 1];                int bid = 0;                // 当前数去哪个桶，桶的3个信息要更新        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];        int i = 1;                // 当前桶min与它前一个桶的max的差值，最大差值就在其中        for (; 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));    }    // for test    public static int comparator(int[] nums) {        if (nums == null || nums.length < 2) {            return 0;        }        Arrays.sort(nums);        int gap = Integer.MIN_VALUE;        for (int i = 1; i < nums.length; i++) {            gap = Math.max(nums[i] - nums[i - 1], gap);        }        return gap;    }    // for test    public static int[] generateRandomArray(int maxSize, int maxValue) {        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());        }        return arr;    }    // for test    public static int[] copyArray(int[] arr) {        if (arr == null) {            return null;        }        int[] res = new int[arr.length];        for (int i = 0; i < arr.length; i++) {            res[i] = arr[i];        }        return res;    }    // for test    public static void main(String[] args) {        int testTime = 500000;        int maxSize = 100;        int maxValue = 100;        boolean succeed = true;        for (int i = 0; i < testTime; i++) {            int[] arr1 = generateRandomArray(maxSize, maxValue);            int[] arr2 = copyArray(arr1);            if (maxGap(arr1) != comparator(arr2)) {                succeed = false;                break;            }        }        System.out.println(succeed ? "Nice!" : "Fucking fucked!");    }}