【恋上数据结构与算法二】(一)排序(Sorting)

排序方法

  1. 冒泡排序
  2. 选择排序
  3. 堆排序
  4. 插入排序
  5. 归并排序
  6. 快速排序
  7. 希尔排序
  8. 计数排序
  9. 基数排序
  10. 桶排序

初识排序

◼ 什么叫排序?
排序前:3,1,6,9,2,5,8,4,7
排序后:1,2,3,4,5,6,7,8,9(升序) 或者 9,8,7,6,5,4,3,2,1(降序)

◼ 排序的应用无处不在

10大排序算法

◼ 以上表格是基于数组进行排序的一般性结论
◼ 冒泡、选择、插入、归并、快速、希尔、堆排序，属于比较排序(Comparison Sorting)

一、冒泡排序(Bubble Sort)

◼ 冒泡排序也叫做起泡排序

◼ 执行流程(本课程统一以升序为例子)
1 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
✓ 执行完一轮后，最末尾那个元素就是最大的元素

2 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序

for (int end = array.length - 1; end > 0; end--) {
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);// 交换两个元素
        }
    }
}

/*
 * 返回值等于0，代表 array[i1] == array[i2]
 * 返回值小于0，代表 array[i1] < array[i2]
 * 返回值大于0，代表 array[i1] > array[i2]
 */
protected int cmp(int i1, int i2) {
    cmpCount++;
    return array[i1].compareTo(array[i2]);
}

protected void swap(int i1, int i2) {
    swapCount++;
    T tmp = array[i1];
    array[i1] = array[i2];
    array[i2] = tmp;
}

冒泡排序 – 优化1

◼ 如果序列已经完全有序，可以提前终止冒泡排序

for (int end = array.length - 1; end > 0; end--) {
    boolean sorted = true;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);
            sorted = false;
        }
    }
    if (sorted) break;// 如果是有序的，提前终止冒泡排序
}

冒泡排序 – 优化2

◼ 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数

◼最后1次交换的位置是 6

for (int end = array.length - 1; end > 0; end--) {
    int sortedIndex = 1;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(begin, begin - 1) < 0) {
            swap(begin, begin - 1);
            sortedIndex = begin;// 记录最后1次交换的位置
        }
    }
    end = sortedIndex;
}

◼ 最坏、平均时间复杂度:O(n2)
◼ 最好时间复杂度:O(n)
◼ 空间复杂度:O(1)

排序算法的稳定性(Stability)

◼ 如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法
排序前:5, 1, 3𝑎, 4, 7, 3𝑏
稳定的排序: 1, 3𝑎, 3𝑏, 4, 5, 7
不稳定的排序:1, 3𝑏, 3𝑎, 4, 5, 7

◼ 对自定义对象进行排序时，稳定性会影响最终的排序效果

◼ 冒泡排序属于稳定的排序算法
稍有不慎，稳定的排序算法也能被写成不稳定的排序算法，比如下面的冒泡排序代码是不稳定的

原地算法(In-place Algorithm)

◼ 何为原地算法?
不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
空间复杂度为 𝑂(1) 的都可以认为是原地算法

◼非原地算法，称为 Not-in-place 或者 Out-of-place

◼冒泡排序属于 In-place

二、选择排序(Selection Sort)

◼ 执行流程
1 从序列中找出最大的那个元素，然后与最末尾的元素交换位置
✓ 执行完一轮后，最末尾的那个元素就是最大的元素

2 忽略 1 中曾经找到的最大元素，重复执行步骤 1

for (int end = array.length - 1; end > 0; end--) {
    int max = 0;
    for (int begin = 1; begin <= end; begin++) {
        if (cmp(max, begin) < 0) {
            max = begin;
        }
    }
    swap(max, end);
}

◼思考
选择排序是否还有优化的空间?
✓ 使用堆来选择最大值

◼ 选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
◼ 最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于稳定排序

三、堆排序(Heap Sort)

◼ 堆排序可以认为是对选择排序的一种优化

◼ 执行流程
1 对序列进行原地建堆(heapify)
2 重复执行以下操作，直到堆的元素数量为 1
✓ 交换堆顶元素与尾元素
✓堆的元素数量减 1
✓对 0 位置进行 1 次 siftDown 操作

