排序算法——选择排序（简单选择排序&&堆排序）

淡淡的烟草味﹌ 2022-05-07 18:03 264阅读 0赞

## 简单选择排序： ##

转载：[简单选择排序（直接选择排序）][Link 1]

【基本思想】

每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。  
【特点】

数据结构：数组

稳定性：不稳定  
【过程】

初始关键字：『 8，5，2，6，9，3，1，4，0，7 』

第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

结果：          『 0，1，2，3，4，5，6，7，8，9 』

![SouthEast][]       ![SouthEast 1][]

排序过程           宏观过程

代码：

//直接选择排序
    #include<iostream>
    #include<algorithm> 
    using namespace std;
    
    void select_sort(int a[],int n)
    {
    	int i,j;
    	int tmp;
    	for(i=0;i<n-1;i++)
    	{
    		tmp=i;
    		for(j=i+1;j<n;j++)
    			if(a[tmp]>a[j])
    				tmp=j;		
    		swap(a[i],a[tmp]);
    	}
    }
    
    int main()
    {
    	int a[]={1,8,5,6,9,7,3};
    	int n=sizeof(a)/sizeof(int);
    	
    	select_sort(a,n);
    	
    	for(int i=0;i<n;i++)
    		printf("%d ",a[i]);
    	
    	return 0;
    }

## 堆排序： ##

转载：（原文写的很好）[白话讲排序系列（六） 堆排序（绝对让你明白堆排序！）][Link 2]

开门见山，本文讲述堆排序。

就我自身对于排序的了解来看，其实堆排序是诸多排序中最难写的，光是理解起来都有点费劲，本文旨在于用通俗易懂的话，把堆排序娓娓道来。

下面，开始！

1：堆

毫无疑问，排序两个字没必要去死磕，这里的重点，在于排序的方式，堆排序，就是以堆的形式去排序，毫无疑问，了解堆很重要。

那么，什么是堆呢？

这里，必须引入一个完全二叉树的概念，然后过渡到堆的概念。

![70][]

上图，就是一个完全二叉树，其特点在于：

1.  从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层一个元素，第二层4个，第三层8个，以此类推。
2.  而最后一行的元素，都要紧贴在左边，换句话说，每一行的元素都从最左边开始安放，两个元素之间不能有空闲，具备了这两个特点的树，就是一棵完全二叉树。

那么，完全二叉树与堆有什么关系呢？

我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。

同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。

![70 1][]

如上图，左边就是大根堆；右边则是小根堆，这里必须要注意一点，只要求子节点与父节点的关系，两个节点的大小关系与其左右位置没有任何关系。

明确下大根堆，小根堆的概念，继续说堆排序。

现在对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大根堆，或者小根堆，下面讨论以大根堆为例子。

给定一个列表array=\[16,7,3,20,17,8\]，对其进行堆排序（使用大根堆）。

接下来内容是转载部分，自己绘图功底太差：其中绿色部分为自己的注解。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下

![70 2][]

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。

![70 3][]

4.找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。

在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。

![70 4][]

这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。

牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。

![70 5][]

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。

![70 6][]

b.重新调整结构，使其继续满足堆定义

![70 7][]

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

![70 8][]

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

![70 9][]

下面，附上我的代码，也是从文末链接中模仿过来的，但是亲自敲过一遍，印象深刻。

代码的注释真的是非常详细。

public class HeapSort {
    	public static void main(String[] args) {
    		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
    		// 接下来就是排序的主体逻辑
    		sort(array);
    		System.out.println(Arrays.toString(array));
    	}
     
    	/**
    	 * 
    	 * @description 本方法只有一个参数，那就是待排序的array
    	 * @author yuzhao.yang
    	 * @param
    	 * @return
    	 * @time 2018年3月9日 下午2:24:45
    	 */
    	public static void sort(int[] array) {
    		// 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整
    		// 也就是说，是按照自下而上，每一层都是自右向左来进行调整的
    		// 注意，这里元素的索引是从0开始的
    		// 另一件需要注意的事情，这里的建堆，是用堆调整的方式来做的
    		// 堆调整的逻辑在建堆和后续排序过程中复用的
    		for (int i = array.length / 2 - 1; i >= 0; i--) {
    			adjustHeap(array, i, array.length);
    		}
     
    		// 上述逻辑，建堆结束
    		// 下面，开始排序逻辑
    		for (int j = array.length - 1; j > 0; j--) {
    			// 元素交换
    			// 说是交换，其实质就是把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
    			swap(array, 0, j);
    			// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
    			// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
    			// 而这里，实质上是自上而下，自左向右进行调整的
    			adjustHeap(array, 0, j);
    		}
    	}
     
