选择排序与堆排序

引言

从这篇文章开始，将介绍几大排序算法：选择排序、堆排序、直接插入排序、希尔排序、冒泡排序、快速排序、归并排序以及计数排序。

在本篇文章中要介绍的是选择排序与堆排序，它们都属于选择排序。
这两种排序算法的思想都是从待排序的数据元素中选出最大或最小的元素，放在序列的起始位置或末尾位置，以此来使整个序列有序：

选择排序

思路

选择排序就很符合上面的描述：从数组中选出最小的元素，放在数组的起始位置。然后就相当于起始位置的元素就是正确的位置，也就相当于需要排序的部分减少了一个元素。由此循环就可以实现排序整个数组：

实现

这样的思路，很明显是需要两层循环的：
内层循环需要确定出当前待排序部分中最小的元素，并将其下标记录下来。每次内层循环后，将最小元素与待排徐部分的起始元素交换；
外层循环需要缩小待排序部分的大小。从数组的大小开始，直到待排序部分为0，即整个数组排序完毕：

void Swap(int* a, int m, int n)//交换
{int temp = a[n];a[n] = a[m];a[m] = temp;
}
//选择排序
void SelectSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int min = a[i];int mini = i;for (int j = i + 1; j < n; j++){if (a[j] < min){min = a[j];mini = j;}}Swap(a, i, mini);}
}

堆排序

思路

堆排序是建立在二叉树上的一种排序方法，在前面我们详细介绍了二叉树与堆这种数据结构。
对于大堆而言，堆顶的元素是该堆中最大的元素。我们只需要通过不断建堆，不断将堆顶的元素放到当前待排序的部分的末尾。就相当于末尾元素就在其正确的位置。逐渐缩小堆的大小就可以实现排序整个数组。

实现

在这个思路下，我们需要两次循环：

第一次循环实现将当前数组所有元素建大堆。
建堆时，有两种方式：向上调整建堆与向下调整建堆：
向上调整建堆时，类似于二叉树的尾插，然后将这个尾插的数向上调整放到合适的位置；
向下调整建堆时，即将每一个根结点向下调整，放在其合适的位置。这要求该根的子树都是正确的大堆，所以我们需要从倒数第二层的根结点开始向下调整：
（向下调整建堆的时间复杂度是比向上调整少的，在这里不做证明，在本篇文章中也只实现向下调整建堆）

第二次循环需要实现不断将堆顶的元素与当前待排序部分所建堆的末尾元素交换，使该元素完成排序。然后待排序的部分缩小，待排序部分再次建大堆。直到排序结束：

（关于向下调整的AdjustDown函数，在堆中有详细讲解，这里就不赘述：戳我看堆及其实现详解）

void Swap(int* a, int m, int n)//交换
{int temp = a[n];a[n] = a[m];a[m] = temp;
}
void AdjustDwon(int* a, int n, int root)//向下调整建堆
{int parent = root;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, parent);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(int* a, int n)
{for (int i = (n - 2) / 2; i >= 0; i--)//建堆{AdjustDwon(a, n, i);}for (int i = 1; i < n ; i++)//排序{Swap(a, 0, n-i);AdjustDwon(a, n - i, 0);}
}

总结

到此，关于选择排序与堆排序的内容就介绍完了
接下来会继续介绍其他的排序，欢迎持续关注哦

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出

如果本文对你有帮助，希望一键三连哦

希望与大家共同进步哦