C语言————排序算法网站首页 技术杂谈

C语言————排序算法

mc2356 2025-03-24 12:01:02

简介C语言————排序算法

在C语言中可以实现多种不同的排序算法，根据情景选取合适的算法可以减少排序消耗的时间，在c++中常用<algorithm>库中的sort函数快排（默认都是从小到大），本文讲解的多种排序实际上包含了多种算法思维，并不是单纯以排序为目的。

冒泡排序（Bubble Sort）

原理：比较相邻的元素，如果顺序错误就把它们交换过来，重复此步骤直到整个数组都被排序。每一轮比较都会将最大（或最小）的元素 “冒泡” 到数组的末尾。（这种相邻上下气泡大小的例子个人感觉不太形象）

代码实现：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

复杂度分析：
- 时间复杂度：O( $n^{2}$ )，其中n是数组的长度。这种排序是纯粹的硬排，逐个枚举。
- 空间复杂度：O(1)，只需要常数级的额外空间。

选择排序（Selection Sort）

原理：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。稍微有点贪心中的局部最优解的味道（实则不然）。

代码实现：

	for (int i = 0; i < len - 1; i++) {
		for (int j = 1 + i; j < len; j++) {
			if (arr[i] > arr[j]) {
				int temp = arr[j];//选择排序
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}

复杂度分析：
- 时间复杂度：O( $n^{2}$ )。
- 空间复杂度：O(1)。

插入排序（Insertion Sort）

原理：将未排序数据插入到已排序序列的合适位置。初始时，已排序序列只有一个元素，然后依次将未排序元素插入到已排序序列中，直到所有元素都被插入。
代码实现：
```
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
```
从i=1开始迭代，arr【0】是已经存在的，这种排法是维护双指针规律，首先key是要插入到有序部分中的值，如果没有while循环执行（即key>当前有序部分的最大值），直接把key放在最右边（实际上就是直接延伸了有序部分，相当于没改），arr【i】是有序序列外的第一个数，arr【j】是有序部分的最右值（从小到大排序，是最大值），如果新值key<有序内最大值，将大于key的值都右移，中间空出来的地方出入key。
复杂度分析：
- 时间复杂度：平均和最坏情况为 O( $n^{2}$ )，最好情况（数组已经有序）为O(n) 。
- 空间复杂度：O(1)。

快速排序（Quick Sort）

原理：采用分治法，选择一个基准值（pivot），将数组分为两部分，使得左边部分的所有元素都小于等于基准值，右边部分的所有元素都大于等于基准值，然后分别对左右两部分递归地进行排序。

代码实现：

void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;}// 交换两个元素的函数
int partition(int arr[], int low, int high) {// 分区函数
    int pivot = arr[high],i = low;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            swap(&arr[i++], &arr[j]);
        }
    }
    swap(&arr[i], &arr[high]);
    return i;
}
void quickSort(int arr[], int low, int high) {// 快速排序函数
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

取一个基准值，将元素划分（不均分），分区函数是每次区这个区间最右侧的为基准值，j是遍历到右边倒数第二个，i初始是区间最左，如果遍历到arr【j】比基准值小，和arr【i】交换位置，这样小的就在左侧了，遍历完后把基准值放在arr【i】的位置（遍历完了之后的此刻，arr【i】是比基准值大的数），再返回基准值（这一分界线）的索引，然后使用递归的方法，越分区间越小，最终有序化。

复杂度分析：
- 时间复杂度：平均情况为 O(n log n)，最坏情况为 O( $n^{2}$ )。
- 空间复杂度：平均情况为O(log n) ，最坏情况为 O(n)。主要是递归调用栈的空间开销。

归并排序（Merge Sort）

原理:采用分治法（Divide and Conquer）的思想来实现排序功能。归并排序的核心思想是将一个大问题分解为多个小问题，分别解决这些小问题，然后将小问题的解合并起来得到大问题的解。具体到排序问题上，归并排序把一个无序的数组不断地分成两个子数组，直到每个子数组只有一个元素（此时子数组自然是有序的），然后将这些有序的子数组合并成一个最终的有序数组。

算法步骤

归并排序主要分为两个步骤：“分” 和 “合”。

分（Divide）：
- 找到数组的中间位置，将数组分成左右两个子数组。
- 递归地对左右两个子数组分别进行 “分” 的操作，直到子数组中只有一个元素。因为单个元素的数组可以认为是有序的。
合（Merge）：
- 合并两个有序的子数组为一个新的有序数组。比较两个子数组的元素，依次选取较小的元素放入新数组中。
- 重复合并操作，直到所有子数组合并成一个完整的有序数组。

我们可以用满二叉树来看待这个过程，原第一代数组等分为第二代，第二代的两个又分成4个第三代，就像细胞分裂一样，最终的第四代就只剩一个元素了（假定一代有8个元素，总之最后就是第n代时，每个叶节点只剩1个元素了），这样就是递归分到底了。

接了下来进行回溯了，也就是合的过程，最末代的一组的两个数进行大小比较排序，回溯到上一代就是4个数进行排序，直到回溯到第一代，这时候多次局部有序化已经使得整个数组有序了。

代码实现：

分的过程直接递归实现，合的过程我们我们建立一个合并函数（merge），如果left>=right了说明已经分到最后一代了，每个节点只有一个元素了。

// 合并两个已排序的子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);// 创建临时数组
    // 拷贝数据到临时数组 L[] 和 R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    // 归并临时数组到 arr[left..right]
    int i = 0; // 初始化第一个子数组的索引
    int j = 0; // 初始化第二个子数组的索引
    int k = left; // 初始归并子数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {// 拷贝 L[] 的剩余元素
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {// 拷贝 R[] 的剩余元素
        arr[k] = R[j];
        j++;
        k++;
    }
}
// 归并排序函数
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;// 找到中间点
        mergeSort(arr, left, mid);// 递归排序左半部分
        mergeSort(arr, mid + 1, right);// 递归排序右半部分
        merge(arr, left, mid, right);// 合并已排序的两部分
    }
}

