桶排序以及排序内容大总结

堆

1.堆结构就是用数组实现的完全二叉树结构
2.完全二叉树中如果每颗子树的最大值都在顶部就是大根堆
3.完全二叉树中如果每颗子树的最小值都在顶部就是小根堆
4.堆结构的heapInsert与heapify操作
5.堆结构的增大与减少
6.优先级队列结构，就是堆结构

heapInsert操作

时间复杂度O(logN)
新添一个数，使得一个堆结构成为大根堆

//某个数在index位置上，往上继续移动
    void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
1
2
3
4
5
6
7

void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
1
2
3
4
5

heapify操作

时间复杂度O(logN)
去掉大根堆的最大值后，使得堆结构仍然保持大根堆

 //某个数在index位置，能否往下移
    void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;//左孩子的下标
        while (left < heapSize) {//还有子节点的时候
            //两个孩子中谁的值大，把下标给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //父和孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

堆排序

时间复杂度O(NlogN)

void heapSort(int[] arr) {
        if (arr == null && arr.length < 2) {
            return;
        }
        /**
        *是整个数组成为一个大根堆
        */
        for (int i = arr.length - ; i >= 0 ; i--) {
            heapify(arr, i,arr.length);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);//O(logN)
            swap(arr, 0, --heapSize);//O(1)
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

堆排序扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相当于数组来说比较小。请选择一个合适的排序算法针对这个数组进行排序。

思路：
可以采用小根堆结构
将数组中的每k位数构建成小根堆结构，然后将根节点位置上的数进行弹出，k的位置向后移，依次进行，直到超过数组长度

void sortedArrDistanceLessK(int[] arr,int k){
//默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for (;index <= Math.min(arr.length,k); index++){
            heap.add(arr[index]);
        }
        int i = 0;
        for (;index < arr.length;i++,index++){
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        while (!heap.isEmpty()){
            arr[i++] = heap.poll();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

比较器的使用

1.比较器的实质就是重载比较符
2.比较器可以很好地应用在特殊标准的排序上
3.比较器可以很好地应用在根据特殊标准排序的结构上

当两个参数进行比较时
如果返回的是负数，认为第一个参数应该排在前面
如果返回的是正数，认为第二个参数应该排在前面
如果返回的是0，认为谁在前面都可以

桶排序

计数排序

基数排序

 void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        //有多少个数准备多少个辅助空间
        int[] bucket = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) {//有多少为就进出几次
            int[] count = new int[radix];
            //10个空间
            //count[0]当前位(d位)是0的数字有多少个
            //count[1]当前位(d位)是(0和1)的数字有多少个
            //count[2]当前位(d位)是(0、1、2)的数字有多少个
            //count[i]当前位(d位)是(0~i)的数字有多少个
            for (i = L; i <= R; i++) {//count[0...9]
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
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

分析：
1.桶排序思想下的排序都是不基于比较的排序
2.时间复杂度为O(N)，额外空间负载度O(M)
3.应用范围有限，需要样本的数据状况满足桶的划分

排序内容的总结