6.2排序——选择排序与堆排序

本文主要是介绍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
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--;}
}