初阶数据结构（C语言实现）——6.2选择排序详解（思路图解+代码实现）
1. 选择排序基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
选择排序分为两类： 1.直接选择排序 2.堆排序
1.1 直接选择排序:
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
1.1.1 单趟直接选择排序代码实现（升序）
优化的单趟选择排序思路：遍历所有数据，一次选出2个值即找最小值和最大值。把最小值放到最左边把最大值放到最右边
有一个点需要注意，就是当遇到极限情况：当max = left 的时候，我们把最小值和left进行了交换，我们max所指向的值就变成了最小值，我们需要换回来，就是让max = min，然后在进行交换
两种情况，看先交换哪个，图解是先把最小值交换到最左边的话，就需要判断当max ==left的情况
如果是先把最大值交换到最右边，那需要判断当min == right的情况，处理下就行。取决于你的选择。
swap(&a[right], &a[max]);
if (right == min)
{
min = max;
}
swap(&a[left], &a[min]);
swap(&a[left], &a[min]);
如果max和left重叠，交换后修正下
if (left == max)
{
max = min;
}
把最大值换到最右边
swap(&a[right], &a[max]);
- 单趟直接选择排序代码实现
void selectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
//单趟选择排序
int min = 0;
int max = 0;
int i = 0;
for (i = 0; i < n-1 ; i++)//在所有数里面进行找最大值和最小值
{
if (a[i] < a[min]) //找到最小值的下标
{
min = i;
}
if (a[i] > a[max])
{
max = i;//找到最大值的下标
}
}
//程序走到这里说明已经找到了最大值下标和最小值下标
//把最小值换到最左边
swap(&a[left], &a[min]);
//如果max和left重叠，交换后修正下
if (left == max)
{
max = min;
}
//把最大值换到最右边
swap(&a[right], &a[max]);
}
- 单趟直接选择排序验证
1.1.1 整体直接选择排序代码实现（升序）
- 整体直接选择排序思路
单趟实现之后的结果就是最大的在最右边，最小的在最左边，所以直接外面套个while 循环就行，
- 整体选择排序代码
void selectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)//整体选择排序，加一层while循环，最后记得更新循环变量即可
{
//单趟选择排序
int min = left;//这里随意给个初值，因为后面会被覆盖
int max = left; //这里随意给个初值，因为后面会被覆盖
int i = 0;
for (i = left; i < right; i++)//在所有数里面进行找最大值和最小值
{
if (a[i] < a[min]) //找到最小值的下标
{
min = i;
}
if (a[i] > a[max])
{
max = i;//找到最大值的下标
}
}
//程序走到这里说明已经找到了当前数组中最大值下标和最小值下标
//把最小值换到最左边
swap(&a[left], &a[min]);
//如果max和left重叠，交换后修正下
if (left == max)
{
max = min;
}
//把最大值换到最右边
swap(&a[right], &a[max]);
//更新循环变量
++left;
--right;
}
}
- 整体选择排序验证
1.2 堆排序
我们在二叉树中堆的应用中已经详细介绍了堆排序，此处不再赘述 ，这里只呈现其中一种的代码实现。
初阶数据结构（C语言实现）——5.3 堆的应用（1）——堆排序
void swap(HPDataType* p1, HPDataType* p2)
{
HPDataType x = *p1;
*p1 = *p2;
*p2 = x;
}
// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{
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], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void heapSort(int* a, int n)
{
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}
1. 附录-源代码
2.1 .h
#pragma once
#include<stdio.h>
#include<stdbool.h>
//直接选择排序
void selectSort(int* a, int n);
//堆排序
void heapSort(int* a, int n);
2.2 .c
#define _CRT_SECURE_NO_WARNINGS 1
#include"20250320_shellSort.h"
//直接选择排序
//升序
void selectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)//整体选择排序，加一层while循环，最后记得更新循环变量即可
{
//单趟选择排序
int min = left;//这里随意给个初值，因为后面会被覆盖
int max = left; //这里随意给个初值，因为后面会被覆盖
int i = 0;
for (i = left; i < right; i++)//在所有数里面进行找最大值和最小值
{
if (a[i] < a[min]) //找到最小值的下标
{
min = i;
}
if (a[i] > a[max])
{
max = i;//找到最大值的下标
}
}
//程序走到这里说明已经找到了当前数组中最大值下标和最小值下标
//把最小值换到最左边
swap(&a[left], &a[min]);
如果max和left重叠，交换后修正下
if (left == max)
{
max = min;
}
把最大值换到最右边
swap(&a[right], &a[max]);
//swap(&a[right], &a[max]);
//if (right == min)
//{
// min = max;
//}
//swap(&a[left], &a[min]);
//更新循环变量
++left;
--right;
}
}
// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{
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], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void heapSort(int* a, int n)
{
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}
2.3 test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"20250320_shellSort.h"
void selectSortTest()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5 };
int size = sizeof(a) / sizeof(a[0]);
printArray(a, size);
selectSort(a, size);
printArray(a, size);
}
void TestHeapSort()
{
int a[] = { 3,5,1,6,2,3,7,9,0,8 };
printArray(a, sizeof(a) / sizeof(int));
heapSort(a, sizeof(a) / sizeof(int));
printArray(a, sizeof(a) / sizeof(int));
}
int main()
{
// insertTest();
// shellTest();
// selectSortTest();
// bubbleSortTest();
TestHeapSort();
return 0;
}