排序 - 选择排序（2） 逃离我推掉我的手 2022-01-10 00:07 141阅读 0赞 ### 概念 ### 选择排序（Selection sort）是一种简单直观的[排序算法][Link 1]。它的工作原理是每一次从待排序的[数据元素][Link 2]中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 ## ## ### 分类 ### 简单选择排序和堆排序 ## ## ### 简单选择排序 ### **算法思想** 每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。 **排序演示** ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70][] **实现代码** public static void selectSort(int[] a) { if((a == null) || (a.length == 0)) return ; for(int i = 0;i < a.length - 1;i ++){ int minIndex = i; // 无序区的最小数据数组下标 for(int j = i + 1;j < a.length;j ++){ // 在无序区中找到最小数据并保存其数组下标 if(a[j] < a[minIndex]){ minIndex = j; } } // 将最小元素放到本次循环的前端 int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } //第二种 public static void sort(int[] array) { for(int i=0;i<array.length;i++) { int min=array[i]; for(int m=1+i;m<array.length;m++) { if(array[m]<min) { array[i]=array[m]; array[m]=min; min=array[i]; } } } } **算法分析** 1. **时间复杂度** 选择排序的复杂度分析。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。 共比较的次数是 `(N - 1) + (N - 2) + ... + 1`，求等差数列和，得 `(N - 1 + 1)* N / 2 = N^2 / 2`。 舍去最高项系数，其时间复杂度为 O(n²)。 2. **空间复杂度** 不需要额外的空间O(1) 3. **稳定性** 选择排序是不稳定的，例如，对n=3的键值序列为\{2,2,1\}，经过排序后，前后两个2的位置颠倒了。 用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。 不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。 首先，选择排序是不稳定的。在《算法》第四版217页上作者已经说了，**有很多办法可以将任意排序算法变成稳定的，但是，往往需要额外的时间或者空间**。 ### 堆排序 ### **概念** **堆排序**（英语：Heapsort）是指利用[堆][Link 3]这种数据结构所设计的一种[排序算法][Link 4]。堆是一个近似[完全二叉树][Link 5]的结构，并同时满足**堆积的性质**：即子结点的键值或索引总是小于（或者大于）它的父节点。 1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； **堆的操作** 在堆的[数据结构][Link 6]中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作： 1. 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 2. 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序 3. 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的[递归][Link 7]运算 **基本思想（大顶堆）** 1. 创建一个堆 H\[0……n-1\]； 2. 把堆首（最大值）和堆尾互换； 3. 把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置； 4. 重复步骤 2，直到堆的尺寸为 1。 **实现代码** public static void heapSort(int[] arr) { //每建堆一次就出堆顶元素一次 for(int i=arr.length-1;i>0;i--) { //1.建大顶堆 buildHeap(arr,i); //2.堆顶元素出队 swap(arr,i); } } private static void buildHeap(int[] arr,int max) { for(int j=(max-1)/2;j>=0;j--){ int temp=arr[j]; for(int k=2*j+1;k<=max;k=k*2+1) { if(k+1<=max && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点 k++; } if(arr[k] > temp){//如果子节点大于父节点，将子节点值赋给父节点 arr[j] = arr[k]; j=k; } } arr[j] = temp;//将temp值放到最终的位置 } } private static void swap(int[] arr,int last) { int max=arr[0]; arr[0]=arr[last]; arr[last]=max; } **算法分析** * 时间复杂度 堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，\[log2(n-1),log2(n-2)...1\]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn) * 空间复杂度 O(1) * 算法稳定性 不稳定排序 [Link 1]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605 [Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70]: /images/20220109/082e2a4e177f481ba8f8a2d0be5e01a6.png [Link 3]: https://baike.baidu.com/item/%E5%A0%86 [Link 4]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95 [Link 5]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91 [Link 6]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84 [Link 7]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
还没有评论，来说两句吧...