代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言：
1.1-排序界说：
排序就是将一组紊乱无章的数据按照一定的规律（升序或降序）组织起来。(注：我们这里的排序接纳的都为升序)
1.2-排序分类：
常见的排序算法：
- 插入排序
a. 直接插入排序
b. 希尔排序
- 选择排序
a. 选择排序
b. 堆排序
- 互换排序
a. 冒泡排序
b. 快速排序
- 归并排序
a. 归并排序
- 非比较排序
a.计数排序
b.基数排序
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.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.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.5-性质：
时间复杂度：
冒泡排序算法是一种基于比较的排序算法，每次冒泡过程，都会有一个数据确定位置。最坏的环境下需颠末n-1次冒泡，就有n个数据确定了位置时间复杂度为O(N^2),但若是我们参加判断条件则最好的环境下可提前结束循环最好的环境下只需颠末2次冒泡即可此时时间复杂度为O(N)。
空间复杂度：
因为没开辟空间，所以空间复杂度为O（1）。
稳固性：
冒泡排序是相邻元素之间的比较，此时我们可以控制相同元素的位置，所以冒泡排序是稳固性的算法。
五、结语：
上述内容，即是我个人对数据结构排序中选择排序、堆排序、冒泡排序的个人看法以及自我实现。如有大佬发现那里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞，关注，收藏与支持，我会更加积极的学习编程语言，还望各位多多关照，让我们一起进步吧！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
