选择排序和堆排序
选择排序
原理
选择排序：每次从待排序序列中找到最小值和待排序序列的第一个值交换。
图示
(红线右边为待排序序列)
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;
}
}
}
- minindex 保存的是最小值的下标
- 趟数 总数少一趟
- 每趟循环一进来 ，待排序序列的第一个值是最小值 所以minindex先赋值为i
- 从待排序序列的第二个值开始和arr[minindex]比较
- 如果找到更小的数 则minindex重新赋值为新的最小值的下标
- 此时for循环执行结束 代表着minindex保存的就是最小值的下标
- 因为i保存的是待排序序列第一个值
评价
每一次将待排序序列中最小值和待排序序列中第一个值进行交换，直到完全有序即可。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定(存在跳跃交换)
堆排序
堆的概念
什么是堆？
以完全二叉树的结构来管理的一维数组。
什么是大顶堆？
父节点的值大于子节点
什么是小顶堆？
父节点的值小于子节点
原理
把一维数组臆想成完全二叉树
示例：
如何通过父节点的下标推出子节点的下标？
如图:红色为下标
左孩子下标 ： 2 * i + 1;
右孩子下标 ： 2 * i + 2
子节点怎么推出父节点？
父节点：(i - 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)
- 稳定性：不稳定（存在跳跃交换）