一只猪

用户名：TuT99

访问量：11768

签　名：

拥有良好的积累，并且一直在路上，我相信自己有无限的可能

等　　级
排　　名	70
经　　验	10251
参赛次数	6
文章发表	68
年　　龄	21
在职情况	学生
学　　校	哔哩哔哩大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

使用C++和Qt写的连连看小游戏
浏览：75

使用C++和QT实现的2D超级玛丽
浏览：70

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C++常用算法和数据结构（STL）

　　作者: 一只猪　　　　发表时间：2023-06-23 00:14:06 浏览：77　|　评论：0　

##  主要是分享 其次是想偷懒（写了之后自己可以参考）原文中还有一些没有参透的点 写的不是很好
### 1、排序
##### 1.1、冒泡排序
###### 原理：
是从待排序序列的左边开始，依次比较相邻的两个元素，比较大小并将较大的数进行交换，一直比较到数组的右侧，确保当前序列中最大的数到达了最右边。接下来将序列长度缩小一步，重复上述过程，直到序列有序。
###### 缺点：
1、不适用于大量数据的排序
2、缺乏效率
###### 优点
1、但原理简单，很容易实现
###### 复杂度：
时间复杂度为O(N^2)
空间复杂度为O(1)
```cpp
#include <iostream>
#include <vector>

using namespace std;

void bubbleSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n - 1; i ++) {
        for (int j = 0; j < n - i - 1; j ++) {
            if (vec[j] > vec[j+1]) {
                int tmp = vec[j];
                vec[j] = vec[j+1];
                vec[j+1] = tmp;
            }
        }
    }
}

int main() {
    vector<int> vec = {5, 8, 1, 3, 9, 10, 2, 4, 6, 7};
    bubbleSort(vec);

for (int i = 0; i < vec.size(); i ++) {
        cout << vec[i] << " ";
    }
    cout << endl;

return 0;
}
```
##### 1.2选择排序
###### 原理：
是在待排数组中选择最小（或最大）的元素，与数组的第一个元素交换位置，再在剩余的元素中选择最小值，与数组的第二个位置交换，以此类推，直到数组有序为止。
###### 缺点：
1、在时间效率问题不太行
###### 优点：
易于实现
###### 复杂度：
时间复杂度O(N^2)
空间复杂度为O(1)
```cpp
#include <iostream>
#include <vector>

using namespace std;

void selectionSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n - 1; i ++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j ++) {
            if (vec[j] < vec[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = vec[i];
            vec[i] = vec[minIndex];
            vec[minIndex] = tmp;
        }
    }
}

int main() {
    vector<int> vec = {5, 8, 1, 3, 9, 6, 2, 7, 4, 10};
    selectionSort(vec);

for (int i = 0; i < vec.size(); i ++) {
        cout << vec[i] << " ";
    }
    cout << endl;

return 0;
}
```
#####1.3 插入排序
###### 原理：
是将数组视为两部分：已排序和未排序。在已排序部分中寻找合适的位置插入未排序部分的第一个元素，插入后将已排序部分的长度增加1，重复以上操作直至数组有序。
插入排序的基本思路如下：

1、从第一个元素开始，该元素可以认为已经被排序；
2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
4、重复步骤3，直到找到已排序的元素小于或等于新元素的位置；
5、将新元素插入到该位置后；
重复步骤2~5。
###### 缺点：
在处理大规模的数据排序时，效率下降
###### 优点：
实现简单，容易理解，可读性强，适用于小规模数据排序、部分有序的数据排序以及数据集规模较小的情况。
###### 复杂度：
时间复杂度为O(N^2)
空间复杂度为O(1)
```cpp
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = { 12, 11, 13, 5, 6 ,7, 1, 2, 4};
    insertionSort(arr);
    for (auto i : arr) {
	//C++11中的range-based for循环，也被称为foreach循环。这个循环可以遍历容器中的所有元素，这里用于遍历vector容器arr中所有元素。在每次循环迭代中，i被赋值为当前迭代的元素的值，然后输出到标准输出流中。
    cout << i << " ";
    }
    return 0;
}
```
##### 1.4快速排序(不稳定的排序方法)
###### 原理：
通过选择一个pivot（基准），以此为基准将数组分为两个子数组，使得左子数组中的每个元素都小于等于基准，右子数组中的每个元素都大于基准，然后对子数组进行递归排序。
基本流程如下：
1、从数组中选择一个元素作为基准点（pivot），通常为数组中间的元素
2、将数组中小于基准点的元素放在基准点的左侧，大于基准点的元素放在基准点的右侧；
3、对基准点左侧和右侧的子数组分别递归执行以上操作。
###### 缺点：
对部分有序的情况下，效率下降
###### 优点：
适用于大多数情况，在大规模随机的数据效率高
###### 复杂度：
时间复杂度为O(nlongn)
空间复杂度为O(longn)
最坏的情况时间复杂度为O(n^2)

