图解"数据结构--内部排序算法"----选择排序：直接选择排序、堆排序

╰半夏微凉° 2022-05-18 02:48 553阅读 0赞

#     #

# 一、选择排序(Selection Sort)的基本思想 #

每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

# ![1351558208_1942.jpg][]    #

#     #

# 二、选择排序分类 #

本文介绍两种选择排序：直接选择排序、堆排序。

## 2.1 直接选择排序 ##

##  ##

###         2.1.1 直接选择排序的基本思想 ###

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

**① 始状态**

无序区为R\[1..n\]，有序区为空。

**②第1趟排序**

> > > 在无序区R\[1..n\]中选出关键字最小的记录R\[k\]，将它与无序区的第1个记录R\[1\]交换，使R\[1..1\]和R\[2..n\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

**③第i趟排序**

> > > 　　第i趟排序开始时，当前有序区和无序区分别为R\[1..i-1\]和R\[i..n\](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R\[k\]，将它与无序区的第1个记录R\[i\]交换，使R\[1..i\]和R\[i+1..n\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

### **2.1.2 举例说明"直接选择排序的排序过程"** ###

**待排序列(45,38,65,97,76,13,27,49')，从小到大进行排序**

![1351558820_5220.jpg][]

> >   
> > 
> > 
> > 假设我们有一个没有排好序的序列，那么首先我们选择序列中的最小元素(13),放在首位置；再选择第2小的元素放在最小元素的后面；依次重复，直到序列从小到大排成一列。
> > 
> >   
> >

## 2.2 堆排序 ##

### 2.2.1 堆排序的基本思想 ###

> >     将待排序的数组构造成一个大顶堆，从而获得数组最大的元素，即当前的根节点。将其移走之后，再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行，最后得到一个有序序列。 
> > 
> > ![1351558566_5328.jpg][]  
> >

> > ### **2.2.2 堆排序的过程** ###

> > ① 循环处理元素构造大顶堆
> 
> > ② 获取堆顶元素并和最后一个叶节点交换位置
> 
> > ③ 重新构建大顶堆，元素个数减一（除去最后一个叶节点，即选出的最大值）。
> 
> > ④ 循环第2、3个步骤。
> > 
> >   
> > 
> > 
> > ### **2.2.3 举例说明"堆排序的排序过程"---以"大根堆为例"** ###
> > 
> >   
> > 
> > 
> >    **堆**分为**大根堆**和**小根堆**，是**完全二叉树**。大根堆的要求是每个**节点的值**都不大于**其父节点的值****。**在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
> > 
> > **1.建堆过程**
> > 
> >     既然是**堆排序**，自然需要先建立一个堆，而建堆的核心内容是**调整堆**，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。调堆的过程应该从**最后一个非叶子节点**开始，假设有数组A = \{1, 3, 4, 5, 7, 2, 6, 8, 0\}。那么调堆的过程如下图，数组下标从0开始，调堆从A\[3\] = 5开始。分别与左孩子和右孩子比较大小，如果A\[3\]最大，则不用调整，否则和孩子中的值最大的一个交换位置，在图1中是A\[7\] > A\[3\] > A\[8\]，所以A\[3\]与A\[7\]对换，从图1.1转到图1.2。
> > 
> >     依次转换，最后建立的堆为 图1.8.
> > 
> > ![1351559632_2412.jpg][]
> > 
> >   
> > 
> > 
> >   
> > 
> > 
> > **2.调堆过程**
> > 
> >     如果初始数组是非降序排序，那么就不需要调堆，直接就满足堆的定义，此为最好情况，运行时间为Θ(1)；如果初始数组是如图1.5，只有A\[0\] = 1不满足堆的定义，经过与子节点的比较调整到图1.6，但是图1.6仍然不满足堆的定义，所以要递归调整，一直到满足堆的定义或者到堆底为止。如果递归调堆到堆底才结束，那么是最坏情况，运行时间为O(h) (h为需要调整的节点的高度，堆底高度为0，堆顶高度为floor(logn) )。
> > 
> > **建堆完成之后**，堆如图1.7是个大根堆。将A\[0\] = 8 与 A\[heapLen-1\]交换,然后heapLen减一，如图2.1，然后AdjustHeap(A, heapLen-1, 0)，如图2.2。如此交换堆的第一个元素和堆的最后一个元素，然后堆的大小heapLen减一，对堆的大小为heapLen的堆进行调堆，如此循环，直到heapLen == 1时停止，最后得出结果如图3。
> > 
> > ![1351560931_9236.jpg][]  
> > 
> > 
> >   
> >

[1351558208_1942.jpg]: https://img-my.csdn.net/uploads/201210/30/1351558208_1942.jpg
[1351558820_5220.jpg]: https://img-my.csdn.net/uploads/201210/30/1351558820_5220.jpg
[1351558566_5328.jpg]: https://img-my.csdn.net/uploads/201210/30/1351558566_5328.jpg
[1351559632_2412.jpg]: https://img-my.csdn.net/uploads/201210/30/1351559632_2412.jpg
[1351560931_9236.jpg]: https://img-my.csdn.net/uploads/201210/30/1351560931_9236.jpg