1、选择排序的基本思想
将排序序列分为有序区和无序区，每一趟排序从无序区中选出最小的元素放在有序区的最后，从而扩大有序区，直到全部元素有序为止。
一、直接选择排序
1、基本思想
第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
可以通过看下面GIF来简单了解直接选择排序的过程：
2、代码
import java.util.Arrays; public class 简单选择排序 { public static void selectSort(int[] arr){ //防止arr数组为空或者arr只有一个数，不用进行排序 if (arr == null || arr.length < 2) { return; } /*每次要进行比较的两个数，的前面那个数的下标*/ for (int i = 0; i < arr.length - 1; i++) { //min变量保存该趟比较过程中，最小元素所对应的索引， //先假设前面的元素为最小元素 int min = i; /*每趟比较，将前面的元素与其后的元素逐个比较*/ for (int j = i + 1; j < arr.length; j++) { //如果后面的元素小，将后面元素的索引极为最小值的索引 if(arr[j] < arr[min]) { min = j; } } //然后交换此次查找到的最小值和原始的最小值 swap(arr, i, min); } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr={9, 8, 6, 29, 10, 7, 37, 48}; selectSort(arr); System.out.println(Arrays.toString(arr)); } }
3、代码优化
选择排序的优化引入的二分的思想，前面是找到最小的值往前面放，现在在一趟循环中同时找到最大最小值，将最小值放入头，最大值放入尾。
import java.util.Arrays; public class 简单选择排序二分 { public static void SelectSort(int[] arr){ // find the max and min num in an iteration int n = arr.length; for(int i = 0;i<n;i++){ int min = i; int max = n-1; for(int j = i;j<n;j++){ if (arr[j]<arr[min]){ min = j; } if (arr[j]>arr[max]){ max = j; } } swap(arr,i,min); // 防止i的位置为最大值，然后被最小值换了，所以检查一下 if (max == i){ max = min; } swap(arr,n-1,max); n = n-1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr={9, 8, 6, 29, 10, 7, 37, 48}; SelectSort(arr); System.out.println(Arrays.toString(arr)); } }
4、总结
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：在插入排序中，当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n- 1次，时间复杂度为O(n)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n^2)。平均来说，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是O(n^2)。空间复杂度：O(1)
- 稳定性：不稳定，因为排序序列为（5，5，1）,第一趟排序之后（1，5，5），这可以很清楚的看到两个5的相对位置发生了变化。
- 适用场景： 待排序序列的元素个数不多，且元素基本有序。
二、堆排序
1、堆
堆一般指的是二叉堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆总是满足下列性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值；（即k ᵢ <=k₂ᵢ 且kᵢ<=k₂ᵢ₊₁为小根堆，kᵢ>k₂ᵢ且kᵢ>=k₂ᵢ₊₁为大根堆）
- 堆总是一棵完全二叉树。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
可以看下面小根堆建立的GIF简单了解堆排序的的过程
2、基本思想
堆排序是简单选择排序的改进，利用二叉树代替简单选择方法来找最大或者最小值，属于一种树形选择排序方法。
利用大根堆(小根堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大值(最小值)变得简单。
- 将待排序的序列构造成一个大根堆，此时序列的最大值为根节点
- 依次将根节点与待排序序列的最后一个元素交换
- 再维护从根节点到该元素的前一个节点为大根堆，如此往复，最终得到一个递增序列
3、堆的存储方式
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节
点，就会导致空间利用率比较低。
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
4、堆的shift up和shift down
Ⅰ、shift up：向一个最大堆中添加元素
如下面向堆中加入一个新元素52，这时需要重新调整为大根堆，52比它的父节点28大，需要交换，然后和28的父节点（41）比较，还是更大也需要交换。
Ⅱ、shift down：从一个最大堆中取出一个元素只能取出最大优先级的元素，也就是根节点
如果上面那个堆的62变成了12，这时候为了维持大根堆，只能将12这个节点进行shift down操作以维持大根堆
5、堆的插入与删除
Ⅰ、插入
堆的插入总共需要两个步骤：
- 先将元素放入到底层空间中(注意：空间不够时需要扩容)
- 将最后新插入的节点向上调整，直到满足堆的性质
其实这就是shift up操作
Ⅱ、删除
注意：堆的删除一定删除的是堆顶元素（因为 二叉堆不支持查找元素位置，因此删除一个你完全不知道内容的元素毫无意义 ）。具体如下：
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整（小根堆为例）
调整之后
6、建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
第1层，2^0个节点，需要向下移动h-1层
第2层，2^1个节点，需要向下移动h-2层
第3层，2^2个节点，需要向下移动h-3层
第4层，2^3个节点，需要向下移动h-4层
........................
第h-1层，h-2个节点，需要向下移动1层
7、代码（建大根堆小根堆，入队出队）
package 选择排序; import java.util.Arrays; public class Main { public static int[] elem; public static int usedSize;//当前堆当中的有效的元素的数据个数 /** * 建堆:【大根堆】 * 时间复杂度：O(n) */ public static void createHeap() { for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) { shiftDown(parent,usedSize); } } /** * 实现 向下调整 * @param parent 每棵子树的根节点的下标 * @param len 每棵子树的结束位置 */ private static void shiftDown(int parent, int len) { int child = 2 * parent + 1; //最起码是有左孩子 while (child < len) { //判断 左孩子 和 右孩子 谁最大,前提是 必须有 右孩子 if(child+1 < len && elem[child] < elem[child+1]) { child++;//此时 保存了最大值的下标 } if(elem[child] > elem[parent]) { swap(elem,child,parent); parent = child; child = 2*parent+1; }else { break; } } } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * 入队 * @param x */ public void offer(int x) { if(isFull()) { elem = Arrays.copyOf(elem,elem.length*2); } this.elem[usedSize] = x; usedSize++; shiftUp(usedSize-1); } /** * 实现 向上调整 * @param child 需要向上调整的子树的下标 */ private void shiftUp(int child) { int parent = (child-1) / 2; while (child > 0) { if(elem[child] > elem[parent]) { swap(elem,child,parent); child = parent; parent = (child-1) / 2; }else { break; } } } public boolean isFull() { return usedSize == elem.length; } /** * 出队 */ public int poll() { if(isEmpty()) { return -1; } int old = elem[0]; swap(elem,0,usedSize-1); usedSize--; shiftDown(0,usedSize); return old; } /* 判断是否为空 */ public boolean isEmpty() { return usedSize == 0; } /** *建立小根堆 */ public static void heapSort() { int end = usedSize - 1; while (end > 0) { swap(elem,0,end); shiftDown(0,end); end--; } } public static void main(String[] args) { elem = new int[]{5,4,10,16,1,8,9,48,18,17}; usedSize = elem.length; createHeap();//建立小根堆，先建立大根堆，然后将最大值放入堆尾，建立小根堆 heapSort(); System.out.println(Arrays.toString(elem)); //[1, 4, 5, 8, 9, 10, 16, 17, 18, 48] createHeap();//建立大根堆 System.out.println(Arrays.toString(elem)); //[48, 18, 16, 17, 9, 10, 5, 1, 8, 4] } }
8、总结
- 堆排序使用堆来选数，相比直接选择排序效率就高了很多。堆排序中每一趟都有元素归位了
- 时间复杂度：最好/最环/平均时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用场景：元素较多的情况，因为建初始堆的所需的比较次数比较多，所以堆排序不适合元素较少的情况。
