简介
排序算法是基础，其思想在各个框架，源码中的底层都有体现，本文将介绍一些有特色的排序算法；如：快排、归并、插入、堆、计数、桶排序算法；
1.快速排序
快排，在面试中真的是经常被问到；
1.1 思路分析：快速排序的思路
1.2 代码实现
import java.util.Arrays;
import java.util.Random;
/**
* @auther:lgb
* @Date: 2021/5/9
*/
public class QuickSort {
public static void main(String[] args) {
int length = 100;
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++) {
arr[i] = random.nextInt(100);
}
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
private static void quickSort(int[] arr, int left, int right) {
int i, j, temp;
if (left > right) {
return;
}
//左边哨兵的索引
i = left;
//右边哨兵的索引
j = right;
//以最左边的作为基准位
temp = arr[left];
while (i < j) {
//一定要先从右边开始
//从右向左找一个比基准位小的数
//当右边的位子所在的数大于等于基准位数时，不符合要求，继续找j--;
//找到的时候退出循环
while (temp <= arr[j] && i < j) {
j--;
}
//在开始从左边往右递增
while (temp >= arr[i] && i < j) {
i++;
}
//找到i和j了，如果i<j则交换
if (i < j) {
int z;
z = arr[i];
arr[i] = arr[j];
arr[j] = z;
}
}
//此时跳出了while循环，说明i=j，它们在同一位置
//此时，需要将temp和arr[i]进行交换
arr[left] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
复制代码时间复杂度：时间复杂度为NlogN 因为，它先找个哨兵，然后，哨兵的左边都小于等于哨兵，哨兵的右边都大于等于哨兵；一般情况下这个哨兵分出来的都是一半；而每次分出来以后，都需要进行循环一遍；所以，平均情况时间复杂度为NlogN;
如果，这个排序内容接近有序，因为每次访问到的哨兵区分出对象比较少；所以，时间复杂度会退化为N2;为了解决这个问题，有以下两种思路：
- 如果知道它是近乎有序的，那么，可以使用插入排序，时间复杂度直接升级到N；
- 如果你不知道它是不是有序，那么，就只能对这个哨兵来进行选取了，比如说：哨兵选取arr[left]、 arr[right]、 arr[mid] 这三个数的中间值来当作哨兵；
空间复杂度： 如果考虑递归的消耗，那么就是logN 如果，不考虑就是0；
稳定性：举例说明 2 1(l) 1(r) 3 通过快排排序后，结果为： 1(r) 1(l) 2 3 很显然是不稳定的；
2.归并排序
归并排序 也是有自己的特色；
特色一： 它的实现思路是分治；
特色二： 它是稳定的；
归并排序的话，主要是使用分治的思想来进行实现；
2.1 实现思路
对于，实现的思路可以查看以下链接： 归并排序的思路
2.2 代码实现：
import java.util.Random;
/**
* 1.归并排序的思路还是比较重要的，其实，有时候思路是一个比较重要的事情；
* 2.归并排序使用的是分治的思想;
* @auther:lgb
* @Date: 2021/5/9
*/
public class MergeSort {
/**
* 1.在递归调用的时候，原则就是先拆分，再进行合并；
* @param arr
* @param l
* @param r
*/
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
// 找出中间值
int mid = l + ((r - l) >> 1);
// 在[l, mid] 进行拆分
mergeSort(arr, l, mid);
// 在[mid , r] 进行拆分
mergeSort(arr, mid + 1, r);
// 1.当[0, 1]这种情况是可以进行合并的，这个时候，l = 0, mid = 0, r = 1;
// 2.像[0, 0]这种情况是不需要进行合并的，因为直接return了 不会执行到这里
merge(arr, l, mid, r);
}
// 这个时候，就进行合并了
public static void merge(int[] arr, int l, int m, int r) {
/**
* 1. 首先，先创建一个help数组
* 2. 为什么需要这个数组呢？把两个有序的数组需要合并到这个help数组中
* 3. 然后，再把help数组赋值到原数组arr上
*/
int[] help = new int[r - l + 1];
int i = 0;
/**
* 1. m把[l, r]数组划分为[l, m] [m + 1, r]
* 2. 其中，l1 代表左边的l,就是左边的第一个数
* r1 代表右边的 m + 1， 就是右边的第二个数
*/
int l1 = l;
int r1 = m + 1;
/**
* 1.如果，两边都没到最后的话
* 2.在help[i] 中存储arr[l1] 和 arr[r1]最小的那个
* 3.如果 左边没到最后，那么，左边的数就赋值到help中
* 4.如果 右边没到最后，那么，右边的数就赋值到help中
* 5.最后，再将数据赋值到右边中
*/
while (l1 <= m && r1 <= r) {
help[i++] = arr[l1] <= arr[r1] ? arr[l1++] : arr[r1++];
}
while (l1 <= m) {
help[i++] = arr[l1++];
}
while (r1 <= r) {
help[i++] = arr[r1++];
}
for (int j = 0; j < help.length; j++) {
arr[l + j] = help[j];
}
}
public static void main(String[] args) {
int length = 100;
int[] a = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++) {
a[i] = random.nextInt(100);
}
mergeSort(a,0, a.length - 1);
for (int value : a) {
System.out.println(value);
}
}
}
复制代码对下面代码中的四个箭头来进行分析：
- 第一个箭头，是先找到中间值
- 第二个箭头，是对[l, mid] 进行递归调用
- 第三个箭头，是对[mid + 1, r] 进行递归调用
- 第四个箭头，是对merge()来进行合并 ——–> 由于，它是在递归调用之后；所以，是先分在合；是一种分治算法；
时间复杂度：NlogN 因为，递归进行分 或者 合的时候 是需要 logN次 然后，每次合的时候，时间复杂度为N；
空间复杂度：在合并的过程中，是需要通过一个help[r – l + 1]来进行实现的，把两个排序好的数组来进行合并；所以，在不考虑递归调用的消耗情况下，空间复杂度为 N；
稳定性：稳定性这个这么考虑呢？我自己喜欢举例说明 以 1，2(l) 和 2(r)，3合并为例子；合并后，结果为1，2 (l), 2(r), 3这两个2 还是保持位置的稳定的；所以，它是一种稳定的排序算法；
3.堆排序
优先队列的底层实现：堆
3.1使用场景：
像快排、归并排序，都是将所有的数据都排序好了。然后，供我们进行使用；那么，假设我就像使用最大的前100个数，那么，后面排好序的元素，是不是就白排序了呢？ 确实是这样；
所以，堆的使用场景 TOPN 的相关问题；
在1000000个元素中选出前100个，在N个元素中选出前M个元素，这种题，就是使用优先队列，也就是堆排序是最好的选择；如果使用的快排，那么时间复杂度就是 NlogN; 如果使用优先队列的话，时间复杂度就是NlogM;就上面这个题来说，这么优化，可以使我们的算法快10几倍；
3.2 堆的基本实现
最大堆：1.任何节点都不大于它的父节点 2.是一颗完全二叉树；
注意：最大堆，并不意味着，层级越高，数越小；因为，你看第三层有一个数据是19，而第二层有数据是13；
堆有一个经典实现，通过数组来实现二叉堆；因为，堆是一颗完全的二叉树，对于每一个节点来说，它的左节点就是它的二倍（从索引1开始存储）；它的右节点就算它的二倍加一；
这样，就很好的使用数组来进行存储了；
3.2.1 向堆中增加元素offer()
1.先向数组的末尾加元素；
2.刚刚加入不一定是符合最大堆的定义的，需要进行维护；
3.和其父节点比，如果是大于父节点，就进行更换； 父节点就算当前结点索引 index/2;
3.2.2 向堆中弹出元素poll()
1.从最大堆中取出一个元素，只能取出最大的元素；
2.这时候，堆中第一个元素，没有了，那么怎么填补呢？
3.把堆中最后一个元素，放到堆顶,这样就只有一个元素不符合最大堆定义；
4.然后，在对堆中元素进行移动；
5.看根节点的左右结点判断出来，谁大和谁换；
6.直到它左右索引小于count,或者比左右结点大时才停止；
3.3 代码实现
/**
* 模拟一个最大堆
* 出队的是最大值
*/
public class Heap {
private int[] ints;
// 表示当前堆中数据
private int count = 0;
public Heap(int length) {
this.ints = new int[length + 1];
}
public static void main(String[] args) {
Heap heap = new Heap(1000);
Random random = new Random();
for (int i = 0; i < 500; i++) {
heap.offer(random.nextInt(10000));
}
for (int i = 0; i < 500; i++) {
System.out.println(heap.poll());
}
}
/**
* 向堆中增加元素
* 1.先向数组中，末尾加元素
* 2.刚刚加入不一定是符合最大堆的定义的，需要进行维护
* 3.和其父节点比，如果是大于父节点，就进行更换
*
* @param value
*/
public void offer(int value) {
int index = count + 1;
ints[index] = value;
// 父节点小于当前加入的值，就需要进行交换,直到不符合为止
while (index / 2 > 0 && ints[index / 2] < ints[index]) {
ints[index] = ints[index / 2];
ints[index / 2] = value;
index = index / 2;
}
count++;
}
/**
* 向堆中取出元素
* 1.从最大堆中取出一个元素，只能取出最大的元素
* 2.这时候，堆中第一个元素，没有了，那么怎么填补呢？
* 3.把堆中最后一个元素，放到堆顶即可
* 4.然后，在对堆中元素进行移动
* 5.看根节点的左右结点判断出来，谁大和谁换；
* 6.直到它左右索引小于count,或者比左右结点大时才停止
* 7.由于，它是最小的，所以，肯定是到最底层的，不会存在比左右结点大停止的情况
*/
public int poll(){
if (count <= 0){
return -1;
}
int res = ints[1];
ints[1] = ints[count];
count--;
int index = 1;
while (index * 2 <= count){
if (ints[index * 2] > ints[index * 2 + 1]){
int tem = ints[index];
ints[index] = ints[index * 2];
ints[index * 2] = tem;
index = index * 2;
}else {
int tem = ints[index];
ints[index] = ints[index * 2 + 1];
ints[index * 2 + 1] = tem;
index = index * 2 + 1;
}
}
return res;
}
}
复制代码时间复杂度：NlogM
空间复杂度：N
稳定性：不稳定 1(l) 2 3 1(r) 按照先加入后取出的原理 取出来以后为 3 2 1(r) 1(l) 可以照着添加元素和取出元素的思路来推理取出来的数据；
4.插入排序
4.1 思路分析
- 从第一个元素开始，该元素可以认为已经被排序；
- 下一个元素，如果，大于等于前面的元素，就结束；
- 如果，小于前面的元素，就把前面的元素向后移动一位，在和前面的元素进行判断，直到判断出来大于等于前面元素为止；
4.2 动图演示
4.3 代码实现
import java.util.Random;
/**
* @auther:lgb
* @Date: 2021/5/9
*/
public class InsertSort {
public static void insertSort(int[] ints) {
if (ints == null || ints.length <= 1) {
return;
}
for (int i = 1; i < ints.length; i++) {
if (ints[i] >= ints[i - 1]) {
continue;
}
int tem = i - 1;
int temValue = ints[i];
while (tem >= 0 && ints[tem] > temValue) {
ints[tem + 1] = ints[tem];
tem--;
}
ints[tem + 1] = temValue;
}
}
public static void main(String[] args) {
int length = 100;
int[] ints = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++) {
ints[i] = random.nextInt(100);
}
insertSort(ints);
for (int i = 0; i < length; i++) {
System.out.println(ints[i]);
}
}
}
复制代码时间复杂度：N2
空间复杂度：0
稳定性：稳定 举例 2(l),6,4,7,2(r) 排序后结果为 2(l),2(r),4,6,7;
以上的时间复杂度都大于等于NlonN的，下面介绍一些时间复杂度为N的排序算法；
5.桶排序
5.1 排序思想
划分多个范围相同的区间，每个子区间自排序，最后合并；
每个桶中存储一定范围的元素，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入到原序列中。
5.2 图解过程
5.3 代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
/**
* @auther:lgb
* @Date: 2021/5/9
*/
public class BucketSort {
public static void bucketSort(int[] ints) {
if (ints == null || ints.length <= 1) {
return;
}
int length = ints.length;
// 计算最大值和最小值
int max = ints[0];
int min = ints[0];
for (int i = 1; i < length; i++) {
max = Math.max(ints[i], max);
min = Math.min(ints[i], min);
}
// 判断桶的数量
int bucketNum = (max - min) / length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
/**
* 将元素放入到桶中
* 以 min = 0 max = 100 length = 10 为例
* 则一个桶存的区间为10 比如说第一个桶存的区间为[0,10); 总共有11个桶
* 像20 就应该存在第三个桶中；
*/
for (int i = 0; i < length; i++) {
int num = (ints[i] - min) / length;
bucketArr.get(num).add(ints[i]);
}
// 对每个桶进行排序
for (int i = 0; i < bucketNum; i++) {
Collections.sort(bucketArr.get(i));
}
// 将桶中元素赋值到原序列
int index = 0;
for (int i = 0; i < bucketNum; i++) {
for (int j = 0; j < bucketArr.get(i).size(); j++) {
ints[index++] = bucketArr.get(i).get(j);
}
}
}
public static void main(String[] args) {
int length = 100;
Random random = new Random();
int[] ints = new int[length];
for (int i = 0; i < length; i++) {
ints[i] = random.nextInt(100);
}
bucketSort(ints);
for (int i = 0; i < length; i++) {
System.out.println(ints[i]);
}
}
}
复制代码时间复杂度：假设数组长度为N 分成了M个桶，则每个桶有N/M个元素；对每个桶中元素进行快排时间复杂度为(N/M)*log(N/M) 因为有M个 所以时间复杂度为 (N/M)log(N/M) * M = Nlog(N/M) 如果N=M 那么，时间复杂度就变成N了；
空间复杂度：M + N 首先，需要有M个桶，然后，每个元素都需要加入到桶中，所以，还有加上N;
稳定性：主要是取决，每个桶内采取的排序算法是否稳定，如果是稳定的，就是稳定，如果不稳定，就不稳定；
6.计数排序
桶排序是一个桶中存放一部分区间，那么，如果，一个桶只存一个数，那么桶内就不需要进行排序了，不是更加简单了吗？这种排序算法就是计数排序；
假设，在[0,100]的区间内，有100个数需要进行排序；
6.1 代码实现
import java.util.ArrayList;
import java.util.Random;
/**
* @auther:lgb
* @Date: 2021/5/9
*/
public class CountSort {
public static void countSort(int[] ints) {
if (ints == null || ints.length <= 1) {
return;
}
int length = ints.length;
// 计算最大值和最小值
int max = 100;
int min = 0;
// 判断桶的数量
int bucketNum = (max - min) + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
/**
* 将元素放入到桶中
*/
for (int i = 0; i < length; i++) {
int num = ints[i];
bucketArr.get(num).add(ints[i]);
}
// 将桶中元素赋值到原序列
int index = 0;
for (int i = 0; i < bucketNum; i++) {
for (int j = 0; j < bucketArr.get(i).size(); j++) {
ints[index++] = bucketArr.get(i).get(j);
}
}
}
public static void main(String[] args) {
int length = 100;
Random random = new Random();
int[] ints = new int[length];
for (int i = 0; i < length; i++) {
ints[i] = random.nextInt(100);
}
countSort(ints);
for (int i = 0; i < length; i++) {
System.out.println(ints[i]);
}
}
}
复制代码这里说一下选择List而不是new int[100]的原因：其实，针对本题，使用int[100]也可以，比如说出现88 那么，在ints[88]++即可；但是，该方法没有体现出桶；而且，当需要{0：小丁， 1：小卢}对这种格式进行排序时，就不行了；所以，不选择此方法；
时间复杂度：N
空间复杂度：M + N 桶的数量 + 要排序数据的个数
稳定性：稳定
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