堆排序 – 实现

@Override
protected void sort() {
    // 原地建堆
    heapSize = array.length;
    for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
        siftDown(i);
    }
    
    while (heapSize > 1) {
        // 交换堆顶元素和尾部元素
        swap(0, --heapSize);

        // 对0位置进行siftDown（恢复堆的性质）
        siftDown(0);
    }
}

private void siftDown(int index) {
    T element = array[index];
    
    int half = heapSize >> 1;
    while (index < half) { // index必须是非叶子节点
        // 默认是左边跟父节点比
        int childIndex = (index << 1) + 1;
        T child = array[childIndex];
        
        int rightIndex = childIndex + 1;
        // 右子节点比左子节点大
        if (rightIndex < heapSize &&
                cmp(array[rightIndex], child) > 0) {
            child = array[childIndex = rightIndex];
        }
        
        // 大于等于子节点
        if (cmp(element, child) >= 0) break;
        
        array[index] = child;
        index = childIndex;
    }
    array[index] = element;
}

◼ 最好、最坏、平均时间复杂度:O(nlogn)，空间复杂度:O(1)，属于不稳定排序

四、插入排序(Insertion Sort)

◼ 插入排序非常类似于扑克牌的排序

◼ 执行流程
1 在执行过程中，插入排序会将序列分为2部分
✓ 头部是已经排好序的，尾部是待排序的

2 从头开始扫描每一个元素
✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

插入排序 – 实现

for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    while (cur > 0 && cmp(cur, cur - 1) < 0) {
        swap(cur, cur - 1);
        cur--;
    }
}

插入排序 – 逆序对(Inversion)

◼ 什么是逆序对?
数组 <2,3,8,6,1> 的逆序对为:<2,1> <3,1> <8,1> <8,6> <6,1>，共5个逆序对

◼ 插入排序的时间复杂度与逆序对的数量成正比关系
逆序对的数量越多，插入排序的时间复杂度越高

◼ 最坏、平均时间复杂度:O(n2)
◼ 最好时间复杂度:O(n)
◼ 空间复杂度:O(1)
◼ 属于稳定排序

◼ 当逆序对的数量极少时，插入排序的效率特别高
甚至速度比 O nlogn 级别的快速排序还要快

◼ 数据量不是特别大的时候，插入排序的效率也是非常好的

插入排序 – 优化

◼ 思路是将【交换】转为【挪动】
1 先将待插入的元素备份
2 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
3 将待插入元素放到最终的合适位置

for (int begin = 1; begin < array.length; begin++) {
    int cur = begin;
    T v = array[cur];
    while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
        array[cur] = array[cur - 1];
        cur--;
    }
    array[cur] = v;
}

二分搜索(Binary Search)

◼ 如何确定一个元素在数组中的位置?(假设数组里面全都是整数)
如果是无序数组，从第 0 个位置开始遍历搜索，平均时间复杂度:O(n)

如果是有序数组，可以使用二分搜索，最坏时间复杂度:O(logn)

二分搜索 – 思路

◼假设在 [begin, end) 范围内搜索某个元素 v，mid = (begin + end) / 2
◼如果 v < m，去 [begin, mid) 范围内二分搜索
◼如果 v > m，去 [mid + 1, end) 范围内二分搜索
◼如果 v == m，直接返回 mid

二分搜索 – 实例

◼搜索 10

◼搜索 3

二分搜索 – 实现

/**
 * 查找v在有序数组array中的位置
 */
