八大排序——冒泡排序/归并排序

八大排序——冒泡排序/归并排序

一、冒泡排序

1.1 冒泡排序

1.2 冒泡排序优化

二、归并排序

1.1 归并排序（递归）

1.2 递归排序（非递归）

---

一、冒泡排序

1.1 冒泡排序

比较相邻的元素。如果第一个比第二个大，就交换它们两个。

void Bubble_Sort(int arr[], int len) // 定义冒泡排序函数，参数为数组和数组长度
{// 外层循环控制排序的总趟数，从0开始，到len-1结束for (int i = 0; i < len - 1; i++){// 内层循环负责每一趟排序中的实际比较和交换操作// 从0开始，到len-i-1结束，因为每趟排序结束后，最大的元素会“冒泡”到最后，不需要再参与比较for (int j = 0; j + 1 < len - i; j++){// 比较相邻的两个元素if (arr[j] > arr[j + 1]){// 如果左边的元素大于右边的元素，说明它们的顺序错误，需要交换int tmp = arr[j]; // 使用临时变量tmp来保存arr[j]的值arr[j] = arr[j + 1]; // 将arr[j+1]的值赋给arr[j]arr[j + 1] = tmp; // 将tmp的值赋给arr[j+1]，完成交换}}}
}

1.2 冒泡排序优化

数据要是已经默认有序了，则后续的趟数就不排序了

问题：怎么得出已有数据是否有序？

解决方法：跑一趟，跑完了都没有一次数据交换发生，也就是说都是左边值小于右边值

void Bubble_Sort(int arr[], int len)
{bool tag = true;for (int i = 0; i < len - 1; i++)//控制趟数{//每一趟开始时把tag重新置位真tag = true;for (int j = 0; j + 1 < len - i; j++)//j指向比较一对数据中左边的值，右边用j+1{if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j ] = arr[j+1];arr[j + 1] = tmp;tag = false;}}if (tag)//tag还是真，那么就默认递增有序，直接退出{return;}}
}

时间复杂度位n^2  空间复杂度1

稳定值：稳定 俩个俩个比

二、归并排序

将长度为n的待排序序列，看作n个长度为1的有序组，然后进行合并，合并成n/2个长度为2的有序组，然后接着合并，直到所有的数据都合并到同一个组为止

1.1 归并排序（递归）

