排序算法——选择排序系列及性能测试

一时失言乱红尘 2022-10-22 15:55 194阅读 0赞

### 文章目录 ###

*   *   *  初识选择排序
         *  优化思路
         *   *  思路一
             *  思路二（堆排序）
         *  性能测试
         *  扩展：堆排序的应用
         *   *  Top K问题
             *  优先级队列

### 初识选择排序 ###

选择排序是一种和冒泡排序一样简单的排序算法。它的思想非常简单，假设数组大小为n，每次从数组的待排序部分中选出一个最小的元素，放到数组最左侧，n轮筛选后，数组就整体有序了。

图解如下

假设准备对如下数组进行选择排序

![ddbc6ad87ca620840d2b9f7d285280d0.png][]

先对数组的待排序部分进行遍历，选出最小的元素为1，将1放到数组最左侧

![76103cadd7b18dc66e4d0ce5fdedea1a.png][]

第二轮，对剩下的部分进行遍历，选出最小的元素为2，将2放到最左侧（和4交换）

![35b35eadc8b8d460d954f43e92300c39.png][]

如此以来，第三轮选出的元素是3，第四轮选出的是4…经过9轮选择后，数组整体有序  
![027b0d1a9d7ac8f0c3463c0ef5d32741.png][]

它的代码实现也非常简单

public void selectSort(int[] array) { 
    		for (int i = 0; i < array.length; i++) { 
    			int minPos = i;
    			for (int j = i + 1; j < array.length; j++) { 
    				if (array[minPos] > array[j]) { 
    					minPos = j;
    				}
    			}
    			swap(array, i, minPos);
    		}
    	}

### 优化思路 ###

#### 思路一 ####

**双向选择**

选择排序的优化思路比较有限，根据双向冒泡的优化经验，我们可以一轮遍历选出一个最大值和一个最小值，从而提高筛选的效率。

写成代码如下

public void selectSortDual(int[] array) { 
    		int leftBorder = 0;
    		int rightBorder = array.length - 1;
    		while (leftBorder < rightBorder) { 
    			int minPos = leftBorder;
    			int maxPos = leftBorder;
    			for (int j = leftBorder + 1; j <= rightBorder; j++) { 
    				if (array[minPos] > array[j]) { 
    					minPos = j;
    				}
    				if (array[maxPos] < array[j]) { 
    					maxPos = j;
    				}
    			}
    			swap(array, leftBorder, minPos);
                /* 下面的交换要注意，若恰好maxPos等于leftBorder，由于上面已经将leftBorder下标的元素交换到minPos了 */
    			if (maxPos == leftBorder) { 
    				/* 若恰好maxPos为leftBorder，则下面对maxPos的交换要与minPos进行 */
    				swap(array, rightBorder, minPos);
    			} else { 
    				swap(array, rightBorder, maxPos);
    			}
    			leftBorder++;
    			rightBorder--;
    		}
    	}

#### 思路二（堆排序） ####

**堆排序**

其实，堆排序也是选择排序的一个变种。堆排序需要先对数组进行建堆（大顶堆或小顶堆），然后每次将堆顶元素和堆尾元素进行交换，随后将堆尾元素在逻辑上从堆中剔除，对剩余部分的堆进行调整，再将堆顶元素和当前堆尾元素交换，以此类推。每一轮排序都会将堆顶元素追加到数组末端的有序序列中，而**堆顶元素就是每一轮选出来的最大或最小值**，所以堆排序也属于选择排序。

首先对堆进行一个简单的介绍。堆的本质就是一棵完全二叉树。而大顶堆，指的是堆顶元素（二叉树的根节点）要大于其左右子树的任意节点，而其余的每个非叶子节点的值，也要大于其左右子树的任意节点。下图即是一个大顶堆的逻辑结构图

![17f5ca95d8262b5612230d63a2d5c5d8.png][]

可以看到堆顶元素9要大于其左右子节点8和7，节点8要大于其左右子节点4和3，7要大于其左右子节点5和6，4要大于其左右子节点1和2。这就使得堆顶元素是最大的元素。而二叉堆在实际使用中，常常以数组的形式进行存储，如下所示

![47153500fdad0345a0df2d5b227a1c73.png][]

紫色的数字表示元素在数组中的下标。堆从第一层开始，每一层从左往右编号，即是其在数组中存储的位置。容易得到如下的关系：

若堆中的一个节点在数组中的下标为n，若其有左右子节点，则

左子节点的下标为：2n + 1

右子节点的下标为：2n + 2

若其有父节点，则父节点的下标为：(n - 1) / 2