public static int indexOf(int[] array, int v) {
    if (array == null || array.length == 0) return -1;
    int begin = 0;
    int end = array.length;
    while (begin < end) {
        int mid = (begin + end) >> 1;// 右移1，相当于除以2
        if (v < array[mid]) {
            end = mid;
        } else if (v > array[mid]) {
            begin = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

◼思考
如果存在多个重复的值，返回的是哪一个?
✓ 不确定

插入排序 – 二分搜索优化

◼在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素 v 插入

◼要求二分搜索返回的插入位置:第1个大于 v 的元素位置
如果 v 是 5，返回 2
如果 v 是 1，返回 0
如果 v 是 15，返回 7
如果 v 是 8，返回 5

插入排序 – 二分搜索优化 – 思路

◼假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
◼如果 v < m，去 [begin, mid) 范围内二分搜索
◼如果 v ≥ m，去 [mid + 1, end) 范围内二分搜索

插入排序 – 二分搜索优化 – 实例

◼搜索 5

◼搜索 1

◼搜索 15

◼搜索 8

插入排序 – 二分搜索优化 – 实现
@Override
protected void sort() {
    for (int begin = 1; begin < array.length; begin++) {
        insert(begin, search(begin));
    }
}

/**
 * 将source位置的元素插入到dest位置
 * @param source
 * @param dest
 */
private void insert(int source, int dest) {
    T v = array[source];
    for (int i = source; i > dest; i--) {
        array[i] = array[i - 1];
    }
    array[dest] = v;
}

/**
 * 利用二分搜索找到 index 位置元素的待插入位置
 * 已经排好序数组的区间范围是 [0, index)
 * @param index
 * @return
 */
private int search(int index) {
    int begin = 0;
    int end = index;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (cmp(array[index], array[mid]) < 0) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }
    return begin;
}

◼需要注意的是，使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n2)

五、归并排序(Merge Sort)

◼1945年由约翰·冯·诺伊曼(John von Neumann)首次提出

◼ 执行流程
1 不断地将当前序列平均分割成2个子序列
✓ 直到不能再分割(序列中只剩1个元素)
2 不断地将2个子序列合并成一个有序序列
✓ 直到最终只剩下1个有序序列

归并排序 – divide实现

// 准备一段临时的数组空间，在merge操作中使用
leftArray = (T[]) new Comparable[array.length >> 1];
sort(0, array.length);

/**
 * 对 [begin, end) 范围的数据进行归并排序
 */
private void sort(int begin, int end) {
    if (end - begin < 2) return;
    
    int mid = (begin + end) >> 1;
    sort(begin, mid);
    sort(mid, end);
    merge(begin, mid, end);
}

归并排序 – merge

归并排序 – merge细节

◼需要 merge 的 2 组序列存在于同一个数组中，并且是挨在一起的

◼为了更好地完成 merge 操作，最好将其中 1 组序列备份出来，比如 [begin, mid)

归并排序 – merge
归并排序 – merge – 左边先结束
归并排序 – merge – 右边先结束
归并排序 – merge实现
/**
 * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
 */
private void merge(int begin, int mid, int end) {
    int li = 0, le = mid - begin;// 左边数组(基于leftArray)
    int ri = mid, re = end;// 右边数组(基于array)
    int ai = begin;// array的索引
    
    // 备份左边数组
    for (int i = li; i < le; i++) {// 拷贝左边数组到leftArray
        leftArray[i] = array[begin + I];
    }
    
    // 如果左边还没有结束
    while (li < le) {
        if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
            array[ai++] = array[ri++];// 拷贝右边数组到array
        } else {
            array[ai++] = leftArray[li++];// 拷贝左边数组到array
        }
    }// cmp位置改为 <= 会失去稳定性
}
归并排序 – 复杂度分析

◼ 归并排序花费的时间
Tn =2∗Tn/2 +O(n)
T1 =O(1)
T n /n=T n/2 /(n/2)+O(1)

◼令Sn =Tn/n
S1 =O(1)
S n =S n/2 +O(1)=S n/4 +O(2)=S n/8 +O(3)=S n/2k +O k =S 1 +O(logn)=O(logn)
Tn =n∗Sn =O(nlogn)

◼由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是 O(nlogn) ，属于稳定排序

◼从代码中不难看出:归并排序的空间复杂度是On/2+logn =O(n)
n/2 用于临时存放左侧数组，logn 是因为递归调用

常见的递推式与复杂度

作业

◼ 合并两个有序数组
https://leetcode-cn.com/problems/merge-sorted-array/
◼ 合并两个有序链表
https://leetcode-cn.com/problems/merge-two-sorted-lists/comments/
◼ 合并K个有序链表
https://leetcode-cn.com/problems/merge-k-sorted-lists/
◼ 解题教程
https://ke.qq.com/course/436549

