数据结构-C语言-排序（2）
代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言：
1.1-排序定义：
排序就是将一组杂乱无章的数据按照一定的规律（升序或降序）组织起来。(注：我们这里的排序采用的都为升序)
1.2-排序分类：
常见的排序算法：
1.3-算法比较：
1.4-目的：
今天，我们这里要实现的是选择排序、堆排序、冒泡排序。
二、选择排序：
2.1-思路：
1.找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置；
2.找到数组中最大的元素，拎出来，将它和数组的最后一个元素交换位置；
3.在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置;
4.在剩下的元素中继续寻找最大的元素，拎出来，和数组的倒数第二个元素交换位置;
5.需要注意max若与left位置相同时需特殊处理，否则位置交换会出现问题；
6.如此循环，直到整个数组排序完成；
7.若是由大到小也是同样方法，只需要修改比较大小的符号；
2.2-过程图：
2.3-代码：
//升序
void SelectSort(int* a, int len)//选择排序---时间复杂度(O(N^2))
{
printf("原数组顺序：");
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
int left = 0;
int right = len - 1;
int max = 0;
int min = 0;
while (left < right)
{
max = min = left;
for (int i=left; i<=right; i++)
{
if (a[i] > a[max])
max = i;
if (a[i] < a[min])
min = i;
}
Swap(&a[left], &a[min]);
if (max == left)
{
max = min;
}
Swap(&a[right], &a[max]);
++left;
right--;
printf("第%d时排序：",left);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
}2.4-效果图：
2.5-性质：
由上述代码及图片见:
时间复杂度：
简单选择排序是通过两层循环实现。 第一层循环：依次遍历序列当中的每一个元素 第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。每次循环时间复杂度都为O（N）所以选择排序时间复杂度为O(N^2)。
空间复杂度：
因为没开辟空间，所以空间复杂度为O（1）。
稳定性：
选择排序是一种不稳定的排序算法。 我们可以从上面的图片中看出，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。 比如说：5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以选择排序是不稳定的排序算法。
三、堆排序：
3.1-思路：
对于堆排序，我们首先要将无序的数组建成大堆，大堆的话有助于排升序。因为大堆可以确定最大值，我们只需将首元素与尾元素交换，然后去除尾元素，继续进行向下调整，最后进行循环，直到排序完成为止。
3.2-过程图：
3.3-代码：
void AdjustDown(int* a, int len, int parent)//向下调整---时间复杂度(O(logN))
{
int child = parent * 2 + 1;
while(child<len)
{
if (child+1<len && a[child] < a[child + 1])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int len)//堆排序---时间复杂度(O(N*logN))
{
printf("原数组顺序：");
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
//建大堆---时间复杂度(O(N))
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, len, i);
}
printf("建堆后数组顺序：");
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
//自我实现排序---时间复杂度(O(N*logN))
int end = len-1;
int n = 1;
while(end>0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
printf("第%d趟排序：",n++);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
}3.4-效果图：
3.5-性质：
时间复杂度：
由于向下调整函数的时间复杂度为O(logN)，遍历数组的时间复杂度为O(N)，所以堆排序的时间复杂度为O(N*logN)
空间复杂度：
因为没开辟空间，所以空间复杂度为O（1）。
稳定性：
堆排序是通过反复调整元素位置来完成排序的过程，其中涉及到交换操作。这些交换操作可能导致相同键值元素的相对顺序发生变化，因此堆排序是一个不稳定的排序算法。
四、冒泡排序：
4.1-思路：
通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就如果水底下的气泡一样逐渐向上冒。
4.2-过程图：
4.3-代码：
void BubbleSort(int* a, int len)//冒泡排序---时间复杂度(O(N^2))
{
printf("原数组顺序：");
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
for (int j = 0; j < len - 1; j++)
{
int judge = 1;//判断数组是否有序
for (int i = 0; i < len - j-1; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
judge = 0;//如果进循环说明无序令judge为0
}
}
printf("第%d趟排序：", j + 1);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
if (judge)
{
return;
}
}
}4.4-效果图：
4.5-性质：
时间复杂度：
冒泡排序算法是一种基于比较的排序算法，每次冒泡过程，都会有一个数据确定位置。最坏的情况下需经过n-1次冒泡，就有n个数据确定了位置时间复杂度为O(N^2),但若是我们加入判断条件则最好的情况下可提前结束循环最好的情况下只需经过2次冒泡即可此时时间复杂度为O(N)。
空间复杂度：
因为没开辟空间，所以空间复杂度为O（1）。
稳定性：
冒泡排序是相邻元素之间的比较，此时我们可以控制相同元素的位置，所以冒泡排序是稳定性的算法。
五、结语：
上述内容，即是我个人对数据结构排序中选择排序、堆排序、冒泡排序的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞，关注，收藏与支持，我会更加努力的学习编程语言，还望各位多多关照，让我们一起进步吧！
原文地址：https://blog.csdn.net/h_number_1/article/details/140424114
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！