    	/**
    	 * 
    	 * @description 这里，是整个堆排序最关键的地方，正是因为把这个方法抽取出来，才更好理解了堆排序的精髓，会尽可能仔细讲解
    	 * @author yuzhao.yang
    	 * @param
    	 * @return
    	 * @time 2018年3月9日 下午2:54:38
    	 */
    	public static void adjustHeap(int[] array, int i, int length) {
    		// 先把当前元素取出来，因为当前元素可能要一直移动
    		int temp = array[i];
    		// 可以参照sort中的调用逻辑，在堆建成，且完成第一次交换之后，实质上i=0；也就是说，是从根所在的最小子树开始调整的
    		// 接下来的讲解，都是按照i的初始值为0来讲述的
    		// 这一段很好理解，如果i=0；则k=1；k+1=2
    		// 实质上，就是根节点和其左右子节点记性比较，让k指向这个不超过三个节点的子树中最大的值
    		// 这里，必须要说下为什么k值是跳跃性的。
    		// 首先，举个例子，如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了，
    		// 也就是说，是以本节点的左子节点为根的那棵小的子树
    		// 而如果a[0}<a[2]呢，那就调整a[0]和a[2]的位置，然后继续调整以a[2]为根节点的那棵子树，而且肯定是从左子树开始调整的
    		// 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，直到每一颗小子树都满足大根堆的规律为止
    		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
    			// 让k先指向子节点中最大的节点
    			if (k + 1 < length && array[k] < array[k + 1]) {
    				k++;
    			}
     
    			// 如果发现子节点更大，则进行值的交换
    			if (array[k] > temp) {
    				swap(array, i, k);
    				// 下面就是非常关键的一步了
    				// 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
    				// 所以，循环对子节点所在的树继续进行判断
    				i = k;
    				// 如果不用交换，那么，就直接终止循环了
    			} else {
    				break;
    			}
    		}
    	}
     
    	/**
    	 * 交换元素
    	 * 
    	 * @param arr
    	 * @param a
    	 *            元素的下标
    	 * @param b
    	 *            元素的下标
    	 */
    	public static void swap(int[] arr, int a, int b) {
    		int temp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = temp;
    	}
    }

参考上面的代码，我自己写了一遍。

//堆排序
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    void heap_adjust(int a[],int i,int len)//调整节点i，使得以i为根节点的树为堆 
    {
    	int k,tmp;
    	for(k=2*i+1;k<len;k=2*i+1)//一直向下调整 
    	{
    		tmp=a[i];
    		if(k+1<len&&a[k]<a[k+1])//使得k指向较大的孩子 
    			k++; 
    		if(tmp<a[k])//如果当前节点小于孩子节点
    		{
    			swap(a[i],a[k]); 
    			i=k;
    		} 
    		else//有排序的时候从下向上调整，故后面在没有变动的情况下，默认有序 
    			break;
    	} 
    } 
    
    void heap_sort(int a[],int length)
    {
    	int i,j;
    	
    	/*初始建立大顶堆*/
    	for(i=length/2-1;i>=0;i--)//从最后一个非叶子节点开始，从下向上进行建立 
    	{
    		heap_adjust(a,i,length); 
    	}
    	
    	/*排序*/ 
    	for(j=length-1;j>0;j--)
    	{
    		swap(a[0],a[j]);
    		heap_adjust(a,0,j); 
    	}	
    }
    
    
    int main()
    {
    	int a[]={1,5,8,7,9,3,4,2,8,6,8,7};
    	int n=sizeof(a)/sizeof(int);
    	
    	heap_sort(a,n);
    	
    	for(int i=0;i<n;i++)
    		cout<<a[i]<<" ";
    	
    	return 0;
    }

注：堆排序对记录较少的文件不提倡。

[Link 1]: https://blog.csdn.net/u011815404/article/details/79256237
[SouthEast]: https://img-blog.csdn.net/20180205022942062?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMTgxNTQwNA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220506/3433d1aa3d1b406ba0fa23a5a98d9194.png
[Link 2]: https://blog.csdn.net/u013384984/article/details/79496052
[70]: /images/20220506/c6117a55572544f1b672075d98c128fe.png
[70 1]: /images/20220506/9c57c43e22094a8b9cccd32d6fe39c42.png
[70 2]: /images/20220506/0b2fc023a3264985a82a8bda6255e342.png
[70 3]: /images/20220506/73d7a10317424353b9ef2da0bb8ba972.png
[70 4]: /images/20220506/734b3a71c517469c85b08eaf3a52e916.png
[70 5]: /images/20220506/daffe65fe57c44989223bc4837972189.png
[70 6]: /images/20220506/e27e4c455ec14a06abdc7908888eb98d.png
[70 7]: /images/20220506/733d036c97e749d29a4122cc64a8b873.png
[70 8]: /images/20220506/7672a819ea014409857eec9a3ea95ac8.png
[70 9]: /images/20220506/bc26ea7d154b4ad3a928b1a2c6266b2c.png