六、快速排序(Quick Sort)

◼1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare，缩写为C. A. R. Hoare)提出
昵称为东尼·霍尔(Tony Hoare)

快速排序 – 执行流程
1.从序列中选择一个轴点元素(pivot)
✓假设每次选择 0 位置的元素为轴点元素

2.利用 pivot 将序列分割成 2 个子序列
✓将小于 pivot 的元素放在pivot前面(左侧)
✓将大于 pivot 的元素放在pivot后面(右侧)
✓ 等于pivot的元素放哪边都可以

3.对子序列进行 1 2 操作
✓ 直到不能再分割(子序列中只剩下1个元素)

◼ 快速排序的本质
逐渐将每一个元素都转换成轴点元素

快速排序 – 轴点构造

快速排序 – 时间复杂度

◼ 在轴点左右元素数量比较均匀的情况下，同时也是最好的情况
T n =2∗T n/2 +O n =O(nlogn)

◼ 如果轴点左右元素数量极度不均匀，最坏情况
Tn =Tn−1 +On =O(n2)

◼ 为了降低最坏情况的出现概率，一般采取的做法是
随机选择轴点元素

◼ 最好、平均时间复杂度:O(nlogn)
◼ 最坏时间复杂度:O(n2)
◼ 由于递归调用的缘故，空间复杂度:O(logn)
◼ 属于不稳定排序

快速排序 – 实现

/**
 * 对 [begin, end) 范围的元素进行快速排序
 * @param begin
 * @param end
 */
private void sort(int begin, int end) {
    // 至少要有2个元素
    if (end - begin < 2) return;
    
    // 确定轴点位置 O(n)
    int mid = pivotIndex(begin, end);
    // 对子序列进行快速排序
    sort(begin, mid);
    sort(mid + 1, end);
}

/**
 * 构造出 [begin, end) 范围的轴点元素
 * @return 轴点元素的最终位置
 */
private int pivotIndex(int begin, int end) {
    // 随机选择一个元素跟begin位置进行交换
    swap(begin, begin + (int)(Math.random() * (end - begin)));
    
    // 备份begin位置的元素
    T pivot = array[begin];
    // end指向最后一个元素
    end--;
    
    while (begin < end) {
        while (begin < end) {
            if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                end--;
            } else { // 右边元素 <= 轴点元素
                array[begin++] = array[end];
                break;
            }
        }
        while (begin < end) {
            if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                begin++;
            } else { // 左边元素 >= 轴点元素
                array[end--] = array[begin];
                break;
            }
        }
    }
    
    // 将轴点元素放入最终的位置
    array[begin] = pivot;
    // 返回轴点元素的位置
    return begin;
}

快速排序 – 与轴点相等的元素

◼如果序列中的所有元素都与轴点元素相等，利用目前的算法实现，轴点元素可以将序列分割成 2 个均匀的子序列

◼思考:cmp 位置的判断分别改为 ≤、≥ 会起到什么效果?

◼ 轴点元素分割出来的子序列极度不均匀
导致出现最坏时间复杂度 O(n2)

七、希尔排序(Shell Sort)

◼1959年由唐纳德·希尔(Donald Shell)提出

◼希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
𝑚 从某个整数逐渐减为1
当 𝑚 为1时，整个序列将完全有序

◼因此，希尔排序也被称为递减增量排序(Diminishing Increment Sort)

◼矩阵的列数取决于步长序列(step sequence)
✓ 比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序
✓ 不同的步长序列，执行效率也不同

希尔排序 – 实例

◼希尔本人给出的步长序列是 𝑛/2𝑘，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}

◼ 分成8列进行排序

◼ 分成4列进行排序

◼ 分成2列进行排序

◼ 分成1列进行排序

◼不难看出来，从8列 变为 1列的过程中，逆序对的数量在逐渐减少
因此希尔排序底层一般使用插入排序对每一列进行排序，也很多资料认为希尔排序是插入排序的改进版

◼假设有11个元素，步长序列是{1, 2, 5}

