#C++小知识# 1.那些不同的排序算法
2024-09-18 11:01:43
发布于:上海
总所周知,排序是一种十分重要的知识
所以呢,我就想简单地讲一些常用的排序
若有遗漏,请补充,thanks
点赞过100更新下一期
(Macw07都点赞了,你不来看看)
The First part(What is 排序):
排序的定义:
简单来说,就是将一组数据(通常是一个列表、数组或任何可以遍历的集合)按照某种特定的顺序重新排列的过程。这个特定的顺序可以是从小 到大、从大到小、按照字母顺序、根据某个属性的值等等。排序的目的是让数据变得有序,便于后续的查找、分析或处理。
举个例子来说明排序的过程:
假设你有一堆乱序的卡片,每张卡片上写着一个数字。现在,你希望将这些卡片按照数字的大小顺序重新排列。这个过程就是排序。你可以通过比较相邻卡片的数字大小,然后交换它们的位置(如果它们的顺序不符合你的要求),重复这个过程直到所有的卡片都按照你想要的顺序排列好。
The second Part (不同的的排序):
1.冒泡排序(Bubble Sort)
定义:冒泡排序是一种简单的排序算法,其基本思想是:在待排序的一组数中,将相邻的两个数进行比较,若前面的数比后面的数大,则交换两数位置,这样,每一轮遍历都将当前未排序部分中的最大值“浮”到未排序部分的末尾。这个过程重复进行,直到整个数列都有序为止。由于越大的元素会逐渐“浮”到数列的顶端,因此这种排序算法被形象地称为冒泡排序。
视频展示:冒泡排序
代码:
#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)
定义:选择排序是一种简单直观的排序算法,其基本思路是在未排序的序列中找到最小(或最大)元素,然后将其存放到序列的起始位置
视频展示:选择排序
代码:
#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)
定义:插入排序是一种简单直观的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
视频展示:插入排序
代码:
#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
7.桶排序:
定义: 工作原理是将数组分 into 几个桶,每个桶分别排序,然后按顺序输出。它是一种稳定的排序算法,适用于一些特定的场景,例如数据分布均匀的情况。
图片展示:桶排序
代码
#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
4.计数排序 (桶排序的优化)
定义:简单描述就是,在一个有确定范围的整数空间中,建立一个长度更大的数组,如当输入的元素是 n 个 0 到 k 之间的整数时,建立一个长度大于等于k的数组。该数组的每一个下标位置的值代表了数组中对应整数出现的次数。根据这个统计结果,直接遍历数组,输出数组元素的下标值,元素的值是几, 就输出几次。
图片展示:计数排序
代码:
#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
5.归并排序
定义: 将已有序的子序列合并以得到完全有序的序列。归并排序的核心思想是将一个大问题分解为小问题,然后递归地将这些小问题合并起来以解决大问题。具体来说,归并排序的步骤包括:
1.分解:将数组分割成两个较小的子数组,直到每个子数组只包含一个元素。
2.合并:将两个已排序的子数组合并成一个大的有序数组。
补充:归并排序由约翰·冯·诺伊曼发明
代码:
#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
6.快速排序
定义: 将未排序元素根据一个作为基准的"主元"分为两个子序列,其中一个子序列的记录均大于主元,而另一个子序列均小于主元,然后递归地对这两个子序列用类似的方法进行排序
视频展示:快速排序
代码
#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
7.桶排序:
定义: 工作原理是将数组分 into 几个桶,每个桶分别排序,然后按顺序输出。它是一种稳定的排序算法,适用于一些特定的场景,例如数据分布均匀的情况。
图片展示:桶排序
代码
#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
8.希尔排序:
核心思想:
先进行预排序,让数组接近有序;
直接插入排序
视频展示:希尔排序
代码:
#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;
}
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(n)
在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(nlogn)
稳定性:
不稳定:快速排序,希尔排序,选择排序
稳定:剩余的
好啦,以上的排序,你用过几个呢?
(持续更新中...)
请直接看9:
1.你学废了吗
2.去1
3.你看3干嘛,让你看5
4.GO TO SIX(去6)
5.呜呜呜,你咋么不看7
6.终于来了,去2
7.你看懂排序了吗,看懂了看8,没看懂也看8
8.看4
9.没有东西,就是让你看3
全部评论 2
@AC君
2天前 来自 浙江
0所以计数排序和一级桶排序不是重复了吗……
2天前 来自 广东
0神马意思???
2天前 来自 上海
0计数排序是桶排的优化
昨天 来自 广东
1OK了
昨天 来自 上海
0
有帮助,赞一个