既然堆可以用数组的形式进行存储和表示，那么就可以对数组进行建堆，然后执行堆排序。堆排序的关键在于对初始数组进行**建堆**，以及交换了堆顶元素和堆尾元素后的**调整**

图解如下

假设准备对如下数组进行堆排序

![40efde7d572cc97d743024e91d99605b.png][]

先进行建堆操作（建大顶堆），根据数组，先将数组看成一个二叉树  
![d1d0c2b8932e2292ca15832699e6cad4.png][]

建堆的过程如下：从下往上，先找到第一个非叶子节点（没有任何子节点的节点，上图就是8），从这个节点开始，对所有非叶子节点依次进行**下沉处理**（向下调整）。下沉指的是，将节点与其子节点进行比较，若节点的值小于子节点中的较大者，则交换之。处理节点8，先把节点8及其子节点看成一个堆（局部堆），调整，以使这个局部堆满足大顶堆的特性。发现节点8不需要处理。

接着往前处理，到节点2，发现它比它的子节点要小，而子节点中的较大者是9，则交换2和9

![5e177f4816d00abfeff75d8e44dc2e61.png][]

接着处理节点4，发现它小于8，则交换它和8

![95714f5299605b61d69c8c12de241bf9.png][]

注意下沉处理要下沉到尽可能底部的位置，4和8交换完后，继续处理4，发现4比它的子节点6要小，则交换4和6

![c6c75c6704fa24dde34278b48197c27e.png][]

接着处理1，发现1小于9，则交换之

![145eb4b876429bded22e7452d5b78e45.png][]

继续处理1，发现1小于7，交换之

![34d7b27379989780fc6197d06e4e552a.png][]

如此以来，建堆操作完成，观察可知，现在的堆已经符合大顶堆的特性

建堆完毕后，执行如下操作：将堆顶元素和堆尾元素交换，然后将堆尾元素在逻辑上从堆中删除，将剩余元素看成一个堆，对堆顶元素进行向下调整，使其成为一个大顶堆。然后又将堆顶元素和当前堆的堆尾元素交换，把堆尾元素从堆中删除，对剩余元素继续调整…如此，即完成排序。

图解如下

首先，建堆完毕后的数组状态如下

![32f263976633878254dd49082410b789.png][]

将堆顶元素和堆尾元素交换，即9和4交换

![fe48a9145314b516652771f9dec1f047.png][]

交换完毕后，将堆尾元素9在逻辑上从堆中删除。而剩余元素组成的堆，由于堆顶发生了变化，显然不满足大顶堆的性质，于是对新的堆顶进行向下调整

节点4比其子节点中的较大者8，要小，于是交换之

!![edb934adba16740b540f6a552394fc84.png][]

继续调整节点4，发现其比子节点6要小，则交换之

![d120d12d45739e27941050ccfe27bd1c.png][]

继续调整节点4，发现其只有一个左子节点3，且4大于3，则调整完毕（节点9已经在逻辑上从堆中移除，即堆中不再包含节点9）

剩余的元素组成的堆已符合大顶堆的性质

![999c644defcb9cc578f46bff7a17c946.png][]

接着，继续将堆顶元素和当前堆的堆尾元素交换，即交换8和3

![3be4f57247ef2e9a9c8e7725cd9dac14.png][]

然后将节点8从堆中剔除掉，对当前堆顶元素3进行向下调整，发现只需要交换3和7，调整完毕后结果为

![027e2acbfbac692b03dd2c19494a3519.png][]

接着交换堆顶和堆尾，即交换7和2

![ab8c8722c14b2dea97454896a8c0b11e.png][]

调整堆

![24941b1bb61f76b3effb2198319fef11.png][]

交换堆顶和堆尾

![2e9ff294dcaeaae963ed4321244e3ed3.png][]

调整堆

![ef9cfc05f6f85ba9a4db03456495a14a.png][]

…以此类推，最终数组有序

![ef56db87745eccec9aa220764ed1a1ae.png][]

由此可见，堆排序的关键在于**建堆**，以及对节点的**向下调整**

写成代码如下

