排序算法很多地方都会用到,近期又重新看了一遍算法,并自己简单地实现了一遍,特此记录下来,为以后复习留点材料。
废话不多说,下面逐一看看经典的排序算法:
1. 选择排序
选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。
举个实例来看看:
- 初始: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
- i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])
- i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])
- i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])
- i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 无需交换 )
- i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])
- i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])
- i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])
- i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
- i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
- i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
由例子可以看出,选择排序随着排序的进行( i 逐渐增大),比较的次数会越来越少,但是不论数组初始是否有序,选择排序都会从 i 至数组末尾进行一次选择比较,所以给定长度的数组,选择排序的比较次数是固定的: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ,而交换的次数则跟初始数组的顺序有关,如果初始数组顺序为随机,则在最坏情况下,数组元素将会交换 n 次,最好的情况下则可能 0 次(数组本身即为有序)。
由此可以推出,选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) (选择排序只需要一个额外空间用于数组元素交换)。
实现代码:
- /**
- * Selection Sorting
- */
- SELECTION(new Sortable() {
- public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
- int len = array.length;
- for (int i = 0; i < len; i++) {
- int selected = i;
- for (int j = i + 1; j < len; j++) {
- int compare = array[j].compareTo(array[selected]);
- if (compare != 0 && compare < 0 == ascend) {
- selected = j;
- }
- }
- exchange(array, i, selected);
- }
- }
- })
2. 插入排序
插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。
以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置,于是我们需要依次与前面的元素 31 、 11 做比较,一边比较一边移动比较过的元素,直到找到第一个比 12 小的元素 11 时停止比较,此时 31 对应的索引 1 则是 12 需要插入的位置。
- 初始: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
- 第一趟: [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (无移动的元素)
- 第二趟: [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] ( 31 向后移动)
- 第三趟: [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] ( 11, 12, 31 皆向后移动)
- 第四趟: [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (无移动的元素)
- 第五趟: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] ( 31, 34 向后移动)
- 第六趟: [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] ( 30, 31, 34 向后移动)
- 第七趟: [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (无移动的元素)
- 第八趟: [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] ( 38 向后移动)
- 第九趟: [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] ( 26, 30, 31, 34, 36, 38 向后移动)
插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码:
- /**
- * Insertion Sorting
- */
- INSERTION(new Sortable() {
- public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
- int len = array.length;
- for (int i = 1; i < len; i++) {
- T toInsert = array[i];
- int j = i;
- for (; j > 0; j--) {
- int compare = array[j - 1].compareTo(toInsert);
- if (compare == 0 || compare < 0 == ascend) {
- break;
- }
- array[j] = array[j - 1];
- }
- array[j] = toInsert;
- }
- }
- })
3. 冒泡排序
冒泡排序可以算是最经典的排序算法了,记得小弟上学时最先接触的也就是这个算法了,因为实现方法最简单,两层 for 循环,里层循环中判断相邻两个元素是否逆序,是的话将两个元素交换,外层循环一次,就能将数组中剩下的元素中最小的元素“浮”到最前面,所以称之为冒泡排序。
照例举个简单的实例吧:
- 初始状态: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
- 内层第一趟: [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] ( 9th [23]<->8th [38 )
- 内层第二趟: [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] ( 8th [23]<->7th [29] )
- 内层第三趟: [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] ( 7th [23]<->6th [31] )
- 内层第四趟: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] ( 7 、 23 都位于正确的顺序,无需交换)
- 内层第五趟: [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] ( 5th [7]<->4th [36] )
- 内层第六趟: [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] ( 4th [7]<->3rd [39] )
- 内层第七趟: [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] ( 3rd [7]<->2nd [26] )
- 内层第八趟: [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] ( 2nd [7]<->1st [19] )
- 内层第九趟: [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] ( 1st [7]<->0th [24] )
- ………
其实冒泡排序跟选择排序比较相像,比较次数一样,都为 n * (n + 1) / 2 ,但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换,与之对应的是选择排序,只会在内层循环比较结束之后根据情况决定是否进行交换),所以在我看来,选择排序属于冒泡排序的改进版。
实现代码:
- /**
- * Bubble Sorting, it's very similar with Insertion Sorting
- */
- BUBBLE(new Sortable() {
- public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
- int length = array.length;
- int lastExchangedIdx = 0;
- for (int i = 0; i < length; i++) {
- // mark the flag to identity whether exchange happened to false
- boolean isExchanged = false;
- // last compare and exchange happened before reaching index i
- int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
- for (int j = length - 1; j > currOrderedIdx; j--) {
- int compare = array[j - 1].compareTo(array[j]);
- if (compare != 0 && compare > 0 == ascend) {
- exchange(array, j - 1, j);
- isExchanged = true;
- lastExchangedIdx = j;
- }
- }
- // if no exchange happen means array is already in order
- if (isExchanged == false) {
- break;
- }
- }
- }
- })
4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组,以 gap 来划分,比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 来划分,可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组(对应的,如 gap = 3 ,则划分的数组为: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤,直至 gap = 1 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。
实现代码:
- /**
- * Shell Sorting
- */
- SHELL(new Sortable() {
- public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
- int length = array.length;
- int gap = 1;
- // use the most next to length / 3 as the first gap
- while (gap < length / 3) {
- gap = gap * 3 + 1;
- }
- while (gap >= 1) {
- for (int i = gap; i < length; i++) {
- T next = array[i];
- int j = i;
- while (j >= gap) {
- int compare = array[j - gap].compareTo(next);
- // already find its position
- if (compare == 0 || compare < 0 == ascend) {
- break;
- }
- array[j] = array[j - gap];
- j -= gap;
- }
- if (j != i) {
- array[j] = next;
- }
- }
- gap /= 3;
- }
- }
- })
5. 归并排序
归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间,比如需要规定的数组分别为: [3, 6, 8, 11] 和 [1, 3, 12, 15] (虽然逻辑上被划为为两个数组,但实际上这些元素还是位于原来数组中的,只是通过一些 index 将其划分成两个数组,原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ,我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下:
1) 将两个子数组中的元素复制到新数组 copiedArray 中,以前面提到的例子为例,则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ;
2) 设置两个指针分别指向原子数组中对应的第一个元素,假定这两个指针取名为 leftIdx 和 rightIdx ,则 leftIdx = 0 (对应 copiedArray 中的第一个元素 [3] ), rightIdx = 4 (对应 copiedArray 中的第五个元素 [1] );
3) 比较 leftIdx 和 rightIdx 指向的数组元素值,选取其中较小的一个并将其值赋给原数组中对应的位置 i ,赋值完毕后分别对参与赋值的这两个索引做自增 1 操作,如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾,则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例:
- 第一趟:
- 辅助数组 [21 , 28, 39 | 35, 38] (数组被拆分为左右两个子数组,以 | 分隔开)
- [21 , , , , ] (第一次 21 与 35 比较 , 左边子数组胜出, leftIdx = 0 , i = 0 )
- 第二趟:
- 辅助数组 [21, 28 , 39 | 35, 38]
- [21 , 28, , , ] (第二次 28 与 35 比较,左边子数组胜出, leftIdx = 1 , i = 1 )
- 第三趟: [21, 28, 39 | 35 , 38]
- [21 , 28 , 35, , ] (第三次 39 与 35 比较,右边子数组胜出, rightIdx = 0 , i = 2 )
- 第四趟: [21, 28, 39 | 35, 38 ]
- [21 , 28 , 35 , 38, ] (第四次 39 与 38 比较,右边子数组胜出, rightIdx = 1 , i = 3 )
- 第五趟: [21, 28, 39 | 35, 38]
- [21 , 28 , 35 , 38 , 39] (第五次时右边子数组已复制完,无需比较 leftIdx = 2 , i = 4 )
以上便是一次归并的过程,我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为 1 的小数组为止,长度为 1 时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作,直到最后一次归并长度为 n / 2 的子数组,归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断),时间复杂度比较难估,这里小弟也忘记是多少了(囧)。
实现代码:
- /**
- * Merge sorting
- */
- MERGE(new Sortable() {
- public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
- this.sort(array, 0, array.length - 1, ascend);
- }
- private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
- // OPTIMIZE ONE
- // if the substring's length is less than 20,
- // use insertion sort to reduce recursive invocation
- if (hi - lo < 20) {
- for (int i = lo + 1; i <= hi; i++) {
- T toInsert = array[i];
- int j = i;
- for (; j > lo; j--) {
- int compare = array[j - 1].compareTo(toInsert);
- if (compare == 0 || compare < 0 == ascend) {
- break;
- }
- array[j] = array[j - 1];
- }
- array[j] = toInsert;
- }
- return;
- }
- int mid = lo + (hi - lo) / 2;
- sort(array, lo, mid, ascend);
- sort(array, mid + 1, hi, ascend);
- merge(array, lo, mid, hi, ascend);
- }
- private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
- // OPTIMIZE TWO
- // if it is already in right order, skip this merge
- // since there's no need to do so
- int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
- if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
- return;
- }
- @SuppressWarnings("unchecked")
- T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
- System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
- int lowIdx = 0;
- int highIdx = mid - lo + 1;
- for (int i = lo; i <= hi; i++) {
- if (lowIdx > mid - lo) {
- // left sub array exhausted
- array[i] = arrayCopy[highIdx++];
- } else if (highIdx > hi - lo) {
- // right sub array exhausted
- array[i] = arrayCopy[lowIdx++];
- } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
- array[i] = arrayCopy[lowIdx++];
- } else {
- array[i] = arrayCopy[highIdx++];
- }
- }
- }
- })
6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法,它的魅力之处在于它能在每次 partition (排序算法的核心所在)都能为一个数组元素确定其排序最终正确位置(一次就定位准,下次循环就不考虑这个元素了)。
相关推荐
根据给定文件中的标题“Java排序代码大全”以及描述与标签中的关键词如“Java排序”、“排序大全”和“算法”,本文将详细解读文件中所包含的几种排序算法的实现方式,并结合具体代码进行深入分析。 ### 快速排序...
根据给定的信息,本文将详细介绍几种经典的Java排序算法:冒泡排序、插入排序以及选择排序。 ### 冒泡排序 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果它们的顺序错误就把...
在Java中实现这些算法,通常会涉及以下几个步骤: 1. **数据结构**:定义一个结构来存储磁盘请求,包括请求的扇区号、到达时间等信息。 2. **排序**:根据不同的调度算法对请求进行排序。 3. **模拟磁头移动**:计算...
以下是对KNN算法、UCI数据集以及Java实现的详细解析。 **KNN算法详解** KNN算法的基本思想是:对于给定的未知类别数据点,我们将其特征与训练集中已知类别的数据点进行比较,找出与其最相似的K个数据点(即K个最近...
通常,实现包括以下几个关键部分: 1. 初始化数据结构,如优先队列和距离数组。 2. 主循环,不断从优先队列中取出节点并更新邻接节点。 3. 更新节点状态,将已访问过的节点从队列中移除。 4. 返回最短路径信息,如...
根据提供的文件内容,本文将对JAVA算法题目集中的几个关键知识点进行详细解读。 1. 排列组合(Permutation & Combination)算法实现 文档中出现的`comb(int m, int k)`函数即为组合数学中的组合算法实现,用于计算...
Compare-and-Swap (CAS) 是一种常用的原子操作,用于实现无锁算法。它通过比较预期值与当前值是否一致来决定是否更新变量的值。然而,CAS存在ABA问题,即当一个值由A变为B然后再变回A时,CAS无法检测到中间的变化。...
本篇文章将围绕"Javapunch"这个Java编程的拳击游戏,详细解读其背后的源码,旨在帮助读者理解游戏开发的核心原理,以及在Java语言中的应用实践。 首先,"JAVA源码"标签表明我们将关注的是用Java编程语言编写的程序...
【JAVA拼图游戏源代码】是一个基于Java编程语言开发的项目,主要展示了如何利用Java进行图形用户界面(GUI)的设计和拼图游戏的算法实现。这个项目对于学习Java编程、图形界面设计以及算法应用有着很好的实践价值。...
- 快速排序是一种分而治之的排序算法,通过选取一个“基准”将数组分为两部分,一部分比基准小,另一部分比基准大,然后递归地对这两部分继续进行排序。 4. **Overload和Override的区别。Overloaded的方法是否可以...
接下来将针对实验报告中的几个核心知识点进行详细解读: ### 一、Java开发环境的搭建 #### 1. 安装JDK JDK(Java Development Kit)是Java开发工具包,它包含了编译、运行Java程序所需的各种工具。安装JDK的具体...
这份名为《整理的Java-EE面试总结.pdf》的文档是一份关于Java基础面试知识点的总结,内容涉及了多个在面试中常见的问题和概念,以及它们的区别和使用场景。根据提供的文件信息,下面将详细解读其中的关键知识点。 ...
下面我们将对这几个部分进行详细的分析和解读: 一、设计内容及要求 在设计内容及要求部分,本文首先提出了设计任务和要求,包括硬件可靠性、系统运行的稳定性、系统功能齐全、开放性好等几个方面。这几个要求都是...
5. **程序实现**:如果文件包含源代码,那么我们可以看到如何将理论算法转化为实际的编程语言,例如Python、Java或C++。这有助于我们理解算法的运行流程,并为自己的项目提供参考。 6. **性能评估**:最后,文件...
【部分内容解读】:由于没有提供具体题目内容,无法详细解析,但根据一般的Java笔试题型,我们可以预计会包括以下几个方面: 1. **Java基础**:这部分可能包含Java语法、变量、常量、运算符、流程控制语句(如if-...
3. **排序**:排序算法是另一个常见主题,包括快速排序、归并排序、插入排序等,它们在处理大量数据时非常有用。了解不同排序算法的效率和适用场景是必要的。 4. **算法设计**:在面对复杂问题时,开发者需要设计...