复杂度分析

时间复杂度：归并排序的时间复杂度始终为O(n log n) ，其中n是数组的长度。这是因为每次将数组分成两半需要O(log n)的时间，而合并两个子数组需要O(n)的时间，因此总的时间复杂度为O(n log n) 。n/ $2^{k}$ =1,k= $log_{2}n$ ,一共要分k次。
空间复杂度：归并排序的空间复杂度为O(n) ，主要是因为在合并过程中需要额外的临时数组来存储合并结果。

优缺点

优点：
- 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序前后保持不变。
- 时间复杂度稳定：无论输入数据的初始状态如何，归并排序的时间复杂度都是 O(n log n) ，性能较为稳定。
- 适用于链表等数据结构：由于归并排序不需要随机访问元素，因此也适用于链表等不支持随机访问的数据结构。
缺点：
- 空间复杂度较高：需要额外的 O(n) 空间来存储临时数组，对于大规模数据排序可能会占用较多的内存。

桶排序（Bucket Sort）

原理：桶排序（Bucket Sort）是一种非比较型的排序算法，其核心思想是将待排序的数据分到有限数量的桶里，每个桶再分别进行排序（通常会采用其他排序算法，如插入排序、快速排序等），最后把各个桶中的数据按照顺序合并起来，从而得到一个有序的序列。
实现步骤

确定桶的数量和范围：根据待排序数据的范围和分布，确定合适的桶数量，计算每个桶能够容纳的数据范围。
将数据分配到桶中：遍历待排序数组，根据数据的值将其放入对应的桶中。
对每个桶内的数据进行排序：可以选择合适的排序算法对每个桶内的数据进行排序。
合并所有桶中的数据：按桶的顺序依次取出每个桶中的数据，组成最终的有序数组。

代码实现：

先给总代码，之后逐步讲解。

