- 1DDoS的攻击原理与防御方法_ddos攻击防御
- 2【nginx】nginx配置vue项目（包含vue页面和接口）_nginx 1.20 配置vue nginx页面访问和接口调用的配置
- 3Kafka重点笔记
- 4【不是拷贝】rabbitmq安装延迟队列插件rabbitmq_delayed_message_exchange_把rabiitmq延时消息插件编译成.ez
- 5网络编程：TLV标准详解_tlv网络
- 6使用Python进行云计算：AWS、Azure、和Google Cloud的比较
- 7第二周Python学习小结_python第二周
- 8《Spark系列》建立Hive和Hbase的映射关系，通过Spark将Hive表中数据导入ClickHouse_hive hbase 入到clinkhouse
- 9mysql表连接
- 10禅道-项目从0到1的过程18开源版本使用_禅道18.7 需要哪个版本的tomcat
十大排序算法_十大算法排序
赞
踩
声明：主要参考左程云算法视频
概述
十种常见排序算法可以分为两大类：
- 比较类排序（重点）：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。有冒泡，选择，插入，希尔，归并，快速，堆排序。
- 非比较类排序：不通过比较而是根据数据的状况来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序，以空间换时间实现。有计数排序，桶排序，基数排序。
总结
1、常用快速排序，需要考虑空间复杂度时使用堆排序，需要考虑稳定性时使用归并排序。
2、基于比较的排序算法不能突破时间复杂度O(NlogN)；
3、目前不存在时间复杂度为O(NlogN)，空间复杂度小于O(N），且能保证稳定性的算法。
4、归并排序的额外空间复杂度可以变成O(1)，但是非常难不需要掌握，可以搜“归并排序 内部缓存法” ，并且算法会失去稳定性，还不如用堆排序；另外通过“原地归并排序”实现O(1)的博客都不行，因为会让归并排序的时间复杂度为O(N^2)，还不如用插入。
5、快速排序可以做到稳定性，但是非常难不需要掌握， 可以搜“01 stable sort” ，但是会让空间复杂度为O(N），还不如用归并排序。
6、有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，要求时间复杂度为O(N)，空间复杂度为O(1)， 碰到这个问题直接怼面试官，经典的快排（1.0版本，小于等于区变成奇数区，大于区变成偶数区即可）的分层采用01标准，和本题的奇偶调整属于同一策略，但不能满足要求，请面试官指教怎么做。
7、工程上对排序算法的改进
- 充分利用O(NlogN)和O(N^2)排序各自的优势，进行综合排序；例如在大样本情况下采用快速（归并）排序，但在小样本情况下（比如数据量小于60）直接使用插入排序，这样就利用了大样本时快速（归并）排序调度的优势和小样本时插入排序常数项低的优势。
- 稳定性的考虑，例如系统提供的sort算法会判断数据类型为基础数据类型时使用快速排序，数据类型为自定义数据类型时使用归并排序，因为对基础数据类型稳定性意义不大还不如降低空间复杂度，而非基础类型的稳定性需求不确定应尽量保持。
相关名称解释：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- In-place：占用常数内存，不占用额外内存
- Out-place：占用额外内存
复杂度分析
时间复杂度
对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的指标。常用O （读作big O）来表示。具体来说，在常数操作数量的表达式中， 只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分 如果记为f(N)，那么时间复杂度为O(f(N))。
如选择排序中的常数操作数量的表达式可以写为an^2+bn+c —> n^2
评价一个算法流程的好坏，先看时间复杂度的指标，然后如果指标相同可以再分析不同数据样本下的实际运行时间，也就是常数项时间。
空间复杂度
指算法在计算机内执行时所需存储空间的度量，也是数据规模n的函数。
稳定性分析
稳定性的用途：排序算法的稳定性能够保留相对次序，在根据多项属性排序的场景下具有很好的应用。
如学生（商品）先按年龄（价钱）排序，再按班级（好评率）排序，如果能保证班级（好评率）排序时的稳定性，则得到的结果是学生（商品）按班级（好评率）排好序并且各班级（好评率相同的商品）中学生（商品）是按年龄（价钱）排好序的，反之若不能保证，则各班级学生（好评率相等的商品）的年龄（价钱）顺序就是混乱的。
选择排序：选择排序每轮选择最小元素放在前面，就会涉及到与前面元素的交换，就不能保证稳定性。
快速排序：在分层时遇到比基准小元素需要放在小于区，就会涉及到与小于区元素的交换，就不能保证稳定性；
堆排序：在更新为大根堆的过程中失去稳定性。
- 冒泡排序：遇到相同元素不交换即可保证稳定性；
- 插入排序：遇到相同元素不插入即可保证稳定性；
- 归并排序：归并时遇到相同元素先拷贝左边序列的即可保证稳定性，否则如下方的小和问题求解先拷贝右边的就失去了稳定性；
- 桶排序思想的排序：出入桶的过程中保证先入先出的顺序，从而保证了稳定性。
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
代码实现
时间复杂度为O(n^2)，空间复杂度为O(1)
public class bubbleSort { public static void bubbleSort(int[] array){ if(array == null || array.length < 2){ return; } //确定进行交换的范围，第一轮是0到n-1,第二轮是0到n-2... for(int i = array.length - 1; i > 0; i--){ for(int j = 0; j < i; j++){ //比较相邻元素，交换较大的数在后 if(array[j] > array[j+1]){ swap(array, i, j); } } } } //交换array的i和j位置上的值 public static void swap(int[] array, int i, int j){ array[i] = array[i] ^ array[j]; array[j] = array[i] ^ array[j]; array[i] = array[i] ^ array[j]; } public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; bubbleSort(array); System.out.println(Arrays.toString(array)); } }
- 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
异或运算 ^
10110 ^ 00111 = 10001
异或运算还可以理解为无进位相加；
异或运算的性质：
(1) 0 ^ N = N ，0和任意一个数进行异或运算都等于该数本身，
N ^ N = 0，任意一个数和自身进行异或运算都为0;
(2) 满足交换律，结合律，即a^b=b^a,a^b^c = a^(b^c)；
(3) 一群数和一个数进行异或运算得到结果与进行异或的顺序无关，结果是一样的（用无进位相加来理解）；
因此可以推出交换两个数可以写为：
但前提是a和b的内存地址不一样，如果a和b的内存位置一样，就会同一个位置跟自己进行异或运算，结果为0。
例题
1.在一个整型数组中，如果只有一种数出现了奇数次，其他数都出现偶数次，如何找到出现了奇数次的数？要求时间复杂度O(n) 空间复杂度O(1)
分析：其他数出现偶数次，分别进行异或运算得到的结果为0,最后只会剩下目标，0与目标数进行异或运算就是目标数，从而找到目标数。
public static void printOddTimeNuml(int[] array){
int eor = 0;
for(int cur : array){
eor ^= cur;
}
System.out.println(eor);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.在一个整型数组中，如果有两种数出现了奇数次，其他数都出现偶数次，如何找到出现了奇数次的两种数？要求时间复杂度O(n) 空间复杂度O(1)
分析：假设两种数分别为a和b，首先遍历数组进行异或，得到数必然为a^b，即异或结果为eor=a^b，说明eor必然不为0，进而说明eor的二进制数表达式中必然有一个位置为1；
然后在eor中确定一个为1的位置，可以通过下图所示的方法，提取出eor最右侧的1，得到rightOne，即一个数取反再加上1然后在原来的自己相与，就可以提取最右侧的1；
然后选出数组中所有二进制表达式中在该位为1的元素（将数组中的每一个数与rightOne做与运算，运算结果为1的满足条件），然后进行异或运算，得到的结果onlyOne必然是a或者b，因为eor在该位置为1，因此a和b在该位置必然不一致，一个为1另一个为0，通过筛选该位置为1的元素就可以确定a和b中的一个数（假设是a），此时再与eor=a^b进行异或运算就可以得到另一个数(b)。
public static void printOddTimeNum2(int[[ array){ int eor = 0, onlyOne = 0; //得到a^b for(int curNum : array){ eor ^= curNum; } //eor = a ^ b -> eor != 0 -> eor必然有一个位置为1 int rightOne = eor&(~eor + 1); //提出最右侧的1 for(int cur : array){ if((cur & rightOne) == 0){ onlyOne ^= cur; } } //a^b System.out.println(onlyOne + " " (eor ^ onlyOne)); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。
代码实现
时间复杂度为O(n^2)，空间复杂度为O(1)
public class selectionSort { public static void selectionSort(int[] array){ if(array == null || array.length < 2){ return; } //算法 要选择n-1轮 for(int i = 0; i < array.length - 1; i++){ int minIndex = i; //每轮选择当前轮次最小的数放在 数组中以对应轮数为索引的位置 for(int j = i + 1; j < array.length; j++){ minIndex = array[j] < array[minIndex] ? j : minIndex; } swap(array, i, minIndex); } } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; selectionSort(array); System.out.println(Arrays.toString(array)); } }
- 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
插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到小于或等于为排序数据的位置并插入。
插入排序比冒泡排序和选择排序更好，因为在某些数据情况下，插入排序的时间复杂度为O(1);
具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5
代码实现
时间复杂度为O(n^2)，空间复杂度为O(1)
package sort; import java.util.Arrays; //插入排序 // 构建有序序列，对于未排序数据， // 在已排序序列中从后向前扫描，找到小于或等于为排序数据的位置并插入。 public class insertionSort { public static void insertionSort(int[] array){ if(array == null || array.length < 2){ return; } // 0-i-1为已排序数据，i为待排序数据unsort所在位置 // 将j=i-1上的数据与unsort比较， // 如果array[j] > unsort, 交换两者位置，j--，unsort继续与前一位数比较； // 如果array[j] < unsort, 说明实现0-i的有序，i++，继续实现 for(int i = 1; i < array.length; i++){ for(int j = i - 1; j >= 0 && array[j] > array[j + 1];j--){ swap(array, j, j + 1); } } } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; insertionSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
对数器的概念和使用
有一个你想要测的方法a，
1，实现一个绝对正确但是复杂度不好的方法b，
2，实现一个随机样本产生器
3，实现比对的方法
4，把方法a和方法b比对很多次来验证方法a是否正确。
5，如果有一个样本使得比对出错，打印样本分析是哪个方法出错
6，当样本数量很多时比对测试依然正确，可以确定方法a已经 正确。
package sort; import java.util.Arrays; //插入排序 // 构建有序序列，对于未排序数据， // 在已排序序列中从后向前扫描，找到小于或等于为排序数据的位置并插入。 public class insertionSort { public static void insertionSort(int[] array){ if(array == null || array.length < 2){ return; } // 0-i-1为已排序数据，i为待排序数据unsort所在位置 // 将j=i-1上的数据与unsort比较， // 如果array[j] > unsort, 交换两者位置，j--，unsort继续与前一位数比较； // 如果array[j] < unsort, 说明实现0-i的有序，i++，继续实现 for(int i = 1; i < array.length; i++){ for(int j = i - 1; j >= 0 && array[j] > array[j + 1];j--){ swap(array, j, j + 1); } } } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } //对数器中的方法b 用于测试 public static void comparator(int[] array){ Arrays.sort(array); } //对数器中的随机样本产生器 public static int[] generateRandomArray(int maxSize, int maxValue){ //Math.random() -> [0,1)中的小数等概率返回一个 //Math.random() * N -> [0,N)中的小数等概率返回一个 //(int)(Math.random() * N) -> [0,N-1)中的整数等概率返回一个 int[] array = new int[(int)((maxSize + 1) * Math.random())]; //创建一个长度随机的数组 //数组元素在指定范围内随机产生 for(int i = 0; i < array.length; i++){ array[i] = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random()); } return array; } //复制随机数组 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; } //判断两个数组是否完全一样 public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } 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[] array1 = generateRandomArray(maxSize, maxValue); int[] array2 = copyArray(array1); //测试 insertionSort(array1); comparator(array2); if(!isEqual(array1, array2)){ succeed = false; //打印算法出错时的样本，进行分析 System.out.println(array1); break; } } System.out.println(succeed?"Nice!":"You need to think!"); //最后进行一次排序结果展示 int[] array = generateRandomArray(maxSize, maxValue); System.out.println(Arrays.toString(array)); insertionSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
希尔排序
希尔排序是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序又称缩小增量排序，基本思想是：设定一个增量gap，然后对相距gap的两个元素进行排序；然后减小gap，进行下一轮；直到gap=1，此时为比较相邻元素，排序完成后，数组整体排序完成。如图：
代码实现
希尔排序的时间复杂度一般是说为O(n^3/2)，其与gap有关系，程序中的{1,2,4,8,…}并不是很好的增量序列，其时间复杂度(最坏情形)是O(n^2)，Hibbard提出了另一个增量序列{1,3,7，...,2^k-1}(质数增量)，这种序列的时间复杂度(最坏情形)为O(n^1.5)。参考博客
空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，但比一般 O(n^2 ) 复杂度的算法快得多，对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择。
package sort; import java.util.Arrays; //希尔排序 //设定一个gap，然后对相距gap的两个元素进行排序；然后减小gap，进行下一轮； // 直到gap=1，此时为比较相邻元素，排序完成后，数组整体排序完成。 public class ShellSort { public static void shellSort(int[] array){ int length = array.length; //首先取gap为n/2 for (int gap = length/2; gap >= 1 ; gap >>= 1) { //子序列进行插入排序 for(int i = gap; i < length; i++){ int j = i; //从第gap个元素开始，排序相距gap（向前） 的两个元素，直到越界 while(j - gap >= 0 && array[j] < array[j-gap]){ swap(array, j, j-gap); j -= gap; } } } } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; shellSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
归并排序
递归
master公式中，等号左边代表子问题，等号右边，a代表子问题的调用次数，N/b代表子问题的规模，要求子问题规模必须等量；d代表其他计算的复杂度；当满足master公式时就可以直接求出时间复杂度。
例如在下面求数组最大值代码中，process为母问题，调用自己解决的子问题的规模为N/2，调用了2次，两次的规模一致；其他语句的时间复杂度为O(1)，因此 可以使用master公式：
求出时间复杂度：a=2,b=2,d=0 —> O(N^log(b,a))
//递归算法 求数组最大值 public class RecursionTest { public static int getMax(int[] array){ return process(array, 0, array.length - 1); } public static int process(int[] array, int L, int R){ if(L == R){ return array[L]; } int mid = L + ((R - L) >> 1); //中点 int leftMax = process(array, L, mid); int rightMax = process(array, mid+1, R); return Math.max(leftMax, rightMax) } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
算法思想
分治法：对一个待排序的长度为n的序列，通过递归的方式不断将其二分然后按规则进行归并。
- 递到最后子序列只剩一个元素，然后子序列两两归并，然后回归，再两两归并，直到最后归并完成，也就排序完成；
- 归并时的规则时小数在前，大数在后，从而实现升序排列
相比于O(n^2)的冒泡排序、选择排序以及插入排序第一轮比较n-1次才确定一个数的位置，第二轮比较n-2次，第三轮比较n-3次，各轮独立比较，浪费了比较得到的信息，归并排序充分利用了比较行为，每一次比较得到有序序列在下一次归并时有使用到，因此时间复杂度更低。
代码实现
分析
母问题为排序整个数组，规模为N，
将数组二分，化为子问题调用2次，子问题的规模为N/2，
其他语句时间复杂度的计算主要在于merge的时间复杂度为O(N)
即a=2，b=2，d=1，因此maser公式计算
时间复杂度为O(N*logN），空间复杂度为O(N)：归并时准备长度为N的空间存放归并后的序列
package sort; import java.util.Arrays; //归并排序 分治法 //将待排序数组分为两半，分别排序，然后归并在一起 public class MergeSort { public static void mergeSort(int[] array){ if(array == null || array.length < 2){ return; } process(array, 0, array.length - 1); } //二分 + 递归 完成排序 public static void process(int[] array, int left, int right){ if(left == right){ return; } //分治 完成两个子序列的排序 int mid = left + ((right - left) >> 1); process(array, left, mid); process(array, mid+1, right); //归并 merge(array, left, mid, right); } public static void merge(int[] array, int left, int mid, int right){ //存放归并后的元素 int[] tempArray = new int[right - left + 1]; int i = 0; //指针指向左序列起始位置 [left,mid] int p1 = left; //指针指向右序列起始位置 [mid+1, right] int p2 = mid + 1; //当两指针不越界的情况下,进行归并 //当p1指向的元素小于p2指向的元素时，p1指向的元素存入tempArray,p1后移 //继续对比两指针指向的元素，直到有指针越界 while(p1 <= mid && p2 <= right){ tempArray[i++] = array[p1] < array[p2] ? array[p1++]:array[p2++]; } //当p1指针未越界，p2指针越界时 //说明此时p2负责的右序列已经归并完成， //剩下的只是左序列中未归并的有序元素，归并即可 while(p1 <= mid){ tempArray[i++] = array[p1++]; } //当p2指针未越界，p1指针越界时 while(p2 <= right){ tempArray[i++] = array[p2++]; } //将已排序的数组装入原数组中 //注意，在递归排序过程中会将原数组划分为子序列，传进来进行排序 // 因此此处起点应是left + i for(i = 0; i < tempArray.length; i++){ array[left + i] = tempArray[i]; } } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; mergeSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
归并排序的扩展
小和问题
求解小和问题，可以将其反过来看（例如右边有4个比1大的数，因此加4个1），使用归并排序来求解
如图，在1 3归并时可以找到1个比1大的数，小和累加1个1；
1 3 4 归并时，可以找到1个比1大的数，小和累加1，1个比3大的数，小和累加3；
2 5归并时，可以找到1个比2大的数，小和累加2；
1 3 4 和 2 5归并时，可以看到右边第一个数比1大，因此可以直接计算出右边比1大的数共2个，小和累加2个1，可以找到1个比3大的数，小和累加3，可以找到1个比4大的数，小和累加4；小和为16。
这样求解不会有遗漏也不会有重复，相对于暴力求解（时间复杂度O(N^2))，时间复杂度仅为O(nlogn)。
另外，与传统归并排序可能不同的是，归并时当左右两边的元素相等时，必须先拷贝右边的数（传统的可能是先拷贝左边的），否则就不能直接根据下标计算出比左边数大的数的个数，如下图：
代码实现
package sort; import java.util.Arrays; //小和问题 在一个数组中， // 每一个数左边比当前数小的数累加起来，叫做这个数组的小和。 // 例如[1,3,4,2,5] 小和为16 public class SmallSumTest { public static int smallSum(int[] array){ if(array == null || array.length < 2){ return 0; } return process(array, 0, array.length - 1); } //实现排序 和 求小和 分 public static int process(int[] array, int left, int right){ //递归终止条件 if(left == right){ return 0; } int mid = left + ((right - left) >> 1); //返回求得的小和 // 实际上递归到最后 左右两边为1个数，小和为0， // 还是通过归并求得的小和，然后回归，才有左右两边求得的小和 return process(array, left, mid) // 左子序列求小和 + process(array, mid+1, right) //右子序列求小和 + merge(array, left, mid, right); //左右子序列归并时求小和 } //归并 治 public static int merge(int[]array, int left, int mid, int right){ int[] tempArray = new int[right - left + 1]; int i = 0; int p1 = left; int p2 = mid + 1; int smallSum = 0; //未越界时 while(p1 <= mid && p2 <= right){ //当左序列p1位置的元素小于右序列p2位置的元素时， // 则右序列中共有(right - p2 + 1)个元素大于p1指向的元素 // 从而计算小和 smallSum += array[p1] < array[p2] ? (right - p2 + 1) * array[p1] : 0; //排序 记得保证当两数相等时先存右边的 tempArray[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++]; } //越界时 while(p1 <= mid){ tempArray[i++] = array[p1++]; } while(p2 <= right){ tempArray[i++] = array[p2++]; } //装载 注意此处起始位置是 left + i 因为是各组子序列进行归并 for(i = 0; i < tempArray.length; i++){ array[left + i] = tempArray[i]; } return smallSum; } public static void main(String[] args) { int[] array = {1, 3, 4, 2, 5}; System.out.println(smallSum(array)); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
逆序对问题
求解逆序对问题和最小和问题相似，只需在归并时判断是否为逆序，逆序则记录，不逆序则不记录即可
快速排序
荷兰国旗问题
求解第一个问题
设定遍历数组下标 i=0，num=5，数组起始位前是小于等于区，预设三个区
- [i]<=num，[i[和小于等于区的下一个元素交换，小于等于区右扩一位，i++，继续判断；
- [i]>num，i++，继续判断；
- 直到i越界，此时已完成排序。
求解荷兰国旗问题
设定遍历数组下标 i=0，num=5，数组起始位前是小于区，末尾后是大于区，中间是等于区，预设三个条件
- [i]<num，[i]和小于区的下一个元素交换，小于区右扩一位，i++，继续判断；
- [i]=num，i++;
- [i]>num，[i]和大于区的前一个元素交换，大于区左扩一位，i原地不动（因为此时是交换过来的元素还未判断），继续判断；
- 直到i越界，此时已完成排序。
算法思想
快速排序的基本思想：通过一趟排序将待排元素分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快排1.0版本基于上述的第一个问题的解法，首先选择最后一个数为基准num，实现左边小于等于num，右边大于num，然后将大于区的第一个元素与num做交换，这样就完成初次分区（partition）操作；然后递归地在小于等于区和大于区分别设定新的基准进行分区，中间不动（只确定了一个数）；最后排序完成。
快排2.0版本基于上述的荷兰国旗问题的解法，首先选择最后一个数为基准num，实现左边小于num，右边大于num，中间等于num，然后将大于区的第一个元素与num做交换，这样就完成初次分区操作；然后递归地在小于区和大于区分别设定新的基准进行分区，等于区不动（确定了一批数）；最后排序完成。
快排2.0版本比快排1.0版本稍快，因为一次分区就确定一批数（等于num）的位置。但两个版本时间复杂度都是O(N^2)，因为如下，当选择的基准不好时（偏左或偏右）复杂度较高，此时每次分区只能确定一个数，当基准值越靠近中间时复杂度越低。
快排3.0版本，等概率随机选择基准，放到最后，然后实现左边小于num，右边大于num，中间等于num，然后将大于区的第一个元素与num做交换，完成初次分区操作；然后递归地在小于区和大于区分别设定新的基准进行分区，等于区不动（确定了一批数）；最后划分到待排序序列只有一个元素时，整个序列已排序完成。
此版本快速排序时间复杂度为O(nlogn)，与概率有关。
空间复杂度最差时为O(n)，此时最极端，每次选择的基准值都是最后一个数，导致每层递归中存放中间区位置信息的数组必须保留。（还不太理解）
最好时，空间复杂度为O(logn)，此时最好，每次基准值都是选择的中间位置的值，进行下一次递归时存放中间区信息的数组就可以释放。
代码实现
package sort; import java.util.Arrays; //快速排序 //通过随机选定基准，然后将待排序序列划分为小于区，等于区，大于区 //然后分别在小于区和大于区继续递归地划分 //最后划分到只有一个元素后 此时序列必然是已排好序的 //因为每一次递归得到的都是严格的小于区等于区大于区排列的子序列 public class QuickSort { public static void quickSort(int[] array){ if(array == null || array.length < 2){ return; } process(array, 0, array.length - 1); } //递归 不断分区 public static void process(int[] array, int left, int right){ //递归终止条件 left >= right if(left < right){ //随机选择基准 swap(array, left + (int)(Math.random() * (right - left + 1)), right); //存储等于区第一个元素的位置和最后一个元素的位置以确定边界 int[] border = partition(array, left, right); process(array, left, border[0] - 1); //小于区 process(array, border[1] + 1, right); //大于区 } } //分区 public static int[] partition(int[] array, int left, int right){ int lessBorder = left - 1; //小于区边界 初始时为待排数组首元素前一位 int moreBorder = right; //大于区边界 初始时为待排数组尾元素所在位置 尾元素是基准 while(left < moreBorder){ //left表示当前数的位置 //当前数小于基准时 // 当前数与小于区边界的下一个元素交换，小于区右扩 // 然后继续判断下一个当前数 if(array[left] < array[right]){ swap(array, ++lessBorder, left++); }else if(array[left] > array[right]){ //当前数大于基准时 //当前数与大于区边界的前一个元素交换，大于区左扩 //然后判断交换后的元素 swap(array,--moreBorder, left); }else { //当前数等于基准时，直接后移 left++; } } //遍历完成后 交换基准到大于区的第一个元素位置 //此时左边区小于基准，中间区等于基准，右边区大于基准 swap(array, moreBorder, right); //返回等于区的左右边界 return new int[]{lessBorder + 1, moreBorder}; } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; quickSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
堆排序
堆概念
堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵完全二叉树的数组对象。满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。
- 堆总是一棵完全二叉树。
堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。
堆结构
二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。其中堆的根节点最大称为最大堆，如下图所示：
堆结构就是用数组实现的完全二叉树结构
假设当前元素的索引位置为 i，可以得到规律（计算结果须在索引范围内，如上图中size=7，范围为0-6）：
- parent(i) = (i-1)/2（取整） 如i=3 父节点是(3-1)/2 = 1
- left child(i) = 2i + 1 如i=2 左子树是22+1 = 5
- right child(i) = 2i +2 如i=2 右子树是22+2 = 6
由此，可以将从0出发的连续的size个数就可以想作一颗完全二叉树，即可以用数组表示堆。
所谓的优先级队列结构就是堆结构，堆顶是优先级最大的。
大根堆和小根堆
大根堆：父节点的值大于或等于子节点的值；
小根堆：父节点的值小于或等于子节点的值
堆的操作：堆插入和堆化
堆插入insert
插入一个元素：新元素被加入到堆的末尾，然后更新树以恢复堆的次序。
具体是如何通过数组array实现呢？举例如下：
- 初始时heapsize=0，存入一个数5，5存入到array[heapsize=0]处，heapsize更新为1；
- 然后存入数3，根据计算公式(1-1)/2=0找到父节点值5，比父节点小，3存入array[heapsize=1]，heapsize更新为2；
- 然后存入数6，(i-1)/2=0找到父节点值5，比父节点大，交换，6存入array[0]，5存入array[2]，heapsize更新为3；
- 然后存入数7，(i-1)/2=1找到父节点值3，比父节点大，交换，7存入array[1]，3存入array[3]，没到根节点（i=1）继续计算(i-1)/2=0，找到父节点值6，比父节点大，交换，7存入array[0]，6存入array[1]，heapsize更新为4；
- 然后存入数7，(i-1)/2=1，找到父节点值6，比父节点大，交换，7存入array[1]，6存入array[4]，没到根节点继续计算(i-1)/2=0，找到父节点值7，不比父节点大，不交换，heapsize更新为5；
代码实现
public static void heapInsert(int[]array, int index){
//如果新插入的元素比父节点元素的大则交换
// 直到到根节点或者不比父节点的值大为止
while(array[index] > array[(index - 1) / 2]){
swap(array, index, (index - 1) / 2);
index = (index - 1)/2;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
移除最大值Removemax
按定义，就是每次删除堆中第0个数据。
但为了便于重建堆，实际是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右子结点中找最大的，如果父结点比这个最大的子结点还大说明不需要调整了，反之则将父结点和它交换，然后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。如图（左上->左下->右上->右下）。
而上述过程实际就是堆化heapify（将一个数组调整为最大堆. ）过程，即将某一不符合堆结构的数据下沉至符合堆结构的位置。
代码实现
//堆化 若树中index对应节点的数据小于子树， // 则将其不断下沉交换，直到大于子树的值或成为叶子节点 public static void heapify(int[]array, int index, int heapSize){ int left = index * 2 + 1; //计算得到左子树的下标 // 判断index所在节点是否存在子树 //左子树下标小于heapSize，说明左子树存在，index所在非叶子节点 //否则说明index所在节点为叶子节点，下方不存在子树 while(left < heapSize){ //选出左右子树中较大者并将其下标赋给largest int largest = left + 1 < heapSize && array[left + 1] > array[left] ? left + 1 : left; //判断子树的值是否大于父节点 如果小于说明遵循堆结构，退出循环 //如果大于则交换 并继续下沉判断 largest = array[largest] > array[index] ? largest : index; if(largest == index){ break; } swap(array, largest, index); //指向该待堆化的数据，继续判断是否大于子树的值 index = largest; left = index * 2 + 1; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
总结
在上述的两个堆操作的基础上，当堆中数据发生变化时，若数据变大则可以使用堆插入（向上调整），若数据变小则可以使用堆化（向下调整），从而保持大根堆的结构。
因为高度为h的二叉树至多有2^h - 1个节点，因此具有n个节点的完全二叉树必然与高度h成对数关系（logn），因此在堆中插入新数据（从下往上与高度有关）的时间复杂度为O(logn)，删除最大值并完成堆化（从上往下与高度有关）的时间复杂度也是O(logn)。
堆排序思想
可以将数组（长度为size）排序问题看作是将数组实现堆结构（heapsize=size）再不断删除堆中最大值直到堆中没有元素的操作，此时排序完成。
具体流程如下：
1、首先进行堆插入操作实现将数组转换为堆结构，相当于不断从数组中“取出”元素—>插入堆末尾—>更新为堆结构，直到数组遍历完毕，此时heapsize更新到size大小，堆中根节点为数组中最大的数；
2、然后进行堆的删除最大值操作实现不断确定数组各元素的位置，即将根节点的数与最后一个节点的数进行交换，heapsize--（确定此时数组中最大元素的位置），然后进行堆化直到将此时的最大值置于根节点；然后继续将根节点的数与最后一个节点的数进行交换，heapsize--，以此类推，直到heapsize为0，此时数组中所有元素都已确定位置，数组排序完成。
注意，上述过程中heapsize--可能不好理解，其实就是从堆中去除该元素使其不参与堆中的后续操作，与数组无关。例如第一轮时，堆中根节点元素就是数组最大元素，此时该元素对应在数组第一个元素的位置，交换后，就到了数组中最后一个元素的位置，从堆结构中去除该元素不参与堆中的后续操作，则该元素始终在数组最后一个元素的位置，以此类堆就不断确定元素位置，实现排序。
时间复杂度为O(NlogN + NlogN)——>O(NlogN)，额外空间复杂度为O(1)，只用了常数级空间。
代码实现
package sort; import java.util.Arrays; public class HeapSort { public static void heapSort(int[] array){ if(array == null || array.length < 2){ return; } //使用堆插入操作实现将数组转为堆结构 for(int i = 0; i < array.length;i++){ //O(N) heapInsert(array, i); //O(logN) } //heapSize从1开始计数，即堆中一个元素heapSize=1 int heapSize = array.length; //将堆中根节点的值与最后一个节点交换， //并从堆中去掉该值实现确定该元素在数组中的位置， swap(array, 0, --heapSize); //堆化直到根节点为最大值 然后继续交换 //直到heapsize=0，此时数组中所有元素都已确定位置，排序完成 while(heapSize > 0){ //O(N) heapify(array, 0, heapSize); //O(logN) swap(array, 0, --heapSize); //O(1) } } //堆插入操作：新元素被加入到heap的末尾，然后更新树以恢复堆的次序。 public static void heapInsert(int[]array, int index){ //如果新插入的元素比父节点元素的大则交换 // 直到到根节点或者不比父节点的值大为止 while(array[index] > array[(index - 1) / 2]){ swap(array, index, (index - 1) / 2); index = (index - 1)/2; } } //堆化 若树中index对应节点的数据小于子树， // 则将其不断下沉交换，直到大于子树的值或成为叶子节点 public static void heapify(int[]array, int index, int heapSize){ int left = index * 2 + 1; //计算得到左子树的下标 // 判断index所在节点是否存在子树 //左子树下标小于heapSize，说明左子树存在，index所在非叶子节点 //否则说明index所在节点为叶子节点，下方不存在子树 while(left < heapSize){ //选出左右子树中较大者并将其下标赋给largest int largest = left + 1 < heapSize && array[left + 1] > array[left] ? left + 1 : left; //判断子树的值是否大于父节点 如果小于说明遵循堆结构，退出循环 //如果大于则交换 并继续下沉判断 largest = array[largest] > array[index] ? largest : index; if(largest == index){ break; } swap(array, largest, index); //指向该待堆化的数据，继续判断是否大于子树的值 index = largest; left = index * 2 + 1; } } public static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; heapSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
进一步优化
不使用不断在堆中插入新数据的方式实现数组到大根堆的转换，而是先堆化最末尾最小的树，然后依次往前堆化，直到堆化完整颗大树，转换完成，即如下图标号所示进行堆化：
计算时间复杂度：设有n个节点，则最多有n/2+1个叶节点，每个节点只需查看1次；倒数第二层节点必然有n/4+1个节点，每个节点需查看1次，进行堆化时最多下沉1次；倒数第二层节点必然有n/8+1个节点，每个节点需查看1次，堆化时2次；。。。。以此类推，总共时间复杂度为T(n)=n/2*1+n/4*2+n/8*3+n/16*4..... —> O(n)
如此完成大根堆的转换后，再进行删除最大值操作，这样第一步的数组转大根堆操作就会变快一点，但整个堆排序的时间复杂度仍是O(nlogn），因为O(nlog n) + O(n) = O(n+nlogn) ， nlogn比n增长得快，放大来看，可以忽略O(n)，从而就等同于O(nlogn)。
堆排序扩展
求解本题可以使用一个小根堆，设k=6，首先从数组中取k+1=7个数构建小根堆，然后从数组中再取一个数放入堆中并更新为堆结构，堆中删除根节点的数，此时最小的元素必然在数组首位，因为每个元素移动的距离不会超过k，所以最小元素最远在数组中第7位，从而确定最小元素；然后从数组中再取一个数放入堆中并更新为堆结构，此时数组中第二小的元素必然在数组第二位，因为每个元素移动的距离不会超过k，所以此时数组中第二小的元素必然在堆中，。。。，以此类推，直到数组中元素取尽，再依次弹出堆中数据直到堆中没有数据，排序完成。
时间复杂度为O(N*logK)->O(N)
代码实现
java中**优先级队列PrioriyQueue的底层实现就是堆结构，默认为小根堆**，弹出时优先最小元素；
因此可以直接使用优先级队列作为小根堆，但需注意以下几点：
- add(）方法添加元素，poll方法弹出元素，对应的时间复杂度都分别为O(logN)；
- 底层是由数组实现堆结构，一直添加数据就会涉及到数组扩容问题，其中使用成倍扩展（2->4,N->2N），因此设有N个数，则共需扩容logN次（复制到新数组），总共的时间复杂度为O(NlogN)，平均下来到每次添加数中就是O(NlogN / N) = O(logN），因此扩容并不会影响整体时间复杂度；
- 使用系统提供的堆结构时，只能进行添加，弹出操作，而不支持改变其中的元素后用很低的代价更新为堆结构，这是与开发者自己手写实现堆结构的最大区别，因此，只涉及到添加和弹出操作时可以使用系统提供的堆结构，其他时候建议自己手写实现堆结构。
package sort; import java.util.Arrays; import java.util.PriorityQueue; //堆排序扩展 数组排序完成时，每个元素移动的距离不超过k,且k相对数组较小 //使用小根堆解决，得到的结果为升序 public class SortArrayDistanceLessK { public static void sortArrayDistanceLessK(int[] array, int k){ //java中优先级队列结构的底层实现就是堆结构，默认为小根堆 PriorityQueue<Integer> heap = new PriorityQueue<>(); //初始时从数组中取k+1个元素放入堆中 //这里使用math.min防止k超出数组长度，程序bug int index = 0; for(; index <= Math.min(array.length, k); index++){ heap.add(array[index]); } //然后从数组中取出1个数添加入堆中，堆中再弹出一个数， // 依次确定数组中各元素位置，直到数组中元素取尽 int i = 0; for(; index < array.length; i++, index++){ heap.add(array[index]); array[i] = heap.poll(); } //数组取尽后依次弹出堆中数据直到没有，数组排序完成 while(!heap.isEmpty()){ array[i++] = heap.poll(); } } public static void main(String[] args) { int[] array = {5,23,6,3,22,56,7}; sortArrayDistanceLessK(array,4); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
比较器的使用
进行自定义数据类型的比较，例如定义一个类Student，通过id大小确定多个Student对象的顺序，
使用比较器就可以将优先级队列转为大根堆
package sort; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; //堆排序扩展 数组排序完成时，每个元素移动的距离不超过k,且k相对数组较小 //使用大根堆解决，得到的结果为降序 public class SortArrayDistanceLessK { public static void sortArrayDistanceLessK(int[] array, int k){ //java中优先级队列结构的底层实现就是堆结构，默认为小根堆，加比较器后为大根堆 PriorityQueue<Integer> heap = new PriorityQueue<>(new AComp()); //初始时从数组中取k+1个元素放入堆中 //这里使用math.min防止k超出数组长度，程序bug int index = 0; for(; index <= Math.min(array.length, k); index++){ heap.add(array[index]); } //然后从数组中取出1个数添加入堆中，堆中再弹出一个数， // 依次确定数组中各元素位置，直到数组中元素取尽 int i = 0; for(; index < array.length; i++, index++){ heap.add(array[index]); array[i] = heap.poll(); } //数组取尽后依次弹出堆中数据直到没有，数组排序完成 while(!heap.isEmpty()){ array[i++] = heap.poll(); } } public static void main(String[] args) { int[] array = {5,23,6,3,22,56,7}; sortArrayDistanceLessK(array,4); //降序 System.out.println(Arrays.toString(array)); } } //使用比较器将优先级队列转为大根堆 class AComp implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
但由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
算法流程
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为 i 的元素出现的次数，存入额外开辟的数组C的第 i 项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去1
代码实现
时间复杂度:Ο(n+k)（k为数据范围）
空间复杂度:O(K)
这样的算法虽然时间复杂度非常低，但是空间复杂度确十分高，K很大时就难以执行，是用空间来换取时间的做法
package sort; import java.util.Arrays; //计数排序 //根据待排序数组的数据情况创建0-数组最大值范围的辅助数组（桶) //然后遍历数组，出现一个元素，对应桶就+1，实现桶中记录数组中各元素的个数 //然后遍历桶，依次将对应元素存入原数组并清零桶中记录，直到所有桶记录为0，排序完成 public class CountSort { public static void countSort(int[] array){ if(array == null || array.length < 2){ return; } //获取最大值 int max = Integer.MIN_VALUE; for(int i = 0; i < array.length; i++){ max = Math.max(max, array[i]); } //构建桶 数组大小为0-max 各元素值代表待排序数组中有多少这个数 int[] bucket = new int[max + 1]; //入桶 for(int i = 0; i < array.length; i++){ bucket[array[i]]++; } //出桶 int i = 0; for(int j = 0; j < bucket.length; j++){ //bucket对 待排序数组中为j值的元素的个数的记录清零 while(bucket[j]-- > 0){ array[i++] = j; //存入原数组 } } } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; countSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
具体流程如图：
代码实现
当输入的数据可以均匀的分配到每一个桶中，桶排序最快，当输入的数据被分配到了同一个桶中时最慢，同时各桶排序时选用的排序算法也很重要，一般选用快排。
对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：
- N 次循环，将每个元素装入对应的桶中 M次循环；
- 对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）
一般使用较为快速的排序算法，时间复杂度为 O(NlogN) ，实际的桶排序过程是以链表形式插入的。
整个桶排序的时间复杂度为： O(N)+O(M∗(N/M∗log(N/M)))=O(N∗(log(N/M)+1))，最好情况是当 N = M 时，复杂度为O(N)，最坏是所有数据都在同一个桶中，时间复杂度为O(N^2)，因此时间度复杂度（平均）为O(N+k)
额外空间复杂度：O(N + M)
package sort; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class BucketSort { public static void bucketSort(int[] array){ //计算最值 int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i < array.length; i++) { max = Math.max(max, array[i]); min = Math.min(min, array[i]); } //计算桶的数量 桶数和原数组大小保持一致 int bucketNum = (max - min) / array.length + 1; //链表实现桶 每个桶可以装多个元素， 链表将多个桶装载 ArrayList<ArrayList<Integer>> bucketArray = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArray.add(new ArrayList<Integer>()); } //入桶 各桶的数据范围长度取为数组长度 for (int i = 0; i < array.length; i++) { int num = (array[i] - min) / array.length; //计算元素对应的桶编号 bucketArray.get(num).add(array[i]); } //各桶进行排序 这里使用系统提供的排序方法 for(int i = 0; i < bucketArray.size(); i++){ Collections.sort(bucketArray.get(i)); //其实就是链表排序 } //出桶 将各桶的元素复制到原数组 int index = 0; for (int i = 0; i < bucketArray.size(); i++) { for(int j = 0; j < bucketArray.get(i).size(); j++){ array[index++] = bucketArray.get(i).get(j); } } } //测试 public static void main(String[] args) { int[] array = {23,5,6,7,22,56,3}; bucketSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
基数排序
基数排序是先按照低位放入对应容器（桶）中，然后按照桶的顺序和先进先出的规则，从桶中出来；再按照高位放入对应桶中，再从桶中出来；依次类推，直到最高位。
基数排序基于数据状况完成排序，如下例中，待排数据是根据数据的进制确定优先级。
如下图中，3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 进行排序
- 先按个位数入相应的桶，3->3号桶，44->4号桶，38->8号桶，，，50->0号桶，48->8号桶；
- 然后按照桶的顺序以及先进先出的原则出桶，50，2，3，44，4，5，，，19；
- 然后按十位数进入相应桶，，，出桶，排序完成。
代码实现
时间复杂度：O(K * (N + M)) = O(N*K），N为数据数量，M为数据取值范围，K为执行的计数排序次数。
空间复杂度：O(N + M)， N为数据数量，M为数据取值范围
package sort; import java.util.Arrays; public class RadixSort { //仅考虑非负数 public static void radixSort(int[] array){ if(array == null || array.length < 2){ return; } //方法重载 注意参数不一致即可辨别 radixSort(array, 0, array.length - 1, getMaxDigit(array)); } //获取最高位数 public static int getMaxDigit(int[] array){ int max = Integer.MIN_VALUE; for (int i = 0; i < array.length; i++) { max = Math.max(max, array[i]); } int maxDigit = 0; while(max != 0){ maxDigit++; max /= 10; } return maxDigit; } //基数排序 [13,21,11,52,62] public static void radixSort(int[] array, int left, int right, int digit){ final int radix = 10; int i = 0, j = 0; //辅助数组 int[] bucket = new int[right - left + 1]; //有多少位就出入桶多少次 通过count和bucket模拟实现出入桶 for (int d = 1; d <= digit; d++) { //入桶 //count[0] 记录当前位(d位）是0的数字有多少个 //count[1] 记录当前位(d位）是0和1的数字有多少个 //count[i] 记录当前位(d位）是0-i的数字有多少个 [0,2,4,5,5,5,5,5,5,5] int[] count = new int[radix]; for(i = left; i <= right; i++){ //count[i]记录=i的数字有多少个 j = getDigit(array[i], d); count[j]++; } for(i = 1; i < radix; i++){ //count[i]记录<=i的数字有多少个 count[i] = count[i] + count[i - 1]; } //原数组从右往左遍历存入辅助数组，通过count，实现按规则出桶 //i=4, 62 -> 2 count[2]-1=4-1=3 bucket[3]=62 //数组中共4个数<=2，都进2桶，顺序为21,11,52,62, // 因此62应最后出桶，放在辅助数组第4-1位，同理52放在第3-1=2位 //i=2, 11 -> 1 count[1]-1=2-1=1 bucket[1]=11 //数组中共2个数<=1，都进1桶，顺序为21,11, // 因此11应最后出桶，放在辅助数组第2-1=1位，同理21放在第1-1=0位 for(i = right; i >= left; i--){ j = getDigit(array[i], d); bucket[count[j] - 1] = array[i]; count[j]--; } for(i = left,j = 0; i <= right; i++,j++){ array[i] = bucket[j]; } } } //获取当前位的数字 public static int getDigit(int x, int d) { //357 d=1 357/1%10=7 d=2 357/10%10=5 d=3 357/100%10=3 return ((x/((int)Math.pow(10, d - 1))) % 10); } //测试 public static void main(String[] args) { int[] array = {23,52,64,72,22,56,3}; radixSort(array); System.out.println(Arrays.toString(array)); } }
- 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
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
