选择排序（直接选择、堆）

刺骨的言语ヽ痛彻心扉 2023-07-25 09:55 22阅读 0赞

## 简单选择排序 ##

##### 排序策略 #####

**在待排序的数据中选择最小值**

##### 排序过程 #####

以集合\{76，38，85，97，76，13，27，49\}中数据为例，执行排序  
①第一趟，在 0~n 找出最小的数  
![在这里插入图片描述][20200414154158226.png]  
②第二趟，在 1~n 找出最小的数  
![在这里插入图片描述][20200414154236989.png]

# … #

共执行n-1趟，则直至排序完成

##### 实现代码 #####

/**
      * 简单选择排序
      * @param list 需要排序的行列
      * @return 排序的结果
      */
     public static int[] selSort(int[] list) {
      	//最小值索引
      	int index = 0;
      	//交换中间值
      	int mid = 0;
      	for(int i=0; i<list.length-1; i++) {
       		index = i;
       		for(int j=i; j<list.length-1; j++) {
        			if(list[j+1] < list[index]) {
         				index = j+1;
        			}    
    	 	}
      		mid = list[i];
       		list[i] = list[index];
       		list[index] = mid;
      	} 
      	return list;
     }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]

##### 时间及空间复杂度 #####

①时间  
每一趟进行比较的数目都会递减1，且需交换一次（即赋值三次）  
则：最后一趟排序需赋值3次，比较1次，即4  
第一趟排序需赋值3比较n-2次，即n+1  
则T(n) ≈ 4+5+…+n+1 = (n+1)(n+2)/2 - 6

即时间复杂度为：T(n) = n2

②空间  
S(n) = O(1)

③稳定性  
不稳定，由于每次只是将最小的值与第i位值进行交换，有可能会使相对位置发生变化

##### 适用范围 #####

①n较小时

②在n个待排序的数据中选择前k(k<<n)个最小值时

## 堆排序 ##

##### 堆的定义 #####

n 元素的序列 \{ k1， k2 ，…… ， kn \}，满足：  
**①ki >= k2i**  
**②ki >= k2i+1**

该结构类似于一棵完全二叉树，父结点值大于其孩子的值：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]

##### 排序策略 #####

**根据堆的特性，即根结点为值最大的结点，取出根结点，不断的调整堆结构，直至将堆清空，将取得的根结点按倒叙排列，即最终结果**

##### 排序过程 #####

以集合\{49, 38, 65, 97, 76, 13, 27, 49\}中数据为例，执行一趟冒泡排序

**先根据序列中的数据构造堆结构**：  
构造堆的时候，必须从底层（倒数第二层）向上进行构造，这样才可成功将较大结点交换到每个子树的根节点  
设从第i个结点进行，在该集合中初始 i=8/2=4

①从第4个结点判断堆结构是否需要调整：可以发现此时97大于其子结点，所以不需调整  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]

②从第3个结点判断堆结构是否需要调整：可以发现此时65大于其子结点，所以不需调整  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]  
③从第2个结点判断堆结构是否需要调整：可以发现此时38小于于其子结点，所以需要调整：  
即将该结点与其较大的一个子节点进行交换

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]  
此时发现该结点38依旧小于其子结点，所以仍旧需要交换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]  
③从第1个结点判断堆结构是否需要调整：可以发现此时49小于其子结点，所以需要调整：  
即将该结点与其较大的一个子节点进行交换，然后还需再次和子结点交换一次  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]  
**取出堆的根结点（堆中最大的结点），再调整堆结构**  
①取出根结点97，将其与最后一个结点进行交换，脱离堆，再调整堆结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]  
②取出根结点76，将其与倒数第二个结点进行交换，脱离堆，再调整堆结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 8]

# … #

直至n-1个结点从堆结构中提取出来，则排序完成  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 9]

##### 实现代码 #####

调整堆结构函数，此处需要注意，所数据从索引为0开始，则结点 i 左孩子为 2\*i+1

/**
      * 根据堆的特征调整堆的结构
      * @param list 堆中数据
      * @param i 起始位置
      * @param j 结束位置
      */
     private static void adjustHeap(int[] list, int i, int j) {
      	//定位左孩子(由于索引从0开始)
      	int child = 2*i+1;
      	//对起始(当前子树的根)做存储
      	int root = list[i];
     	//若当前结点有孩子,调整结构使得根结点最大
      	while(child <= j) {
       		//判断左右孩子中最大的孩子(前提存在右孩子)
       		if(child+1 <= j && list[child] < list[child+1]) {
        			child++;
       		}
       		if(list[child] > root) {
        			//若孩子大于父亲,进行交换
        			list[i] = list[child];
        			list[child] = root;
        			//此处由于父子结点进行交换,可能交换后的父结点在子树中仍然小于其子节点
        			//所以因再次循环并判断是否要继续进行交换 
        			i = child;
        			child = 2*i;
       		}else {
        			//若孩子小于父亲,说明当前堆平衡,直接跳出循环
        			break;
       		}
      	}
     }

主要排序函数：

/**
      * 堆排序
      * @param list 需要排序的行列
      * @return 排序后的结果
      */
     public static int[] heaSort(int[] list) {
      	//先按照原始数据从倒数第二层构建堆,保证堆的平衡
      	System.out.println("构建堆：");
      	int begin = (list.length-1)/2;
      	for(int i = begin; i >= 0; i--) {
       		adjustHeap(list, i, list.length-1);
       		System.out.println(Arrays.toString(list));
      	}
      	//中间值
      	int mid = 0;
      	//共执行n-1趟
      	System.out.println("调整堆：");
      	for(int j = list.length-1; j > 0; j--) {
       		//将最大值从堆中取出,放于数列结尾
       		mid = list[0];
       		list[0] = list[j];
       		list[j] = mid;
       		//调整堆结构
       		adjustHeap(list, 0, j-1);
       		System.out.println(Arrays.toString(list));
      	}
      	return list;
     }

**测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 10]

##### 时间及空间复杂度 #####

①时间  
由于堆结构是一棵平衡二叉树，即调整函数时间复杂度为O(log2n)  
而建立堆的过程时间复杂度为O(n)

堆排序的时间=建立堆+（n-1)次调整堆

即时间复杂度为：T(n) = nlog2n

②空间  
S(n) = O(1)

③稳定性  
不稳定，因为父子比较及交换是在第i个元素和第2i个元素或第2i+1元素之间进行，即原两个相同大小的记录的位置会有变化。

##### 适用范围 #####

①n较大  
②选取前k(k<<n)个最大元素时

[20200414154158226.png]: /images/20230528/247d328a94c442c89d72b1bb18f33bac.png
[20200414154236989.png]: /images/20230528/0b0fd490f2c04ec88969e0376e59f5ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: /images/20230528/82b3d56b10b0405ea3825ee36ce03669.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: /images/20230528/3f32a537c1fb4792afbd0b99072bb775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: /images/20230528/c66cfe0e834c4fff8ac6e813b5182649.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: /images/20230528/32d5fb91cdaa4eedbb1b97460f871d41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 4]: /images/20230528/dac73a6cc75048df8f19e9378aa0ade4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 5]: /images/20230528/bdbd237adb344046955ebaf9889c5fce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 6]: /images/20230528/b868018aa4794bdfb778d74bea02042f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 7]: /images/20230528/024c45df10ad460d91262bffa3231461.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 8]: /images/20230528/a8de2ca25ba64b2393b66cdf8ecd13a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 9]: /images/20230528/ed0c118d9c9f44fcb9cede1329de52b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 10]: /images/20230528/21a8e97d5687483e99ff851e471c7452.png