◼假设元素在第 col 列、第 row 行，步长(总列数)是 step
那么这个元素在数组中的索引是 col + row * step
比如 9 在排序前是第 2 列、第 0 行，那么它排序前的索引是 2 + 0 * 5 = 2
比如 4 在排序前是第 2 列、第 1 行，那么它排序前的索引是 2 + 1 * 5 = 7

希尔排序 – 实现
List<Integer> stepSequence = sedgewickStepSequence();
for (Integer step : stepSequence) {
    sort(step);
}

/**
 * 分成step列进行排序
 */
private void sort(int step) {
    // col : 第几列，column的简称
    for (int col = 0; col < step; col++) { // 对第col列进行排序
        // col、col+step、col+2*step、col+3*step
        for (int begin = col + step; begin < array.length; begin += step) {
            int cur = begin;
            while (cur > col && cmp(cur, cur - step) < 0) {
                swap(cur, cur - step);
                cur -= step;
            }
        }
    }
}

◼最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
◼ 空间复杂度为O(1)，属于不稳定排序

希尔排序 – 步长序列

◼希尔本人给出的步长序列，最坏情况时间复杂度是 O(n2)

private List<Integer> shellStepSequence() {
    List<Integer> stepSequence = new ArrayList<>();
    int step = array.length;
    while ((step >>= 1) > 0) {
        stepSequence.add(step);
    }
    return stepSequence;
}

◼目前已知的最好的步长序列，最坏情况时间复杂度是 O(n4/3) ，1986年由Robert Sedgewick提出

private List<Integer> sedgewickStepSequence() {
    List<Integer> stepSequence = new LinkedList<>();
    int k = 0, step = 0;
    while (true) {
        if (k % 2 == 0) {
            int pow = (int) Math.pow(2, k >> 1);
            step = 1 + 9 * (pow * pow - pow);
        } else {
            int pow1 = (int) Math.pow(2, (k - 1) >> 1);
            int pow2 = (int) Math.pow(2, (k + 1) >> 1);
            step = 1 + 8 * pow1 * pow2 - 6 * pow2;
        }
        if (step >= array.length) break;
        stepSequence.add(0, step);
        k++;
    }
    return stepSequence;
}

八、计数排序(Counting Sort)

◼ 之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序
平均时间复杂度目前最低是 O(nlogn)

◼ 计数排序、桶排序、基数排序，都不是基于比较的排序
它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn)更低

◼计数排序于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序

◼ 计数排序的核心思想
统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

计数排序 – 最简单的实现

◼ 这个版本的实现存在以下问题
无法对负整数进行排序
极其浪费内存空间
是个不稳定的排序
......

int max = array[0];// 找出最大值
for (int i = 1; i < array.length; i++) {
    if (array[i] > max) {
        max = array[i];
    }
} // O(n)

// 开辟内存空间，存储每个整数出现的次数
int[] counts = new int[1 + max];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
    counts[array[i]]++;
} // O(n)

// 根据整数的出现次数，对整数进行排序
int index = 0;
for (int i = 0; i < counts.length; i++) {
    while (counts[i]-- > 0) {
        array[index++] = i;
    }
} // O(n)

计数排序 – 改进思路

◼假设array中的最小值是 min
◼array中的元素 k 对应的 counts 索引是 k – min
◼array中的元素 k 在有序序列中的索引
counts[k – min] – p
p 代表着是倒数第几个 k

◼比如元素 8 在有序序列中的索引
counts[8 – 3] – 1，结果为 7

◼倒数第 1 个元素 7 在有序序列中的索引
counts[7 – 3] – 1，结果为 6

◼倒数第 2 个元素 7 在有序序列中的索引
counts[7 – 3] – 2，结果为 5

计数排序 – 改进实现

