#C++小知识# 1.那些不同的排序算法

userId_undefined

C++真真真难啊啊啊

倔强青铜

2024-11-08 15:20:54

发布于：上海

505阅读
0回复
0点赞

总所周知，排序是一种十分重要的知识
所以呢，我就想简单地讲一些常用的排序
若有遗漏，请补充，thanks
点赞过100更新下一期
(Macw07都点赞了，你不来看看)
The First part（What is 排序）:
排序的定义：

简单来说，就是将一组数据（通常是一个列表、数组或任何可以遍历的集合）按照某种特定的顺序重新排列的过程。这个特定的顺序可以是从小 到大、从大到小、按照字母顺序、根据某个属性的值等等。排序的目的是让数据变得有序，便于后续的查找、分析或处理。

举个例子来说明排序的过程：

假设你有一堆乱序的卡片，每张卡片上写着一个数字。现在，你希望将这些卡片按照数字的大小顺序重新排列。这个过程就是排序。你可以通过比较相邻卡片的数字大小，然后交换它们的位置（如果它们的顺序不符合你的要求），重复这个过程直到所有的卡片都按照你想要的顺序排列好。

The second Part (不同的的排序):

1.冒泡排序（Bubble Sort)

定义：‌冒泡排序‌是一种简单的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大，则交换两数位置，这样，每一轮遍历都将当前未排序部分中的最大值“浮”到未排序部分的末尾。这个过程重复进行，直到整个数列都有序为止。由于越大的元素会逐渐“浮”到数列的顶端，因此这种排序算法被形象地称为冒泡排序。

视频展示：https://i-blog.csdnimg.cn/blog_migrate/8a300c4d3f82b20977174713fd7cb886.gif

代码：

#include<iostream>
using namespace std;
int main(){
    int n,a[110];
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }for(int i = 1;i < n;i++){
        for(int j = 0;j < n - 1;j++){
            if(a[j] > a[j + 1]) swap(a[j],a[j+1]);
        }
    }for(int i = 0;i < n;i++){
        cout << a[i] << " ";
    }
    return 0;
}
输入：
5
89 92 85 80 69
输出：
69 80 85 89 92

2.选择排序（Selection Sort）

定义：‌选择排序是一种简单直观的排序算法，其基本思路是在未排序的序列中找到最小（或最大）元素，然后将其存放到序列的起始位置

视频展示：https://5b0988e595225.cdn.sohucs.com/images/20200513/312439ee96f0451d99b20685a054d2d2.gif

代码：

#include <iostream>
using namespace std;
int main(){
    int n,a[110],k;
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }for(int i = 0;i < n - 1;i++){
        k = i;
        for(int j = i+1;j < n;j++){
            if(a[k] > a[j]){
                k = j;
            }
        }swap(a[k],a[i]);
    }for(int i = 0;i < n;i++){
        cout << a[i] << " ";
    }
    return 0;
}
//输入：
5
6 5 1 3 2
//输出: 
1 2 3 5 6

3.插入排序（Insertion Sort）

定义：插入排序是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

视频展示：https://img2018.cnblogs.com/blog/1757387/201910/1757387-20191017212916558-1582886173.gif

代码：

#include<iostream>
using namespace std;
int main(){
    int n,a[110];
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }for(int i = 1,j;i < n;i++){
        j = i;
        while(j >= 1 && a[j - 1] > a[j]){
            swap(a[j - 1],a[j]);
            j--;
        }
    }for(int i = 0;i < n;i++){
        cout << a[i] << " ";
    }
    return 0;
}
//输入：
5
6 5 1 3 2
//输出：
1 2 3 5 6

4.桶排序：

定义： 工作原理是将数组分 into 几个桶，每个桶分别排序，然后按顺序输出。它是一种稳定的排序算法，适用于一些特定的场景，例如数据分布均匀的情况。

图片展示：https://image-static.segmentfault.com/394/203/3942036120-81b89dadc641bc15_fix732

代码

