【数据结构】选择排序——选择排序 和 堆排序

一、选择排序

选择排序的思路及其代码

选择排序思路很简单
就是经过将数组遍历选择最小值
将最小值位置的数与数组最前面位置的数进行交换
如此反复，完成排序

为了提高效率我们在一次遍历过程中同时找最大和最小值
代码如下：

//选择排序
void SelectSort(int* a, int n)
{int maxi = n - 1;int mini = 0;while (mini < maxi){//找出最大最小值的下标int max = maxi;int min = mini;for (int i = mini; i <= maxi; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}//将最大最小值进行更新，将最大最小值放到数组两边Swap(&a[mini], &a[min]);//若最大值在原最小值的位置，将位置更新if (max == mini){max = min;}Swap(&a[maxi], &a[max]);maxi--;mini++;}
}

运行结果：

选择排序的弊端

因为无论数组中原数组是如何排列
选择排序都要遍历数组
所以它的最好与最坏的情况下
时间复杂度都是 O(N ^ 2)
效率低下，正常情况下是不会使用这个排序的

二、堆排序

以下的链接又对堆和堆排序的讲解：
堆以及堆排序

下面我就直接把代码贴出来：

//向下调整（建大堆）
void AdjustDown(int* a, int parent, int n)
{//左孩子int child = parent * 2 + 1;while (child + 1 < n){//先找左右孩子中大的一个if (child + 1 < n && a[child] < a[child + 1]){child++;}//将父亲节点与孩子节点进行比较，将大的移到父亲节点if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}//进行堆排序int size = n - 1;while (size > 0){//先将堆的第一个数与最后一个数交换Swap(&a[0], &a[size--]);//向下调整AdjustDown(a, 0, size);}
}

运行结果：

堆排序的时间复杂度为 O(N * logN)

三、速度对比

同时排10000个数

同时排100000个数

同时拍500000个数

排序到这里选择排序就已经非常慢了
我们笔记本是 i9 的 cpu 配置还算可以
跑的时候风扇已经呜呜转了

堆排 1 亿个数