protected void sort() {
    int max = array[0];// 最大值
    int min = array[0];// 最小值
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    
    // 开辟内存空间，存储次数
    int[] counts = new int[max - min + 1];// 用于计数
    // 统计每个整数出现的次数
    for (int i = 0; i < array.length; i++) {
        counts[array[i] - min]++;
    }
    // 累加次数
    for (int i = 1; i < counts.length; i++) {
        counts[i] += counts[i - 1];
    }
    
    // 从后往前遍历元素，将它放到有序数组中的合适位置
    int[] newArray = new int[array.length];// 用于存放排好序的数据
    for (int i = array.length - 1; i >= 0; i--) {
        newArray[--counts[array[i] - min]] = array[i];
    }
    
    // 将有序数组赋值到array
    for (int i = 0; i < newArray.length; i++) {
        array[i] = newArray[i];
    }
}

◼ 最好、最坏、平均时间复杂度:O(n + k)
◼ 空间复杂度:O(n + k)

◼k 是整数的取值范围

◼ 属于稳定排序

计数排序 – 对自定义对象进行排序

◼ 如果自定义对象可以提供用以排序的整数类型，依然可以使用计数排序

private static class Person {
    int age;
    String name;
    Person(int age, String name) {
        this.age = age;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Person [age=" + age
                + ", name=" + name + "]";
    }
}

Person[] persons = new Person[] {
        new Person(20, "A"),
        new Person(-13, "B"),
        new Person(17, "C"),
        new Person(12, "D"),
        new Person(-13, "E"),
        new Person(20, "F")
};

// 找出最值
int max = persons[0].age;
int min = persons[0].age;
for (int i = 1; i < persons.length; i++) {
    if (persons[i].age > max) {
        max = persons[i].age;
    }
    if (persons[i].age < min) {
        min = persons[i].age;
    }
}

// 开辟内存空间，存储次数
int[] counts = new int[max - min + 1];
// 统计每个整数出现的次数
for (int i = 0; i < persons.length; i++) {
    counts[persons[i].age - min]++;
}
// 累加次数
for (int i = 1; i < counts.length; i++) {
    counts[i] += counts[i - 1];
}

// 从后往前遍历元素，将它放到有序数组中的合适位置
Person[] newArray = new Person[persons.length];// 用于存放排好序的数据
for (int i = persons.length - 1; i >= 0; i--) {
    newArray[--counts[persons[i].age - min]] = persons[i];
}

// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
    persons[i] = newArray[i];
}
// 打印
for (int i = 0; i < persons.length; i++) {
    System.out.println(persons[i]);
}

◼ 排序之后的结果
1 Person [age=-13, name=B]
2 Person [age=-13, name=E]
3 Person [age=12, name=D]
4 Person [age=17, name=C]
5 Person [age=20, name=A]
6 Person [age=20, name=F]

九、基数排序(Radix Sort)

◼ 基数排序非常适合用于整数排序(尤其是非负整数)，因此本课程只演示对非负整数进行基数排序
◼ 执行流程:依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位)

◼ 个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序

◼ 思考:如果先对高位排序，再对低位排序，是否可行?（不行）

基数排序 – 实现

◼ 最好、最坏、平均时间复杂度:O(d ∗ (n + k)) ，d 是最大值的位数，k 是进制。属于稳定排序
◼ 空间复杂度:O(n + k)，k 是进制

基数排序 – 另一种思路

基数排序 – 另一种思路的实现

◼ 空间复杂度是 O(kn + k) ，时间复杂度是 O(dn)
◼d 是最大值的位数，k 是进制

十、桶排序(Bucket Sort)

◼ 执行流程
1 创建一定数量的桶(比如用数组、链表作为桶)
2 按照一定的规则(不同类型的数据，规则不同)，将序列中的元素均匀分配到对应的桶 3 分别对每个桶进行单独排序
4 将所有非空桶的元素合并成有序序列

◼ 元素在桶中的索引
元素值 * 元素数量

桶排序 – 实现

◼ 空间复杂度:O(n + m)，m 是桶的数量
◼时间复杂度:O(n) +m∗O(n /m∗logn/m = O(n+n∗logn/m) =O(n+n∗logn−n∗logm)
因此为 O(n+k )，k 为 n∗logn−n∗logm
属于稳定排序

史上“最强”排序 – 休眠排序

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,384评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,845评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,148评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,640评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,731评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,712评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,703评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,473评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,915评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,227评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,384评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,063评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,706评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,302评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,531评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,321评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,248评论 2赞 352

推荐阅读更多精彩内容