#include<iostream>
using namespace std;
int main(){
    int n,t,a[101] = {};
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> t;
        a[t]++;
    }for(int i = 1;i <= 100;i++){
        while(a[i]--){
            cout << i << " ";
        }
    }
    return 0;
}
//输入：
6
45 100 45 2 100 45
//输出：
2 45 45 45 100 100

5.计数排序 （桶排序的优化）

定义：‌简单描述就是，在一个有确定范围的整数空间中，建立一个长度更大的数组，如当输入的元素是 n 个 0 到 k 之间的整数时，建立一个长度大于等于k的数组。该数组的每一个下标位置的值代表了数组中对应整数出现的次数。根据这个统计结果，直接遍历数组，输出数组元素的下标值，元素的值是几， 就输出几次。

图片展示： https://bkimg.cdn.bcebos.com/pic/5366d0160924ab18d9ef57593bfae6cd7a890be6?x-bce-process=image/format,f_auto/quality,Q_70/resize,m_lfit,limit_1,w_536

代码：

#include<iostream>
#include<vector>

using namespace std;

void CountSort(vector<int>&);

int main() {
  vector<int> test = { 3, 3, 6, 2, 5, 1, 2, 8 };
  CountSort(test);
  for (auto x : test)
    cout << x << " ";
  return 0;
}

int FindMax(vector<int> arr) {
  int max = 0;
  for (auto x : arr)
    if (x > max)
      max = x;
  return max;
}

void CountSort(vector<int>& arr) {
  int max = FindMax(arr);
  vector<int> count(max+1,0);   //需要分配数组大小,节省了数组空间

  for (int i = 0; i < arr.size(); i++) {  //开始计数
    count[arr[i]]++;   //
  }

  int index = 0;
  for (int k = 0; k <count.size(); k++) {
    for (int cnt = 0; cnt < count[k]; cnt++)
      arr[index++] = k;
  }
}//直接给输入了
//输出：1 2 2 3 3 5 6 8

6.归并排序

定义: 将已有序的子序列合并以得到完全有序的序列。归并排序的核心思想是将一个大问题分解为小问题，然后递归地将这些小问题合并起来以解决大问题。具体来说，归并排序的步骤包括：

1.分解‌：将数组分割成两个较小的子数组，直到每个子数组只包含一个元素。
2‌.合并‌：将两个已排序的子数组合并成一个大的有序数组。

补充：归并排序由约翰·冯·诺伊曼发明

视频与图片展示： https://i-blog.csdnimg.cn/blog_migrate/ea2dc22d7869f262a987fc78c2fed5dd.png#pic_center
https://i-blog.csdnimg.cn/blog_migrate/4e5b705de8ab41ca710b3412fa3ee070.gif#pic_center

代码：

#include<iostream>
using namespace std;
int n;
int a[1005],c[1005]; 
void m_sort(int l,int r){
	int m=(l+r)/2; 
	if(l>=r) return;
	m_sort(l,m);
	m_sort(m+1,r);
	int i=l,j=m+1,k=l;
	while(i<=m && j<=r){
		if(a[i]<=a[j]){
			c[k++]=a[i++]; 
		}else{
			c[k++]=a[j++];
		}
	}
	while(i<=m) c[k++]=a[i++];
	while(j<=r) c[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=c[i];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	m_sort(1,n);
    for(int i=1;i<=n;i++){
     	cout<<a[i]<<" ";   
    }
	return 0;
}
//输入：
5
4 2 4 5 1
//输出：
1 2 4 4 5

7.快速排序

定义： 将未排序元素根据一个作为基准的"主元"分为两个子序列，其中一个子序列的记录均大于主元，而另一个子序列均小于主元，然后递归地对这两个子序列用类似的方法进行排序

视频展示： https://pic4.zhimg.com/v2-671296f1b5e64b40d75605460ef6ed3f_b.webp

代码

#include <iostream>
using namespace std;
int a[10010];
int n;
int partition(int a[],int l,int r){
    int k=a[l];
    while(l<r){
        while(l<r&&a[r]>=k){
            r--;
        }
        a[l]=a[r];
        while (l<r&&a[l]<=k){
            l++;
        }
        a[r]=a[l];
    }
    a[l]=k;
    return l;
}
void QuickSort(int a[],int l,int r){
    if(l>=r)return ;
    int pos =partition(a,l,r);
    QuickSort(a,l,pos-1);
    QuickSort(a,pos+1,r);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    QuickSort(a,1,n);
    for(int i = 0;i < n;i++){
     	cout << a[i] << " ";   
    }
    return 0;
}
//输入：
5
2 3 9 4 5
//输出：
2 3 4 5 9

8.希尔排序：

核心思想：

先进行预排序，让数组接近有序；
直接插入排序

视频展示： https://img.jbzj.com/file_images/article/202205/2022051810363218.gif

代码：

#include <iostream>
#include <vector>
using namespace std;
 
void shellSort(vector<int> &arr, int n) {
    // Start with a large gap, and reduce gap by factor of 2
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do insertion sort for all groups
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}
 
// Main function to test above
int main() {
    vector<int> arr = {12, 34, 54, 2, 3};
    int n = arr.size();
    shellSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}
//输入：已有
//输出：2 3 12 34 54

8.堆排序：

定义： 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

视频展示 堆排序

代码：

#include <iostream>
using namespace std;

// 调整堆
void heapify(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(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);
    }
}

