算法初级面试题02——荷兰国旗问题、随机快速排序、堆排序、桶排序、相邻两数的最大差值问题、工程中的综合排序算法面试题

2018/11/12 09:57
阅读数 28

主要讨论:荷兰国旗问题、随机快速排序、堆排序、稳定性、比较器、桶排序、相邻两数的最大差值问题和简单介绍工程中的综合排序算法

 

题目一

给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边,大于num的数放在数组的右边。

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

参考下面的代码即可


问题二(荷兰国旗问题)

给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。

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

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 };
    }

    // for test
    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)

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(1)


堆结构非常重要


1,堆结构的heapInsert与heapify

2,堆结构的增大和减少

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);
        }
        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);
            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;
    }

 

题目四

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

冒泡、插入、归并稳定。

选择、快速、堆排序不稳定。

 

稳定性的含义?

值相等的情况下,相对次序得到保持。

 

为什么要稳定性?

由现实的例子决定,例如默认序列是按照身高排序的,再按照年龄排序的时候,希望可以保留原始身高的信息,再进行年龄排序。

 

题目五

有关排序问题的补充:

1,归并排序的额外空间复杂度可以变成O(1),但是非常难,不需要掌握,可以搜“归并排序 内部缓存法”

2,快速排序可以做到稳定性问题,但是非常难,不需要掌握,可以搜“01 stable sort”

3,有一道题目,是奇数放在数组左边,偶数放在数组右边,还要求原始的相对次序不变,碰到这个问题,可以怼面试官。面试官非良人。


题目六

认识比较器的使用

 1 public class Code_09_Comparator {
 2 
 3     public static class Student {
 4         public String name;
 5         public int id;
 6         public int age;
 7 
 8         public Student(String name, int id, int age) {
 9             this.name = name;
10             this.id = id;
11             this.age = age;
12         }
13     }
14 
15     public static class IdAscendingComparator implements Comparator<Student> {
16 
17         @Override
18         public int compare(Student o1, Student o2) {
19             return o1.id - o2.id;
20         }
21 
22     }
23 
24     public static class IdDescendingComparator implements Comparator<Student> {
25 
26         @Override
27         public int compare(Student o1, Student o2) {
28             return o2.id - o1.id;
29         }
30 
31     }
32 
33     public static class AgeAscendingComparator implements Comparator<Student> {
34 
35         @Override
36         public int compare(Student o1, Student o2) {
37             return o1.age - o2.age;
38         }
39 
40     }
41 
42     public static class AgeDescendingComparator implements Comparator<Student> {
43 
44         @Override
45         public int compare(Student o1, Student o2) {
46             return o2.age - o1.age;
47         }
48 
49     }
50 
51     public static void printStudents(Student[] students) {
52         for (Student student : students) {
53             System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
54         }
55         System.out.println("===========================");
56     }
57 
58     public static void main(String[] args) {
59         Student student1 = new Student("A", 1, 23);
60         Student student2 = new Student("B", 2, 21);
61         Student student3 = new Student("C", 3, 22);
62 
63         Student[] students = new Student[] { student3, student2, student1 };
64         printStudents(students);
65 
66         Arrays.sort(students, new IdAscendingComparator());
67         printStudents(students);
68 
69         Arrays.sort(students, new IdDescendingComparator());
70         printStudents(students);
71 
72         Arrays.sort(students, new AgeAscendingComparator());
73         printStudents(students);
74 
75         Arrays.sort(students, new AgeDescendingComparator());
76         printStudents(students);
77 
78     }
79 
80 }

 

题目七

桶排序、计数排序、基数排序的介绍

1,非基于比较的排序,与被排序的样本的实际数据状况很有关系,所以实际中并不经常使用

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

3,稳定的排序

public static void bucketSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int[] bucket = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

 

 

题目八

补充问题

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(N),且要求不能用非基于比较的排序。

 

解题思路:

1、准备N+1个桶,遍历数组找到最小最大值

2、Min放在第一个桶,max放在最大的桶,然后把最小到最大的这个范围等分为N+1份

 

3、那么两边放入最大和最小,必然中间会有一个空桶。桶内部的差值肯定没有桶范围的大。

 

4、所以流程为:N个数准备N+1个桶,0~N,当一个数进入桶,每个桶只记录出现的最小值和最大值,还有一个bool记录这个桶有没有进入过数。

5、遍历完成后,计算费控桶直接的差值,用min和max计算,如果是空桶就跳过。

6、设置一个空桶的原因是,用于否定最大差值一定不来自一个桶内部,因为有空桶的存在,那空桶两侧的非空桶差值,肯定大于或者等于任意桶内容最大和最小值的差值。

 

7、上面的式子就是右边先计算出,每个桶放多少个数,再把num-min为分子,可以看当前数占用在哪个位置上。例如有10个数,最大最小范围为1~100那就是说10/100=1/10,当前数要在放以10为分母的中,去计算他该去哪个桶。

 

题目九

介绍一下工程中的综合排序算法

少于60个数的直接用插入排序。(前期用递归分一半一半的,变小了再按照其他排序方法来排序,综合利用各排序的优点)

基础类型用快速排序,因为基础类型相同分数无差异。

自定义类型用归并排序,因为关乎多类数据,需要保持原始排序。

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部