```cpp
//使用 partition 函数来找到排序数组的分区位置，这个函数会根据传入的参数对数组进行分区，使得左区间的元素都小于右区间的元素。在 partition 函数中，我们选择数组中间的数作为 ‘基准’（pivot），然后以此为基准，将数组中小于基准的移到左边，较大的移到右边，最终返回 pivot 的位置。在 quickSort 函数中，我们递归地调用 partition 函数，在分区点的左右两侧分别对子数组进行排序。
#include <iostream>
#include<cmath>
#include <vector>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; ++j) {
        if (arr[j] < pivot) {
            ++i;
        swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<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);
    }
}

int main() {
    vector<int> arr = { 10, 7, 8, 9, 1, 5 , 2, 3, 4};
    int n = arr.size();
    quickSort(arr, 0, n - 1);
    for (auto i : arr) {
        cout << i << " ";
    }
 
    return 0;
}
```
##### 1.5归并排序
###### 原理：
采用分治法的思想，递归地将数组分成两个部分，最终将它们分别排序合并成一个有序的数组。其基本原理可以概括为以下三个步骤：
1、将原始数组以中点位置为界限分成两个子数组；
2、递归调用归并排序算法让两个子数组分别有序；
3、合并两个有序的子数组成为一个有序的数组。
###### 缺点：
1、归并排序算法需要申请额外的空间来存放排序后的数组，因此空间复杂度较高，不适合在内存受限的情况使用；
2、归并排序算法需要递归地调用过程，因此对栈空间的开销也比较高；
归并排序算法的常数因子较大，在许多情况可能被快排等效或超越。
优点：稳定性高
对于大规模的数据排序任能保持较高的效率
###### 复杂度：
总的时间复杂度为O(nlongn)
空间复杂度为O(n)
```cpp
//使用 merge 函数来对已排序的数组进行分组以及合并操作，其中参数left、mid和right分别指的是左半部分轮廓的起始位置，左半部分轮廓的结束位置，和右半部分轮廓的结束位置。我们需要在该函数中创建两个辅助向量，将数组从 left 到 mid 处分为 L，从 mid+1 到 right 处分为 R。接着，我们通过比较 L 和 R 中的元素大小，逐步将较小的元素按顺序放回数组中。最后，我们递归将数组分为两半，并对它们进行排序，最终合并得到有序数组。
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    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];
    }
    int i = 0, j = 0, 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) {
        arr[k] = L[i];
        ++i;
        ++k;
    }
    while (j < n2) {
        arr[k] = R[j];
        ++j;
        ++k;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    vector<int> arr = { 12, 11, 13, 5, 6, 7, 8, 1, 2};
    int n = arr.size();
    mergeSort(arr, 0, n - 1);
   
    for (auto i : arr) {
        cout << i << " ";
    }

return 0;
}
```
 ###### 1.6堆排序