public void heapSort(int[] array) { 
    		/* 先进行建堆 */
    		buildHeap(array);
    		/* 后执行循环 */
    		for (int i = array.length - 1; i >= 0 ; i--) { 
    			/* 将堆顶元素和当前堆尾元素交换 */
    			swap(array, 0, i);
    			/* 调整堆 */
    			adjustDown(array, 0, i - 1);
    		}
    	}
    
    	/** * 对数组进行建堆 * **/
    	private void buildHeap(int[] array) { 
    		/* 从数组最右侧往左，即从堆的最下面往上，找到第一个非叶子节点, 对其进行向下调整 */
    		/* 第一个非叶子节点，也就是最后一个节点的父节点 */
    		/* 第一个非叶子节点之前的所有节点，都是非叶子节点了，都需要依次进行向下调整 */
    		int firstNonLeafNode = (array.length - 1) / 2;
    		for (int i = firstNonLeafNode; i >= 0 ; i--) { 
    			/* 对每个非叶子节点，进行向下调整 */
    			adjustDown(array, i, array.length - 1);
    		}
    	}
    
    	/** * 对某个节点，进行向下调整 * @param targetPos 待调整的节点(数组下标) * @param end 堆的终止位置(数组下标) * @param array 堆的数组表示 * **/
    	private void adjustDown(int[] array, int targetPos, int end) { 
    		int leftSonPos;
    		/* 当左儿子没有超出堆的范围时，执行循环 */
    		while ((leftSonPos = 2 * targetPos + 1) <= end) { 
    			/* 若右儿子存在，则选出左右儿子中较大者，否则则选左儿子 */
    			int maxSonPos = leftSonPos + 1 <= end ?
    					array[leftSonPos] > array[leftSonPos + 1] ? leftSonPos : leftSonPos + 1
    					: leftSonPos;
    			if (array[maxSonPos] > array[targetPos]) { 
    				swap(array, maxSonPos, targetPos);
    				targetPos = maxSonPos;
    			} else { 
    				/* 子儿子没有比target大的, 则调整结束 */
    				break;
    			}
    		}
    	}

注意，向下调整的过程，就是将需要调整的节点，下沉到合适的位置，考虑到先前插入排序时的优化，这里也可以采用单向赋值的方式，以避免频繁交换造成的性能开销。

### 性能测试 ###

对选择排序系列的算法进行性能测试，结果如下

![e992d68865059c4da805b63d0ca526ca.png][]

可见堆排序的性能完爆简单选择排序

### 扩展：堆排序的应用 ###

#### Top K问题 ####

**从海量数据中筛选出前K个最大的数据**

因为数据量特别大，对全部数据进行排序再取前K个数显然是不现实的，并且第K个以后的数是没有必要进行排序的，对K以后的数据进行排序显然浪费了性能。我们观察一下堆排序的性质，发现一个特点，无论大顶堆小顶堆，堆顶的元素总是最大的，或者最小的。如果一个大顶堆有K个元素，则堆顶的元素是这K个中最大的；如果一个小顶堆有K个元素，则堆顶的元素是这K个中最小的。那么假设一共有100个数据，要求找出前K个最大的数，可以这样想，我先取前K个元素，我只要知道当前这K个元素中最小的值，之后每次取一个新的元素，拿新元素和这个最小值比，若新元素小于这个最小值，说明新元素小于这所有的K个元素，则新元素不可能是前K个最大的数，直接抛弃之。若新元素比这个最小值大，那么把最小值剔除，换上这个新元素，再选出当前K个元素的最小值等待后续的比较。根据这个思路，只需要构建一个大小为K的小顶堆。先从海量数据中取前K个数，构建一个小顶堆。然后对K之后数，进行遍历，每次取一个数，和小顶堆的堆顶比较，若小于堆顶，则直接丢弃；若大于堆顶，则将该数和堆顶交换，并向下调整堆，维持其小顶堆的特征。因为只需要和堆顶这一个元素比较，并且小于堆顶的情况直接丢弃，只有大于堆顶的情况才需要调整堆，所以使得能够以较高的效率找到前K个最大的数，代码实现如下