// 桶排序函数
void bucketSort(vector<double> &arr) {
    if (arr.empty()) return;
    // 找到数组中的最小值和最大值(<algorithm>内的函数返回的是索引，不是常规max中的值)
    double min_val = *min_element(arr.begin(), arr.end());
    double max_val = *max_element(arr.begin(), arr.end());
    int num=1,bucket_num = arr.size()/num; // 确定桶的数量，这里简单设置为数组的长度
    vector<vector<double> > buckets(bucket_num);// 创建桶
    double bucket_range = (max_val - min_val) / bucket_num;// 计算每个桶的范围
    // 将数据分配到桶中
    for (double num: arr) {
        int index = static_cast<int>((num - min_val) / bucket_range);
        if (index == bucket_num) {
            index = bucket_num - 1;
        }
        buckets[index].push_back(num);
    }
    // 对每个桶内的数据进行排序
    for (auto &bucket: buckets) {
        sort(bucket.begin(), bucket.end());
    }
    // 合并所有桶中的数据
    int index = 0;
    for (const auto &bucket: buckets) {
        for (double num: bucket) {
            arr[index++] = num;
        }
    }
}

首先如果已知0=<n<=100000啥啥啥的，直接从把范围划分成【0，100000】即呆还占内存，所以准备工作第一步先找出最大值和最小值的索引，之后确定一个桶的数量，这个比较灵活，需要自己判断决定，决定了桶的数量之后每个桶的范围也就确定了，
接下下来进行分桶，逐个遍历确认所在范围入桶就行了，为了保险可以加一个保护措施（实际上多数情况下总范围不能整除桶数，余数都加在最后一个桶上了，有时候可能会桶越界，简单说就是最后一个桶是1.几）这里使用的是在 C++11 及以后的版本中，引入的基于范围的 for 循环，它提供了一种更简洁的方式来遍历容器或数组中的元素。对c++不了解的我在这里解释一下。了解的可以直接看下一步了。

for (declaration : range) {
    // 循环体
}

declaration：用于声明一个变量，该变量将在每次循环迭代时依次绑定到 range 中的元素。
range：表示要遍历的对象，可以是数组、容器（如 vector、list 等）或具有 begin() 和 end() 成员函数的其他对象。
```
for (double num: arr) {}
```
```
for(int i=0;i<arr.size();i++){}
```
这两个是等价的。第一个里面的num其实就是第二个中的i。

分桶之后，对每个桶进行桶内排序，局部有序化，由于是按范围分桶，所有整体也是有序的。

所有只需要简单组合到一个数组中就行了。

复杂度分析

时间复杂度：
- 平均情况下，桶排序的时间复杂度为 O(n+k)，其中 n是数组的长度，k是桶的数量。当k接近n时，时间复杂度接近线性。
- 最坏情况下，所有数据都被分配到同一个桶中，此时时间复杂度退化为 O( $n^{2}$ )，这取决于桶内排序算法的复杂度。
空间复杂度：桶排序的空间复杂度为O(n+k) ，主要用于存储桶和最终的有序数组。

适用场景

桶排序适用于数据分布均匀且数据范围不是特别大的场景，例如对一些浮点数进行排序，或者对年龄、成绩等具有一定范围的数据进行排序。

从这个例子中我们不难发现，桶排经常还快速排序sort协调排序

我们用两种方法排序并得到了以下结果（实际结果可能因机器性能而异）：

n	Bucket Sort (s)	Quick Sort (s)
10	0.000012	0.000008
100	0.000045	0.000032
1000	0.000350	0.000400
10000	0.003200	0.004500
100000	0.035000	0.050000
1000000	0.400000	0.600000

桶排是一种以空间换取时间的排序，快速排序在处理大量数据时耗时过多，所有可以使用桶排的思想分批快速排序，减少排序耗时。

我们给出的代码实际上是桶优化的快排，这里我们再说一下最基本的桶排序：

例如，对n个小于100000个int型数据进行排序

vector<int> v(n, 0),arr(100000,0),ans;
    for (int i = 0; i < n; i++) {cin >> v[i];arr[v[i]]++;}
    for (int i = 0; i < 100000; i++) {
        while(arr[i]--) {ans.push_back(i);}
    }

每个小于100000的数自成一个桶，统计出现个数然后按序加入数字就能实现排序，只是比较消耗内存，这里v数组也就是原数组实际上可以省略，那么每个元素都会被操作2次，一次统计，一次合并，这是一个O（n）的排序。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。