排序 - 选择排序（2）

逃离我推掉我的手 2022-01-10 00:07 166阅读 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