C++ 三种常见排序算法实现与分析：冒泡排序、快速排序、归并排序

本文将介绍三种常见的排序算法：冒泡排序、快速排序和归并排序，并提供 C++ 代码实现和分析。

1. 冒泡排序

冒泡排序是最简单的排序算法之一，其基本思想是重复遍历待排序序列，比较相邻元素的大小，如果顺序错误就交换它们的位置，直到没有相邻元素需要交换为止。

**代码实现：**c++#include #include #include <stdlib.h>#include #include #include

using namespace std;

int size=10000; //随机数大小范围bool a; //冒泡中判断值int arr_zx[100000]; //归并中临时数组double arr_fd[100000];char arr_zf[100000];

//冒泡排序(整型)void function_mp_zx(int dp_zx[],int num){ if(num<=1){ return; } int sl_zx=num-2; int itmp_zx=0; //中间量 while(sl_zx>=0){ a=false; for(int i=0;i<=sl_zx;i++){ if(dp_zx[i]>dp_zx[i+1]){ itmp_zx=dp_zx[i]; dp_zx[i]=dp_zx[i+1]; dp_zx[i+1]=itmp_zx; a=true; } } if(a==false){ break; } sl_zx--; }}//冒泡排序(浮点型)// ... (代码同上，仅数据类型不同)

//冒泡排序（字符型）// ... (代码同上，仅数据类型不同)

算法分析：

时间复杂度： 最坏情况下为 O(n^2)，最好情况下为 O(n)* 空间复杂度： O(1)* 稳定性： 稳定

2. 快速排序

快速排序是一种高效的排序算法，其基本思想是选择一个基准元素，将数组分成两个子数组，其中一个子数组的所有元素都小于等于基准元素，另一个子数组的所有元素都大于等于基准元素，然后递归地对子数组进行排序。

**代码实现：**c++//快速排序（整型）void function_ks_zx(int dp_zx[], int low, int high) { if (low < high) { // 待排序区间至少有两个元素 int pivot = dp_zx[low]; // 选取最左侧元素作为基准元素 int i = low + 1; // i 指向待排序区间的第二个元素 int j = high; // j 指向待排序区间的最后一个元素

    while (i <= j) {            while (i <= j && dp_zx[i] < pivot) {                i++;  // 在左侧寻找第一个大于或等于 pivot 的元素            }            while (i <= j && dp_zx[j] > pivot) {                j--;  // 在右侧寻找第一个小于或等于 pivot 的元素            }            if (i <= j) {  // 如果 i 和 j 尚未交错，则交换 arr[i] 和 arr[j]                swap(dp_zx[i], dp_zx[j]);                i++;                j--;            }        }

    swap(dp_zx[low], dp_zx[j]);  // 将基准元素交换到正确的位置        int mid = j;

    // 对左侧子区间递归排序        function_ks_zx(dp_zx, low, mid - 1);        // 对右侧子区间递归排序        function_ks_zx(dp_zx, mid + 1, high);    }}//快速排序（浮点型）// ... (代码同上，仅数据类型不同)

//快速排序（字符型）// ... (代码同上，仅数据类型不同)

算法分析：

时间复杂度： 平均情况下为 O(nlogn)，最坏情况下为 O(n^2)* 空间复杂度： 平均情况下为 O(logn)，最坏情况下为 O(n)* 稳定性： 不稳定

3. 归并排序

归并排序是一种稳定的排序算法，其基本思想是将数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。

**代码实现：**c++//归并排序（整型）void function_gb_zx(int dp_zx[],int l, int r){ if(l >= r) { return; } int mid = (l + r) / 2; function_gb_zx(dp_zx,l, mid); function_gb_zx(dp_zx,mid + 1, r); int i = l, j = mid + 1, k = l; while(i <= mid && j <= r){ if(dp_zx[i] <= dp_zx[j]) { arr_zx[k ++] = dp_zx[i ++]; } else { arr_zx[k ++] = dp_zx[j ++]; } } while(i <= mid) { arr_zx[k ++] = dp_zx[i ++]; } while(j <= r) { arr_zx[k ++] = dp_zx[j ++]; } for(int i = l; i <= r; i ++){ dp_zx[i] = arr_zx[i]; }}//归并排序（浮点型）// ... (代码同上，仅数据类型不同)

//归并排序（字符型）// ... (代码同上，仅数据类型不同)

算法分析：

时间复杂度： O(nlogn)* 空间复杂度： O(n)* 稳定性： 稳定

4. 代码分析

数据生成： 代码中定义了全局变量 size 来控制随机生成数据的范围。* 函数定义： 代码中定义了三个函数分别实现冒泡排序、快速排序和归并排序，每个函数都针对三种数据类型（整型、浮点型和字符型）进行了实现。* 排序过程： 代码中可以修改排序函数的调用次数来实现同一数据多次排序的功能。

5. 总结

本文介绍了三种常见的排序算法，并提供了 C++ 代码实现和分析。可以根据实际需求选择合适的排序算法