/** * @param array 待查找的数组 * @param k 找到前K个最小的数 * **/
    	public int[] findTheSmallestElements(int[] array, int k) { 
    		return findTheMostElements(array, k, false);
    	}
    
    
    	/** * @param array 待查找的数组 * @param k 找到前K个最大的数 * **/
    	public int[] findTheBiggestElements(int[] array, int k) { 
    		return findTheMostElements(array, k, true);
    	}
    
    	/** * 找出前K个最大的，或者前K个最小的数 * @param biggest 是否是找最大的 * **/
    	private int[] findTheMostElements(int[] array, int k, boolean biggest) { 
    
    		/* 找前K个最大的，则要建小顶堆; 找前K个最小的, 则要建大顶堆 * false 表示小顶堆 * true 表示大顶堆 * */
    		boolean heapType = !biggest;
    
    		/* 对前k个元素，建堆 */
    		buildHeap(array,k - 1, heapType);
    		/* 从第 k + 1 个元素 (下标为k) 开始遍历 */
    		for (int i = k; i < array.length; i++) { 
                /* 当前元素是否需要插入到前k个元素组成的堆中 */
    			boolean needInsert = biggest ? array[i] > array[0] : array[i] < array[0];
    			if (needInsert) { 
    				/* 若需要插入，则插入堆 */
    				swap(array, 0, i);
    				/* 调整堆，使其仍然是小顶堆/大顶堆 */
    				adjustDown(array, 0, k - 1, heapType);
    			}
    			/* 否则,直接抛弃 */
    		}
    		int[] topKElements = new int[k];
            /* 取array数组的前k个元素,作为结果 */
    		System.arraycopy(array, 0, topKElements, 0, k);
    		return topKElements;
    	}
    
    	/** * @param endPos 建堆的终止位置 * @param biggestTop 是否建大顶堆 * **/
    	private void buildHeap(int[] array,int endPos, boolean biggestTop) { 
    		int firstNonLeafPos = (endPos - 1) / 2;
    		for (int i = firstNonLeafPos; i >= 0 ; i--) { 
    			adjustDown(array, i, endPos, biggestTop);
    		}
    	}
    
    	/** * @param biggestTop 是否建大顶堆 * **/
    	private void adjustDown(int[] array, int targetPos, int endPos, boolean biggestTop) { 
    		int leftSonPos;
    		while ((leftSonPos = 2 * targetPos + 1) <= endPos) { 
    			int maxSonPos = leftSonPos, minSonPos = leftSonPos;
    			if (leftSonPos + 1 <= endPos) { 
    				maxSonPos = array[leftSonPos] > array[leftSonPos + 1] ?
    						(minSonPos = leftSonPos + 1) - 1 :
    						leftSonPos + 1;
    			}
    			boolean needSwap = biggestTop ?
    					array[maxSonPos] > array[targetPos] :
    					array[minSonPos] < array[targetPos];
    			int swapPos = biggestTop ? maxSonPos : minSonPos;
    			if (needSwap) { 
    				swap(array, targetPos, swapPos);
    				targetPos = swapPos;
    			} else { 
    				break;
    			}
    		}
    	}

#### 优先级队列 ####

队列在生活中随处可见。坐地铁时排队等车，在食堂排队打饭，去银行办理业务时也要取号排队。队列的本质就是一堆人，需要执行某个动作。最简单普通的队列就是按照先来后到的顺序依次排队，依次接收服务。但在某些场景下需要对排队的人进行一些优先级的设置，比如银行办理业务时，VIP客户的排队优先级就要高于普通客户，再比如，去食堂打饭时，如果有一个人已经10天没吃饭了，马上就要饿死了，是不是应该让他优先打饭，保证他能活过来。这些场景下，普通的队列就太死板了，无法满足需求，于是就有了优先级队列。优先级队列中的元素，不是严格按照先来后到的顺序排队的，而是优先级的高的元素，总是会排到优先级低的元素的前面，优先级相同的元素，再按先来后到的顺序排队。那么堆，这一数据结构，就能够满足这样的需求，因为它总是会把最大的，或者最小的元素，放在堆顶（数组的最前面）。

一个队列有2个基本操作：入队和出队

入队：一个人加入到队列中，进行排队

出队：轮到某个人办事了，将其移出队列

用堆的结构来表示，如下。先来一个优先级为1的人，进行排队

![a8b3c59f036ded0c34a16126ed09a3d2.png][]

随后，来了一个优先级为9的人

![6f7925ed8e56ab53c3274c8c7449468d.png][]

显然不满足大顶堆的性质，则对新来的9，进行调整，此时应该是向上调整，交换1和9即可

![cc7a11affd143026906530a20202312e.png][]

此时又来了一个6，发现仍然满足大顶堆的特性，则不做调整

![b3c3827042148f927472380dfd55c440.png][]

若此时，进行出队，则直接取出堆顶元素，节点9接受服务，数组变成了

![86101c0848a2a304ca027799fef02afb.png][]

对应的堆的逻辑结构就变成了

![88947c39d26706eca55c8c820e6d4318.png][]

发现不满足大顶堆的特性，则进行调整，交换1和6即可

![e9847009205133b7b09914d50a9032d5.png][]

每次出队，都取数组的首元素，即堆顶元素，即能保证每次出队都是当前优先级最高的元素

其核心部分的逻辑为：

*  入队时，新加入的元素追加到数组末尾，也即堆尾，并需要对其进行向上调整，以满足大顶堆的性质。
 *  出队时，移除数组的首元素，将剩余部分元素看成一个新的堆，并重新建堆

在此就不给出具体的代码实现了，有兴趣的读者可以自行尝试