// 输出数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array is \n";
    printArray(arr, n);
    return 0;
}

9.基数排序

定义： 基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较。通常使用的是按照低位先排序，然后收集；再按照高位排序，然后再收集；依此类推，直到最高位。有时也采用基于计数排序或桶排序来实现每个位的排序。

视频展示： https://atts.w3cschool.cn/attachments/day_230919/202309191112272949.png

代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序函数，根据数组中数字的指定位进行排序
void countingSort(vector<int>& arr, int exp) {
    vector<int> output(arr.size());  // 存储排序后的输出数组
    int count[10] = {0};  // 计数数组，基数为10（0到9）

    // 计算每个位的出现次数
    for (int i = 0; i < arr.size(); i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // 调整计数数组，使其包含实际的位置信息
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将输出数组复制回原数组，以便数组按当前位排序
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

// 主函数，使用基数排序对数组进行排序
void radixSort(vector<int>& arr) {
    // 找出数组中的最大数，以确定数字的最大位数
    int m = *max_element(arr.begin(), arr.end());

    // 对每个位进行计数排序。注意，这里传递的是位数的指数，即10的幂
    for (int exp = 1; m / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// 打印数组的功能函数
void print(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

// 驱动程序代码
int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    cout << "排序后的数组: ";
    print(arr);
    return 0;
}

The Third Part(不同排序的时间复杂度，空间复杂度，稳定性)

在C++中，常见的排序算法时间复杂度如下：

冒泡排序（Bubble Sort）：O(n^2)

选择排序（Selection Sort）：O(n^2)

插入排序（Insertion Sort）：O(n^2)

快速排序（Quick Sort）：平均O(n log n)，最坏O(n^2)

归并排序（Merge Sort）：O(n log n)

计数排序（Counting Sort）：O(n+k)（当k是数组中的最大值时）

桶排序（Bucket Sort）：O(n+k)

希尔排序（Shell Sort）：O(n log n) ~ O(n^2)

堆排序：O(nlogn)

在C++中，常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。下面是一些常见排序算法的空间复杂度：

冒泡排序（Bubble Sort）：O(1)

插入排序（Insertion Sort）：O(1)

选择排序（Selection Sort）：O(1)

快速排序（Quick Sort）：最坏情况O(n)，平均O(log n)

归并排序（Merge Sort）：O(n)

希尔排序：O(n^2)

桶排序: O(n^2)

计数排序：O(n + k) k是最大位数

堆排序：O(n)

稳定性：
不稳定：快速排序，希尔排序，选择排序,堆排序
稳定：剩余的

好啦，以上的排序，你用过几个呢？
（持续更新中...）

第二集已出，麻烦看一下 第二集

userId_undefined
去预览
0/2000

全部评论 16

热门讨论