【数据结构】选择排序（直接选择、堆排序）

╰+攻爆jí腚メ 2023-02-25 02:22 31阅读 0赞

**1 选择排序的基本思想**  
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置（或末尾），直到全部待排序的数据元素排完。选择排序可分为直接选择排序、堆排序。  
**2 直接选择排序**  
**2.1 算法步骤**  
1.在元素集合array\[i\]–array\[n-1\]中选择关键码最大(小)的数据元素  
2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换  
3.在剩余的array\[i\]–array\[n-2\]（array\[i+1\]–array\[n-1\]）集合中，重复上述步骤，直到集合剩余1个元素  
**2.2 代码实现**

void Swap(int* left, int* right)
    {
        
    	int temp = *left;
    	*left = *right;
    	*right = temp;
    }
    void SelectSort(int array[], int size)
    {
        
    	for (int i = 0; i < size - 1; ++i)
    	{
        
    		//找当前区间中最大的元素
    		int maxPos = 0;
    		for (int j = 1; j < size - i; ++j)
    		{
        
    			if (array[j]>array[maxPos])
    				maxPos = j;
    		}
    		if (maxPos != size - i - 1)
    		{
        
    			Swap(&array[maxPos], &array[size - i - 1]);
    		}
    	}
    }

以上代码仅标记maxPos位置，效率较低。可一起标记maxPos和minPos两个位置，同时寻找，效率增大一倍，代码如下：

void Swap(int* left, int* right)
    {
        
    	int temp = *left;
    	*left = *right;
    	*right = temp;
    }
    void SelectSortOP(int array[], int size)
    {
        
    	int begin = 0, end = size - 1;
    	while (begin < end)
    	{
        
    		//在[begin,end]区间中找最大和最小的元素
    		int maxPos = begin, minPos = begin;
    		int j = begin + 1;
    		while (j <= end)
    		{
        
    			if (array[j]>array[maxPos])
    				maxPos = j;
    			if (array[j] < array[minPos])
    				minPos = j;
    			++j;
    		}
    		//最大元素放最后
    		if (maxPos != end)
    			Swap(&array[maxPos], &array[end]);
    		//如果end位置存储的刚好是最小元素，上面的交换就将最小元素位置更改了
    		//最小元素位置发生了改变，则必须更新minPos
    		if (minPos == end)
    			minPos = maxPos;
    		//最小元素放最前
    		if (minPos != begin)
    			Swap(&array[minPos], &array[begin]);
    		++begin;
    		--end;
    	}
    }

**2.3 特性**

1.  直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2.  时间复杂度：O(N^2)
3.  空间复杂度：O(1)
4.  稳定性：不稳定

**3 堆排序**  
**3.1 基本思想**  
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。  
**3.2 算法步骤**  
1.建堆（利用向下调整的思想，具体大堆还是小堆看升序还是降序）  
2.排序（利用堆删除的思想进行排序）  
**3.3 代码实现**

void Swap(int* left, int* right)
    {
        
    	int temp = *left;
    	*left = *right;
    	*right = temp;
    }
    //向下调整
    void HeapAdjust(int array[], int size, int parent)
    {
        
    	//用child标记parent较大的孩子，默认先标记parent的左孩子
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
        
    		//找parent中较大的孩子：用parent左右孩子比较
    		//必须先保证parent的右孩子存在
    		if (child + 1 < size&&array[child + 1] > array[child])
    			child += 1;
    		//检测parent是否满足堆的性质
    		if (array[child]>array[parent])
    		{
        
    			Swap(&array[child], &array[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
        
    			return;
    		}
    	}
    }
    void HeapSort(int array[], int size)
    {
        
    	int end = size - 1;
    	//1.建堆
    	//从倒数第一个非叶子节点的位置开始堆调整，一直调整到根节点的位置
    	for (int root = (size - 2) / 2; root >= 0; root--)
    		HeapAdjust(array, size, root);//向下调整
    	//2.排序--利用堆删除的思想进行排序
    	while (end)
    	{
        
    		Swap(&array[0], &array[end]);
    		HeapAdjust(array, end, 0);
    		end--;
    	}
    }

**3.4 特性**

1.  堆排序使用堆来选数，效率就高了很多。
2.  时间复杂度：O(N\*logN)
3.  空间复杂度：O(1)
4.  稳定性：不稳定