本文主要是介绍6.2排序——选择排序与堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本篇博客梳理选择排序，包括直接选择排序与堆排序
排序全部默认排成升序
一、直接选择排序
1．算法思想
每次遍历都选出最小的和最大的，放到序列最前面/最后面
2．具体操作
（1）单趟
每次遍历都选出最小的和最大的。遍历时，遇到更小的，更新min，遇到更大的，更新max
（2）单趟变整体
每趟遍历完之后，begin++，end–
程序结构如下
while(begin<end)
{//遍历后，最小的放到begin处，最大的放到end处；begin++;end--;
}
（3）具体代码实现
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = end;for (int i = begin + 1; i <= end; i++){if (a[i] > a[max])max = i;if (a[i] <= a[min])min = i;}Swap(&a[begin], &a[min]);Swap(&a[end], &a[max]);begin++;end--;}
}
可能很多人首先会想到这么写，但测试一下会发现有bug
拿一个这样子的数组来看：
int a[10] = { 9,2,5,7,4,8,6,3,5,1 };
来分析一下为啥会有这个bug
因此需要对max==begin的情况单独进行修正
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = end;for (int i = begin + 1; i <= end; i++){if (a[i] > a[max])max = i;if (a[i] <= a[min])min = i;}//问题已找到，此为优化版写法Swap(&a[begin], &a[min]);//当max==begin时，此交换操作会导致//max指向错误的值，需要在下面if判断加以修正if (max == begin)max = min;Swap(&a[end], &a[max]);begin++;end--;}
}
3．特性总结
（1）效率不是很好，实际中很少使用
（2）时间复杂度：o(N²)
（3）空间复杂度：o(1)
（4）稳定性：不稳定
二、堆排序（见5.2二叉树中的堆排序，此处略）
这篇关于6.2排序——选择排序与堆排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
