目录

1.堆排序

2.冒泡排序

单趟排序的两种情况

情况1.和arr[i]的前一个元素交换,第一次循环结束时i的值为n-1,第二次循环结束时i的值为n-2

情况2.和arr[i]的后一个元素交换,第一次循环结束时i的值为n-2,第二次第一次循环结束时i的值为n-3,...

将单趟排序代码嵌入外循环中

执行结果

冒泡优化

---

1.堆排序

之前讲过,参见103.【C语言】数据结构之用堆对数组排序

2.冒泡排序

之前简单讲过,见42.【C语言】冒泡排序,但没有详细讲过内外循环的细节上的处理和写法上的逻辑,本文将深入讲解

之前讲过这个经验:写排序应该先写单趟排序,后将其嵌入外循环中发挥作用

单趟排序的两种情况

例如排升序

情况1.和arr[i]的前一个元素交换,第一次循环结束时i的值为n-1,第二次循环结束时i的值为n-2

内循环代码

	for (int i = 1; i < n - j; i++){if (arr[i - 1] > arr[i]){Swap(&arr[i - 1], &arr[i]);}}

例如无序数组arr={5,3,1,2}的第一次单趟排序

情况2.和arr[i]的后一个元素交换,第一次循环结束时i的值为n-2,第二次第一次循环结束时i的值为n-3,...

内循环代码

	for (int i = 0; i < n - j - 1; i++){if (arr[i] > arr[i + 1]){Swap(&arr[i], &arr[i + 1]);}}

例如无序数组arr={5,3,1,2}的第一次单趟排序 

将单趟排序代码嵌入外循环中

以情况1代码为例,嵌入大循环中

void BubbleSort(int* arr, int n)
{for (int j = 0; j < n; j++){for (int i = 1; i < n - j; i++){if (arr[i - 1] > arr[i]){Swap(&arr[i - 1], &arr[i]);}}}
}

 以情况2代码为例,嵌入大循环中

void BubbleSort(int* arr, int n)
{for (int j = 0; j < n; j++){for (int i = 0; i < n - j - 1; i++){if (arr[i] > arr[i + 1]){Swap(&arr[i], &arr[i + 1]);}}}
}

main.c写入

#include "Sort.h"
int main()
{int arr[] = { 3,5,1,6,2,3,9,0,8 };printf("排序前:");PrintArray(arr, sizeof(arr) / sizeof(arr[0]));BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));printf("排序后:");PrintArray(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

执行结果

冒泡优化

如果j==n-1之前数组就已经处于有序状态(即当内循环的Swap函数一次没有执行时),可以提前退出循环

优化后的代码

void BubbleSort(int* arr, int n)
{for (int j = 0; j < n; j++){bool exchange_flag = false;for (int i = 0; i < n - j - 1; i++){if (arr[i] > arr[i + 1]){exchange_flag = true;Swap(&arr[i], &arr[i + 1]);}}//如果一次都没有交换则说明数组处于有序状态if (exchange_flag == false){break;}}
}

注意bool exchange_flag = false;不能写在外循环的外面,否则无效