数据结构-C语言-排序（2）

代码位置：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.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;}}}