#include <stdio.h> // 引入标准输入输出头文件，用于使用 printf 和 scanf 函数
#include <stdlib.h> // 引入标准库头文件，用于使用内存分配函数 malloc 和 exit 函数
#include <string.h> // 引入字符串操作头文件，用于使用 memset 函数// 函数声明，用于在主函数之后定义，显示排序后的数组
void Show(int arr[], int len);// 合并两个有序子数组到临时数组 brr 中，然后再复制回原数组 arr
void Merge(int arr[], int len, int left, int mid, int right, int* brr) {int i = left; // 初始化指针 i 指向左边子数组的起始位置int j = mid + 1; // 初始化指针 j 指向右边子数组的起始位置int k = left; // 初始化指针 k 指向临时数组 brr 的起始位置while (i <= mid && j <= right) { // 当两个子数组中都有元素时if (arr[i] <= arr[j]) { // 如果左边的元素小于等于右边的元素brr[k] = arr[i]; // 将左边的元素放入临时数组 brri++; // 左边子数组的指针后移k++; // 临时数组的指针后移} else { // 如果左边的元素大于右边的元素brr[k] = arr[j]; // 将右边的元素放入临时数组 brrj++; // 右边子数组的指针后移k++; // 临时数组的指针后移}}while (j <= right) { // 复制右边子数组中剩余的元素brr[k++] = arr[j++];}while (i <= mid) { // 复制左边子数组中剩余的元素brr[k++] = arr[i++];}for (int i = left; i <= right; i++) { // 将合并后的有序数组复制回原数组 arrarr[i] = brr[i];}
}// 递归地将数组分成两半，并对每一半进行排序，然后合并
void Divide(int arr[], int len, int left, int right, int* brr) {if (left < right) { // 如果左边界小于右边界，则继续递归int mid = (left + right) / 2; // 计算中间索引Divide(arr, len, left, mid, brr); // 对左半部分递归调用 Divide 函数Divide(arr, len, mid + 1, right, brr); // 对右半部分递归调用 Divide 函数Merge(arr, len, left, mid, right, brr); // 合并两个有序子数组}
}// 归并排序的入口函数
void Merge_Sort(int arr[], int len) {int* brr = (int*)malloc(len * sizeof(int)); // 动态分配一个临时数组 brr，用于合并时存放数据if (brr == NULL) { // 如果内存分配失败fprintf(stderr, "Memory allocation failed\n"); // 打印错误信息到标准错误输出exit(EXIT_FAILURE); // 退出程序}Divide(arr, len, 0, len - 1, brr); // 从数组的起始索引到结束索引进行递归排序free(brr); // 释放临时数组 brr 的内存
}// 显示数组内容的函数
void Show(int arr[], int len) {for (int i = 0; i < len; i++) { // 遍历数组printf("%d ", arr[i]); // 打印数组的每个元素}printf("\n"); // 打印换行符
}int main() {int arr[] = {122, 222, 11, 357, 333, 12, 111, 789, 654, 356}; // 初始化一个待排序的数组int len = sizeof(arr) / sizeof(arr[0]); // 计算数组的长度Merge_Sort(arr, len); // 调用归并排序函数对数组进行排序Show(arr, len); // 显示排序后的数组return 0; // 程序正常结束，返回 0
}

1.2 递归排序（非递归）

#include <stdio.h>
#include <stdlib.h>// 函数声明，用于显示排序后的数组
void Show(int arr[], int len);// 合并两个有序子数组到临时数组brr中，然后再复制回原数组arr
void Merge(int arr[], int len, int left, int mid, int right, int* brr)
{int i = left;int j = mid + 1;int k = left;while (i <= mid && j <= right){if (arr[i] <= arr[j]){brr[k] = arr[i];i++;k++;}else{brr[k] = arr[j];j++;k++;}}while (j <= right){brr[k++] = arr[j++];}while (i <= mid){brr[k++] = arr[i++];}for (int i = left; i <= right; i++){arr[i] = brr[i];}
}// 非递归的分治函数
//gap是当前子数组的长度
void Merge_No_Recursion(int arr[], int len, int gap, int* brr)
{int left1 = 0;int right1 = left1 + gap - 1;int left2 = right1 + 1;int right2 = left2 + gap - 1 < len ? left2 + gap - 1 : len - 1;int k = 0;while (left2 < len){int i = left1;int j = left2;while (i <= right1 && j <= right2){if (arr[i] <= arr[j]){brr[k] = arr[i];i++;k++;}else{brr[k] = arr[j];j++;k++;}}while (j <= right2){brr[k++] = arr[j++];}while (i <= right1){brr[k++] = arr[i++];}left1 = right2 + 1;right1 = left1 + gap - 1;left2 = right1 + 1;right2 = left2 + gap - 1 < len ? left2 + gap - 1 : len - 1;}while (left1 < len){brr[k++] = arr[left1++];}for (int i = 0; i < len; i++){arr[i] = brr[i];}
}// 归并排序的非递归版本
void Merge_Sort_No_Recursion(int arr[], int len)
{int* brr = (int*)malloc(len * sizeof(int));if (brr == NULL)exit(EXIT_FAILURE);for (int gap = 1; gap < len; gap *= 2 ){Merge_No_Recursion(arr, len, gap, brr);}free(brr);
}// 显示数组的函数
void Show(int arr[], int len) {for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = { 120000, 230000, -100, 195, 71, 89, 42, 8, 902, 894, 194, 80, 194, 128, 90, 18, 490, 18, 409, 180, 95, 12, 489, 404 };int len = sizeof(arr) / sizeof(arr[0]);Merge_Sort_No_Recursion(arr, len);Show(arr, len);return 0;
}