基础数据结构——简单选择排序和堆排序——笔记自用

选择排序和堆排序

• 选择排序
• • 原理
  • 图示
  • C语言代码
  • 评价
• 堆排序
• • 堆的概念
  • 原理
  • • 疑问
    • 为什么要调成大顶堆？
    • 怎样调节成大顶堆？
    • 步骤一： 调节成大顶堆
    • 二：将最后一个结点的值和根节点的值交换
    • 三：再次调整为大顶堆
    • 四：重复二三步骤，直至完全有序
  • C语言代码
  • 评价

选择排序

原理

选择排序：每次从待排序序列中找到最小值和待排序序列的第一个值交换。

图示

(红线右边为待排序序列)

C语言代码

注意：

在每次交换的时候，保存的是最小值的下标。

void SelectSort(int* arr, int len)
{
	assert(arr != NULL);

	int minindex = 0; //1

	for (int i = 0; i < len - 1; i++) //2
	{
		minindex = i; //3
		
		for (int j = i + 1; j < len; j++) //4
		{
			if (arr[j] < arr[minindex]) //5
			{
				minindex = j;
			}
		}
		//6

		//进行交换
		if (i != minindex)
		{
			int tmp = arr[i]; //7
			arr[i] = arr[minindex];
			arr[minindex] = tmp;
		}
	}
}
           

1. minindex 保存的是最小值的下标
2. 趟数 总数少一趟
3. 每趟循环一进来 ，待排序序列的第一个值是最小值 所以minindex先赋值为i
4. 从待排序序列的第二个值开始和arr[minindex]比较
5. 如果找到更小的数 则minindex重新赋值为新的最小值的下标
6. 此时for循环执行结束 代表着minindex保存的就是最小值的下标
7. 因为i保存的是待排序序列第一个值

评价

每一次将待排序序列中最小值和待排序序列中第一个值进行交换，直到完全有序即可。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定(存在跳跃交换)

堆排序

堆的概念

什么是堆？

以完全二叉树的结构来管理的一维数组。

什么是大顶堆？

父节点的值大于子节点

什么是小顶堆？

父节点的值小于子节点

原理

把一维数组臆想成完全二叉树

示例：

如何通过父节点的下标推出子节点的下标？

如图:红色为下标

左孩子下标 ： 2 * i + 1;

右孩子下标 ： 2 * i + 2

子节点怎么推出父节点？

父节点：(i - 1) / 2

疑问

为什么要调成大顶堆？

因为每次调整之后根节点的值就是最大值，将其放到最后，实现从小到大排序。若需要从大到小排序，将其调整为小顶堆。

怎样调节成大顶堆？

1. 从最后一个非叶子结点从后向前开始调整。
2. 从上向下开始调整。

1图示：

最后一个非叶子结点为红圈所示

将其调整为：

在调整前一个非叶子结点：

调整为：

步骤一： 调节成大顶堆

这样依次调整，最后调整为大顶堆：

二：将最后一个结点的值和根节点的值交换

并且交换后的尾部节点不参与下一次调整，因为它是最大值，已经找到自己的位置。

三：再次调整为大顶堆

根据上一步骤可以得出：不需要再从最后一个非叶子结点进行调整，只需要以根节点为基准调整一次。

四：重复二三步骤，直至完全有序

C语言代码

void HeapAdjust(int* arr, int start, int end)
{
	int tmp = arr[start];

	for (int i = start * 2 + 1; i <= end; i = start * 2 + 1)//语句3是 时间复杂度O（nlogn）的原因
	{
		if (i < end && arr[i] < arr[i + 1])//有右孩子 并且右孩子比左孩子大 
		{
			i++;
		}
		//如果if为假   代表要么右孩子不存在  要么右孩子存在 但是小于左孩子
		//此时 i保存的是左右孩子中较大的值的下标
		//接着让父子比较

		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	//此时for循环推出了，要么此时触底  要莫if(arr[i]>tmp)为假  break跳出循环
	arr[start] = tmp;
}

void HeapSort(int* arr, int len)
{
	//1.先调整成大顶堆  从最后一个非叶子节点开始
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)//O（n）
	{
		HeapAdjust(arr, i, len - 1);//（logn）    
	}//   则时间复杂度O（nlogn）

	//根节点和尾节点交换
	for (int i = 0; i < len - 1; i++)//O（n）
	{
		int tmp = arr[0];
		arr[0] = arr[len - 1 - i];//9 8 7 6 5 4 3 2 1
		arr[len - 1 - i] = tmp;

		HeapAdjust(arr, 0, (len - 1 - i) - 1);//(len-1-i)相当于最后一个节点的下标  然后最后一个节点不参与计算 则再-1
	}
}
           

评价

• 时间复杂度：O(n log2n)
• 空间复杂度：O(1)
• 稳定性：不稳定（存在跳跃交换）