C语言---选择排序和堆排序

雨点打透心脏的1/2处 2023-09-23 23:37 85阅读 0赞

### 文章目录 ###

*  前言
 *  一、简单选择排序
 *   *  1.简介
     *  2.算法思路
     *  3.代码实现
 *  二、堆排序
 *   *  1.简介
     *  2.算法思路
     *  3.代码实现
 *  总结

--------------------

# 前言 #

堆排序是选择排序的一种，今天我们讲解一下堆排序和简单选择排序

--------------------

# 一、简单选择排序 #

## 1.简介 ##

> 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。  
> 时间复杂度：O(n²） 稳定性：不稳定

## 2.算法思路 ##

动态显示图，充分理解选择排序  
![在这里插入图片描述][6c9a1d6a673b47e59a7f5af6df56d931.gif_pic_center]  
从图中我们可以看见：

1.  第一趟在未排序序列寻找最小值，然后放在序列的起始位置
2.  第二趟，从已排好的元素后面开始寻找最小值，然后再放在最前端
3.  依次寻找，排序…直到所有元素依次排好。

## 3.代码实现 ##

简单选择排序：

void select_sort(int *p,int n)\n
    {
         
     int i,j;
        int min = 0;
        for(i = 0;i < n - 1;i++)//排序次数
        {
        
            min = i;
            for(j = i + 1;j < n;j++)
            {
        
                if(p[j] < p[min])
                {
        
                    min = j;//记录交换的元素下标值
                }
            }
            if(i != min)
            {
        
                int temp = p[i];
                p[i] = p[min];
                p[min] = temp;
            }  
    int main()
    {
        
    	int arr[num] = {
         3,1,4,5,2,7,9,0,8,6 };
    	select_sort(arr, num);
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }

那思考一下，能否进行改进呢？比如，我们同时找最大值最小值，然后将最小值放序列前端，最大值放序列末端。  
**代码实现：**

void swap(int* q, int* a)
    {
        
    	int tem = *q;
    	*q = *a;
    	*a = tem;
    }
    void select_sort(int* a, int n)
    {
        
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
        	
    		int min = begin, max = begin;
    		for (int i = min; i < end; i++)
    		{
        
    			if (a[i] < a[min])
    				min = i;
    			if (a[i] > a[max])
    				max = i;
    		}
    		swap(&a[min], &a[begin]);
    		// begin == maxi时，最大被换走了，修正一下maxi的位置
    		if (begin == max)
    			max = min;
    		swap(&a[max], &a[end]);
    		begin++; end--;
    	}
    }
    int main()
    {
        
    	int arr[num] = {
         3,1,4,5,2,7,9,0,8,6 };
    	select_sort(arr, num);
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }

在使用这个代码时，得小心当begin位置处于max的下标，min和begin互换之后，*max在的下标值则是已经更换，最大值在min的下标值了*，所以需要进行判断。  
**运行结果：**  
![在这里插入图片描述][cb1aa80f5ba14e7bbce7b59af7e444e5.png]

# 二、堆排序 #

## 1.简介 ##

> 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。  
> 时间复杂度：O(N\*logN） 空间复杂度：O(1） 稳定性：不稳定  
> 而如果想使用堆排序，则需要先建立堆，然后选择大推或者小堆排序

## 2.算法思路 ##

1.  将初始待排序关键字序列(R0,R1,R2…Rn)构建成大顶堆，此堆为初始的无序区。
2.  将堆顶元素R\[0\]与最后一个元素R\[n\]交换，此时得到新的无序区(R0,R1,R2,…Rn-1)和新的有序区(Rn)。
3.  由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R0,R1,R2,…Rn-1)调整为新堆，然后 再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R0,R1,R2…Rn-2)和新的有序区(Rn-1,Rn)。
4.  不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成

堆图像展示和讲解：  
![在这里插入图片描述][bac4403758a04c16a1e2ecf4bb46b09f.png]  
大堆构建的动态显示图：  
![在这里插入图片描述][c8b74525912d4897971a791ea62f759d.gif_pic_center]  
耐心观看，我们可以看见，先变成了大堆顶（堆顶元素最大，父亲节点大于孩子节点），然后堆顶元素和最后一个元素交换，最后一个元素变成堆顶元素，然后和最大的孩子结点进行交换，最后将第二大的叶子结点交换上来，变成堆顶元素，而原来的元素则需要调整到适合它的位置。

红色是已排序的有序区间 黄色是调换堆顶元素和末尾元素 绿色是待排序区间

注：重点在于建堆（大堆和小堆）

## 3.代码实现 ##

**代码如下：**

void Swap(int* px, int* py)
    {
        
    	int tmp = *px;
    	*px = *py;
    	*py = tmp;
    }
    void AdjustDown(int* a, int n, int parent)
    {
        
    	int child = parent * 2 + 1;
    	while (child < n)
    	{
        
    		// 选出左右孩子中小的那一个
    		if (child + 1 < n && a[child + 1] > a[child])
    		{
        
    			++child;
    		}
    
    		// 如果小的孩子小于父亲，则交换，并继续向下调整
    		if (a[child] > a[parent])
    		{
        
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }
    
    // 堆排序
    void HeapSort(int* a, int n)
    {
        
    	// O(N)
    	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    	{
        
    		AdjustDown(a, n, i);
    	}
    
    	// O(N*logN)
    	int end = n - 1;
    	while (end > 0)
    	{
        
    		Swap(&a[0], &a[end]);
    		AdjustDown(a, end, 0);
    		--end;
    	}
    }
    int main()
    {
        
    	int arr[num] = {
         3,1,4,5,2,7,9,0,8,6 };
    	HeapSort(arr, num);
    	for (int i = 0; i < num; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }

**运行结果：**  
![在这里插入图片描述][08fd75d3fa734302824938085fe97bcc.png]

--------------------

# 总结 #

堆排序比较难以理解，可以通过画图来消化，并且重点在于建堆。  
文章的动态图全是小小作者我在网上寻找到的，认为最为合适并且容易理解的图。本文的图全部来源于百度

> 本人认为堆排序比较难以理解，千位要画图理解，各位努力学习的IT人员们，一起加油努力哦。祝各位学业有成，财源滚滚。  
> \---------来自菜鸟TQ02的祝福语

[6c9a1d6a673b47e59a7f5af6df56d931.gif_pic_center]: https://img-blog.csdnimg.cn/6c9a1d6a673b47e59a7f5af6df56d931.gif#pic_center
[cb1aa80f5ba14e7bbce7b59af7e444e5.png]: https://img-blog.csdnimg.cn/cb1aa80f5ba14e7bbce7b59af7e444e5.png
[bac4403758a04c16a1e2ecf4bb46b09f.png]: https://img-blog.csdnimg.cn/bac4403758a04c16a1e2ecf4bb46b09f.png
[c8b74525912d4897971a791ea62f759d.gif_pic_center]: https://img-blog.csdnimg.cn/c8b74525912d4897971a791ea62f759d.gif#pic_center
[08fd75d3fa734302824938085fe97bcc.png]: https://img-blog.csdnimg.cn/08fd75d3fa734302824938085fe97bcc.png