[ddbc6ad87ca620840d2b9f7d285280d0.png]: /images/20221022/2e3c62bf78de4f409cd792a6e4e6db4f.png
[76103cadd7b18dc66e4d0ce5fdedea1a.png]: /images/20221022/ea371d5ebf4246b6a8781298e0db25e1.png
[35b35eadc8b8d460d954f43e92300c39.png]: /images/20221022/78be69d96999426991c998f074b58a0c.png
[027b0d1a9d7ac8f0c3463c0ef5d32741.png]: /images/20221022/c5fc81a0685c47399c434cb65ae16bf4.png
[17f5ca95d8262b5612230d63a2d5c5d8.png]: /images/20221022/503031d56fb34a97823dca9fe55e5ad0.png
[47153500fdad0345a0df2d5b227a1c73.png]: /images/20221022/9327ee3d173e4c6db1e4b11a8e618ada.png
[40efde7d572cc97d743024e91d99605b.png]: /images/20221022/5edf40f3ee4c4eee96f6788cbbbf4449.png
[d1d0c2b8932e2292ca15832699e6cad4.png]: /images/20221022/f43abc775bfb436cbaf386914f283fa3.png
[5e177f4816d00abfeff75d8e44dc2e61.png]: /images/20221022/4164ab5867b4490d8bd989505108d1c2.png
[95714f5299605b61d69c8c12de241bf9.png]: /images/20221022/a088f503fad44b369a19ef51f459b3a6.png
[c6c75c6704fa24dde34278b48197c27e.png]: /images/20221022/42274c37872842eb855578b2117aa188.png
[145eb4b876429bded22e7452d5b78e45.png]: /images/20221022/f91da305de18468fab0ac5571b954cdd.png
[34d7b27379989780fc6197d06e4e552a.png]: /images/20221022/445da45ff6154ee29c67d6d6c721c521.png
[32f263976633878254dd49082410b789.png]: /images/20221022/847cd0dc778648a28ece6bebc1ae197e.png
[fe48a9145314b516652771f9dec1f047.png]: /images/20221022/e4fc079b08d04a16ad1a45691c795274.png
[edb934adba16740b540f6a552394fc84.png]: /images/20221022/7da4e8149b234edd86457cd6b408369b.png
[d120d12d45739e27941050ccfe27bd1c.png]: /images/20221022/ccb4d99866334a2b84ad3e9925035ccd.png
[999c644defcb9cc578f46bff7a17c946.png]: /images/20221022/e409b60cb5f747248473f29549d407d9.png
[3be4f57247ef2e9a9c8e7725cd9dac14.png]: /images/20221022/75741c0d3d51435a95d5caa087d163dd.png
[027e2acbfbac692b03dd2c19494a3519.png]: /images/20221022/1513c741a9474cf286db661e796bb530.png
[ab8c8722c14b2dea97454896a8c0b11e.png]: /images/20221022/9b2d909b2b1f484c97502731dc68a9df.png
[24941b1bb61f76b3effb2198319fef11.png]: /images/20221022/3d5ba559182443f287cc6fb59e80acb9.png
[2e9ff294dcaeaae963ed4321244e3ed3.png]: /images/20221022/4c11630fdc8240b6b2f20310686b70a9.png
[ef9cfc05f6f85ba9a4db03456495a14a.png]: /images/20221022/c5f2a13b830b4fdb858e9b7fbc5f241a.png
[ef56db87745eccec9aa220764ed1a1ae.png]: /images/20221022/3b6e2274b0f24c0baa8f72ce029508b3.png
[e992d68865059c4da805b63d0ca526ca.png]: /images/20221022/909ee77a371b4c339ba506307950ff28.png
[a8b3c59f036ded0c34a16126ed09a3d2.png]: /images/20221022/e226124e372a46509a444927a8a72a6a.png
[6f7925ed8e56ab53c3274c8c7449468d.png]: /images/20221022/7bf1ea0578f541e794b75658cb1496b6.png
[cc7a11affd143026906530a20202312e.png]: /images/20221022/a8bdde7a80734a79aba4e72baa1b04c4.png
[b3c3827042148f927472380dfd55c440.png]: /images/20221022/c4d3adfa86774adfbfd2fa73fc7e7e44.png
[86101c0848a2a304ca027799fef02afb.png]: /images/20221022/6c0e6ab963464250a05f33a28eea4d97.png
[88947c39d26706eca55c8c820e6d4318.png]: /images/20221022/04b3e25cf27f49fb88f6d97f0a221f50.png
[e9847009205133b7b09914d50a9032d5.png]: /images/20221022/f991a33abf3444efbe5b654c9510b20a.png