###### 原理：
利用堆这种数据结构而设计的一种排序算法，堆是可以被看成一棵树的数组对象。堆分为最大堆和最小堆两种形式，最大堆的每个节点都大于等于其子节点，最小堆的每个节点都小于等于其子节点。
堆排序的基本原理可以概括如下：
1、建立堆：将原始数组通过堆化操作（将其转化为一个最大堆或最小堆）构建为一个堆；
2、将堆的根节点与堆的最后一个节点进行互换，去除已排序的值，重新堆化（重新调整堆的操作）；
重复步骤2，直到堆的大小为1.
缺点：常数因子较大；不稳定的排序算法
###### 优点：
1、时间复杂度为O(nlongn),性能较好
2、不需要使用额外的空间进行排序，空间复杂度为O(1);
3、可以进行原地排序，占用内存空间较小
4、对于大规模的数据排序仍能保持较高的效率
###### 复杂度：
时间复杂度为O(nlongn)
由于堆已经被存储在原来的数组中，所以空间复杂度为O(1)
```cpp
//使用 heapify 函数来将元素最大堆化，以确保堆排序的正确性。该函数的作用是检查给定索引位置 i 和其子树是否为最大堆。首先，我们将 i 节点的值与其左右子树节点的值进行比较，并将最大值保存为 largest。随后，如果 largest 不等于 i，则交换 i 与 largest 的值，并递归的应用 heapify 函数到 largest 节点，以便保持堆的性质。

对于 heapSort 函数，首先将给定数组构建成最大堆，然后将堆的根节点置于数组的最后，并减小堆的大小。随后，我们重新调整堆的根节点以再次维护堆的最大堆性质，并重复上述步骤直到整个数组排序完成。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    vector<int> arr = { 12, 11, 13, 5, 6, 7, 1, 2, 3, 4  };
    int n = arr.size();
    heapSort(arr, n);
    for (auto i : arr) {
    cout << i << " ";
    }
    return 0;
}
```
##### 1.7基数排序
##### 原理：
通过将每个数字拆分成单个数字（位）的形式来实现的，随着键值位数的增加，以矩阵式排序即可对越高位数字排序。基数排序通常用于多键排序。具体来说，我们使用计数排序算法的思想，以位为基础，从最低位到最高位进行排序。在每一位上，我们根据当前位数上的值来分派元素到大小为10的桶中。注意，我们需要在排序过程中重复使用计数排序算法，以便分别对基数排序的各位进行排序。
基数排序的基本原理可以概括如下：
1、将待排序元素中的每个元素，按照个、十、百…位分别排序；
2、对分配到同一个桶的元素，按照桶位置从前往后合并；
3、将元素依次（从高到低位）放回原数组。
具体来说，基数排序的过程可以划分为以下几个步骤：
1、找到数组中最高位数字，计算数值的位数
2、从最低位到最高位，对每个数位进行排序，可以选择实现计数排序、桶排序等算法
3、当各数位排序完成后，将它们依次组合起来，形成新的序列并得到排序结果
###### 缺点：
1、基数排序的算法时间复杂度为O(d(n+k))，其中d是数字的位数，n是对象数量，k是基数数量，虽然它在空间复杂度方面表现良好，但在时间复杂度方面往往较差
2、实现基数排序的过程较为繁琐，需要开辟多个桶进行排序
3、当数据所处范围不是很大时，基数排序效率提升空间不大
######  优点：
1、适用于大量的数据排序，在数据量越大的情况越优秀
2、稳定的排序算法，保证排序前后的元素顺序不变
3、与桶排序、计数排序等数值排序方法不同，基数排序可以适用于字符串等非数字数据的排序
###### 复杂度：
基数排序的空间复杂度取决于计数排序、桶排序等算法的空间占用情况，以及该算法所需开辟的辅助空间。在基数排序的实现中，核心步骤是对数据进行分配和收集到桶里的过程，而桶排序所需的额外空间是O(n)。同时，为避免数据交换过程中的污染问题，一般会新开一个长度为n的辅助数组，用于存放排序后的结果。
因此，基数排序的空间复杂度由于开辟桶和辅助数组而确定，即O(n+k)。其中，n代表待排序元素的数量，k代表基数的范围。
需要注意的是，基数排序的时间复杂度为O(d(n+k))，其中d是数字的位数，n是对象数量，k是基数数量。在实践中，当k很大时，常数因子较大，效率可能不如常见的排序算法。因此，相较于时间复杂度而言，基数排序更擅长于处理数据范围小、位数较少的排序问题，其空间复杂度相对较低，更适合处理大规模数据的排序。
```cpp
#include <iostream>
#include <vector>
#include<algorithm> //max_element头文件
// countingSort 函数，用于对数组进行计数排序。然后，我们定义了一个最大值变量max，用于计算需要进行排序的数组的最大位数。最终述通过 radixSort 函数完成基数排序。它通过将数字按照位数从个位到十位、百位，和千位等依次进行排序来实现。
using namespace std;
void countingSort(vector<int>& arr, int n, int exp) {
    vector<int> output(n), count(10, 0);
    for (int i = 0; i < n; ++i) {
        int index = (arr[i] / exp) % 10;
        ++count[index];
    }
    for (int i = 1; i < 10; ++i) {
        count[i] += count[i - 1];
    }
    for (int i = n - 1; i >= 0; --i) {
        int index = (arr[i] / exp) % 10;
        output[count[index] - 1] = arr[i];
        --count[index];
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = output[i];
    }
}

void radixSort(vector<int>& arr, int n) {
    int max = *max_element(arr.begin(), arr.end());
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    int n = arr.size();
    radixSort(arr, n);
    for (auto i : arr) {
    cout << i << " ";
    }
    return 0;
}
```
##### 基数排序的适合的场景
基数排序在处理大量数据时性能表现优秀，尤其是面对数据范围小、位数不多的情况，更加适合。对于一些常见的场景，基数排序往往比其他排序算法更为有效。比如：
当数据所处范围较小时，基数排序表现优秀。
例如，对于0到10的数字进行排序，基数排序的效率会很高，而快速排序、归并排序等常规排序算法则可能表现较差。
对于大量数据的排序，基数排序往往比插入排序等其他简单排序算法更快。例如，对于数值范围在10万以上的大规模数据进行排序，基数排序的效率通常比快速排序等算法更高。

##  写这个的期间还有几个问题没处理好，代码和原文中出现错误是在所难免，还请在评论区进行指正

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一只猪

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C++常用算法和数据结构（STL）

评论区

精彩推荐

C二级辅导-计负均正（C语言代码）

回文串（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

【偶数求和】（C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

求组合数（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

【偶数求和】（C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

一只猪

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

汽水瓶 （C语言代码）怎么答案错误？？？？？

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C++常用算法和数据结构（STL）

评论区

精彩推荐

C二级辅导-计负均正 （C语言代码）

回文串 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

【偶数求和】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

求组合数 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

【偶数求和】 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

汽水瓶（C语言代码）怎么答案错误？？？？？

　　评论区

C二级辅导-计负均正（C语言代码）

回文串（C语言代码）

【偶数求和】（C语言代码）

求组合数（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

【偶数求和】（C语言代码）