【初阶数据结构与算法】八大排序算法之选择排序（直接选择排序、堆排）
文章目录
- 一、单向直接选择排序
- 二、双向直接选择排序
- 三、堆排
- 四、直接选择排序以及堆排性能对比
一、单向直接选择排序
选择排序很好理解，就是按照字面意思来，比如我们想要将一个数组排成升序，那么小的值就会被放在前面，我们就可以每次都找到数组中的最小值，把它往前面放，循环往复，最终我们就可以将数组排成升序
降序也是如此，就是每次我们都找到数组中的最小值，把它往后面放，最后我们就能将数组排成降序，这就是单向直接选择排序，我们画个简易图理解理解：
如上图就是使用单向直接选择进行排序的例子，思路很简单，那么有了思路，我们接下来就开始写代码，如下：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//直接选择排序(单向)
void SelectSort1(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
}
Swap(&arr[begin], &arr[mini]);
begin++;
}
}
我们来使用它排序试试，如图：
可以看到单向直接选择排序很好地帮我们完成了任务，接下来我们分析一下它的时间复杂度，它拥有两层用于遍历的循环，所以时间复杂度为O(N^2)，虽然不是很好，但是它的思路很简单
其中单向直接选择排序就是选最小的元素往前或往后放，一次只选一个元素，所以叫单向，那么双向选择排序是什么样子的呢？我们一起来学习一下
二、双向直接选择排序
单向直接选择排序就是一次只选一个值出来往前或往后放，那么双向选择排序就是，一次把当前最小的和最大的元素的下标找出来，把最小的元素往前放，把最大的元素往后放
这样我们是不是一次遍历就可以排好两个元素，而单向的一次遍历只能排好一个元素，相当于是一种优化，那么是不是双向一定比单向快呢？我们在最后的测试阶段给出答案
由于双向直接选择排序和单向直接选择排序很相似，所以我们这里直接就根据上面的思路来写代码了，就是每次找最小值往前放，同时找最大值往后放，但是其实会有坑，但是先不管，我们先把大思路写出来，后面再分析坑在哪里，如下：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//直接选择排序(双向)
void SelectSort2(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++, end--;
}
}
这里的双向直接选择排序几乎和单向直接选择排序差别不大，那么是否它已经没有问题了呢？我们来看看代码的运行结果：
可以看到代码出现了一些小问题，没有将数组完全排成升序，那么问题在哪里呢？这里我也不再墨迹了，直接举一个例子画图讲解，如图：
根据上图我们已经发现了问题，我们来分析一下为什么会出现这种问题，根本原因就是数组中最大值就在begin的位置上，当最小值和begin位置元素进行交换时，把这个最大值交换到mini位置上去了
然后maxi和end位置数据进行交换时，end就拿到了最小值，所以最后导致了上面的问题，根本原因就是最大值在begin的位置上，所以我们想个办法来优化一下
由于begin和mini位置的数据总是先交换，如果begin位置就是最大值的话，经过begin和mini的交换后，这个最大值就会跑到mini的位置上去，所以我们解决的方案就是，如果begin位置就是最大值的话，让maxi = mini
这样的话经过begin和mini的一次交换，将最大值交换到了mini的位置， 现在我们又让maxi走到mini的位置，maxi现在指向的就是最大值，可以放心交换，如图：
现在我们就解决掉这个问题了，我们改正一下我们的代码，如下：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//直接选择排序(双向)
void SelectSort2(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
if (begin == maxi)
{
maxi = mini;
}
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++, end--;
}
}
接下来我们再次来测试一下代码，如图：
可以看到之前的问题被我们完全解决了，这就是我们真正的双向直接选择排序，接着我们分析一下它的时间复杂度，虽然比起单向的循环少了一半，但是还是属于O(N^2)级别，也不算太优，到最后我们再将它们来进行比较，我们继续学习下面的内容
三、堆排
堆排我在堆的应用部分就已经讲过了，如果有兴趣就去看看原理，这里直接给出源代码，如下：
//向上调整算法
void AdjustUp(int* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child + 1] > arr[child])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排
void HeapSort(int* arr, int n)
{
//向上调整建堆
/*for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}*/
//向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
//建堆后进行排序
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
我们之前在堆的应用也讲过堆排的时间复杂度，这里再提一下，大致为O(Nl * logN)，这个时间复杂度非常优秀，在最后我们进行对比时也可以看出来
四、直接选择排序以及堆排性能对比
我们还是按照上一篇文章的样子来写一个专门测试排序性能的函数，它可以帮我们生成10万个随机数，如下：
void TestOP()
{
srand((unsigned int)time(NULL));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
}
int begin1 = clock();
SelectSort1(a1, N);
int end1 = clock();
int begin2 = clock();
SelectSort2(a2, N);
int end2 = clock();
int begin3 = clock();
HeapSort(a3, N);
int end3 = clock();
printf("SelectSort1(单向):%d\n", end1 - begin1);
printf("SelectSort2(双向):%d\n", end2 - begin2);
printf("HeapSort:%d\n", end3 - begin3);
free(a1);
free(a2);
free(a3);
}
int main()
{
TestOP();
return 0;
}
注意我们在运行这段代码之前，要把模式改成Release，这样才能真正测试它们的性能，运行结果如下：
可以看到，我们排10万个随机数，堆排只用了5毫秒，而单向和双向直接选择排序则直接来到了4秒左右，我们再来测试一下排序100万个随机数的时间，如图：
可以发现，堆排的速度依旧非常非常快，仍然在0.1秒之内，而两个直接选择排序则是慢了非常多，已经以分钟来计数了，这就是O(N * log N)的力量
当我们比较完堆排和直接选择排序之后，我们来比较一下单向和双向两个直接选择排序，我们惊讶地发现，单向的直接选择排序居然更快，理论上来说，双向是单向的优化，循环次数更少，为什么还会出现这种问题呢？
大致原因应该是单向选择排序它的交换逻辑和条件判断更简单，编译器在编译代码时，就做了更多和更好的优化，导致单向比双向快，但是我们要知道理论上双向是单向的优化
那么到这里我们选择排序就到这里介绍完毕了，如果有什么疑问欢迎私信我，我会及时作出回应，感谢支持！
bye~