【数据结构与算法】十大经典排序算法深度解析:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序

             💓 博客主页:倔强的石头的CSDN主页 

           📝Gitee主页:倔强的石头的gitee主页

            ⏩ 文章专栏:《数据结构与算法》

                                  期待您的关注

 

1b7335aca73b41609b7f05d1d366f476.gif

 

 

目录

引言

一、排序算法概述

排序算法简介

排序算法的分类

性能指标

二、十大排序算法详解

🍃冒泡排序

🍃直接选择排序

🍃直接插入排序

🍃希尔排序

🍃快速排序

🍃堆排序

🍃归并排序

🍃计数排序

🍃桶排序

🍃基数排序

三、排序算法的性能比较与适用场景分析

性能比较

适用场景分析

四、总结

性能总结

稳定性与适用性

写在结尾


 

引言

在数据处理的广阔领域中,排序算法作为基石般的存在,扮演着至关重要的角色。无论是从日常生活中的简单列表排序,到复杂系统中海量数据的组织与管理,排序算法都是不可或缺的工具。它们不仅决定了数据处理的效率,还直接影响到用户体验和系统性能。

 

排序算法的核心任务是将一组数据元素(记录)按照某个关键字(或关键字序列)的递增或递减顺序重新排列,使得原本无序的数据变得有序。这一过程看似简单,实则蕴含着丰富的算法思想和优化策略。

 

随着计算机科学的发展,众多排序算法应运而生,每种算法都有其独特的适用场景和性能特点。为了帮助读者系统地掌握这些经典算法,本文精心挑选了十大经典排序算法进行深度解析。这十大算法不仅涵盖了比较排序和非比较排序两大类,还包含了从简单直观到高效复杂的多种实现方式,能够满足不同场景下的排序需求。

 

在本文中,我们将逐一介绍每种排序算法的基本原理、实现步骤、性能特点以及适用场景。通过具体的代码示例和性能比较,读者将能够深入理解每种算法的优势与局限,从而在实际应用中做出更加合理的选择。

 

一、排序算法概述

排序算法简介

排序算法是计算机科学中用于将一组数据元素(或记录)按照某个特定的顺序重新排列的算法。这些算法广泛应用于各种数据处理场景中,如数据库管理、数据分析、软件开发等。排序算法的核心目标是将无序的数据序列转变为有序的数据序列,以便进行进一步的查找、分析或呈现。

 35b69883b4384bbea2615000c0c633be.png

排序算法的分类

排序算法可以根据多种标准进行分类,但最常见的分类方式是基于它们的基本工作原理。主要分为两大类:比较排序和非比较排序。(更多的分类标准可以参照上图)

  1. 比较排序:这类排序算法通过比较数据元素之间的大小关系来确定它们的顺序。比较排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。这些算法的性能通常依赖于数据元素的初始排列和比较操作的效率。

  2. 非比较排序:与比较排序不同,非比较排序算法不直接比较数据元素之间的大小。它们通常依赖于数据元素的某些特定属性或额外的数据结构来实现排序。非比较排序算法包括计数排序、桶排序和基数排序等。这些算法在特定条件下(如数据范围有限或数据分布均匀)能够提供比比较排序更优的性能。

 

性能指标

评价排序算法优劣的关键指标主要包括以下几个方面:

  1. 时间复杂度:衡量算法执行所需时间的度量标准。通常用大O表示法(如O(n^2)、O(n log n))来描述算法在最坏情况、平均情况和最好情况下的时间复杂度。

  2. 空间复杂度:衡量算法执行过程中所需额外空间的度量标准。空间复杂度较低的算法更适合处理大数据集或内存受限的环境。

  3. 稳定性:稳定性是指排序算法在保持相等元素之间原有顺序的能力。稳定的排序算法在处理具有相等键值的元素时能够保持它们的相对顺序不变。

  4. 适应性:指算法对不同类型数据的适应能力。一些算法可能特别适用于整数排序,而另一些则可能更擅长处理浮点数或字符串等复杂数据类型。

通过综合考虑以上性能指标,我们可以选择最适合特定应用场景的排序算法。在本文的后续部分,我们将逐一深入探讨十大经典排序算法的原理、实现和性能特点,以帮助读者更好地理解并应用这些算法。

 

 

二、十大排序算法详解

🍃冒泡排序

 

 基本思想

通过重复地遍历待排序的序列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历序列的工作是重复地进行直到没有再需要交换,也就是说该序列已经排序完成。

详情请阅读专题文章 :

​【数据结构与算法】冒泡排序:简单易懂的排序算法解析-CSDN博客

算法过程

  • 比较相邻元素:重复地走访需要排序的元素列表,依次比较两个相邻的元素。
  • 交换元素:如果顺序(如从大到小或从小到大)错误,就交换这两个元素的位置。
  • 重复进行:重复以上步骤,直到没有相邻的元素需要交换,则元素列表排序完成。

 

21d653fc9e434573872733473a0c87bb.png

 C语言实现代码:

//冒泡排序
void BubbleSort1(DataType* a, int size)//升序排序
{for (int i = 0; i < size - 1; i++)//控制排序趟数{for (int j = 0; j < size - 1 - i; j++)//控制每次比较次数{if (a[j] > a[j + 1])//不满足升序就交换位置{DataType tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}
}
void BubbleSort2(DataType* a, int size)//降序排序
{for (int i = 0; i < size - 1; i++)//控制排序趟数{for (int j = 0; j < size - 1 - i; j++)//控制每次比较次数{if (a[j] < a[j + 1])//不满足降序就交换位置{DataType tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}
}

 

🍃直接选择排序

 基本思想

 选择排序(Selection Sort)是一种简单直观的排序算法。

它的工作原理是:

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

详情请阅读专题文章:

【数据结构与算法】选择排序:原理、实现、优化与分析-CSDN博客

算法过程:

  • 初始化:未排序区间为数组的全部元素,即整个数组;已排序区间为空。
  • 遍历:从未排序区间中遍历找到最小(或最大)的元素。
  • 交换:将找到的最小(或最大)的元素与未排序区间的第一个元素进行交换,该元素即为未排序区间的最小值(或最大值),因此交换后,它就到了已排序区间的末尾。
  • 缩小未排序区间:将未排序区间的第一个元素排除(因为它已经是排序好的了),继续在剩余的未排序区间中重复上述步骤,直到未排序区间为空。

下图以升序排序为例进行演示

7eaceeb231984cda89cc94f1b84efe88.png

 

C语言实现代码:

void swap(int* a, int* b)//交换函数
{int tmp = *a;*a = *b;*b = tmp;
}
void SelectSort1(int* a, int n)//选择排序降序
{for (int i = 0; i < n - 1; i++)//控制选择次数{int mini = i;for (int j = i + 1; j < n; j++)//控制查找范围{if (a[j] < a[mini])mini = j;}swap(&a[i], &a[mini]);}
}
void SelectSort2(int* a, int n)//选择排序降序
{for (int i = 0; i < n - 1; i++)//控制选择次数{int maxi = i;for (int j = i + 1; j < n; j++)//控制查找范围{if (a[j] > a[maxi])maxi = j;}swap(&a[i], &a[maxi]);}
}

 

🍃直接插入排序

基本思想

bd1c822db403477c97c1ff44a1f664ac.png

 插入排序的基本思想是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。

 

 

 详情请阅读专题文章:

【数据结构与算法】插入排序:原理、实现与分析-CSDN博客

 

 

 算法过程

b67604e1a5e849ed9b79519bca2a582a.gif

具体步骤是这样的:
(以排升序为例)

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,将该元素向后移动一位。
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5,直到所有元素都排序完成。

 

 

C语言实现代码

void InsertSort1(int* a, int n)//升序
{for (int i = 1; i <= n-1 ; i++)//控制要插入的元素个数{int key = a[i];int end = i - 1;while (end >= 0 && a[end] > key)//移动元素{a[end + 1] = a[end];end--;}a[end+1] = key;//满足大小关系后插入到指定位置}
}
void InsertSort2(int* a, int n)//降序
{for (int i = 1; i <= n - 1; i++)//控制要插入的元素个数{int key = a[i];int end = i - 1;while (end >= 0 && a[end] < key)//移动元素{a[end + 1] = a[end];end--;}a[end + 1] = key;//满足大小关系后插入到指定位置}
}

 

🍃希尔排序

 基本思想:

 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次标准的直接插入排序。

 

这里的“基本有序”是指待排序的数组元素值满足某个增量序列的“局部有序”,即对于某个变量gap,序列中所有距离为gap的元素之间是有序的。随着变量gap的逐渐减小,当gap减小到1时,整个序列恰好被“基本有序”,此时再对全体元素进行一次直接插入排序即可

详情请阅读专题文章:

【数据结构与算法】希尔排序:基于插入排序的高效排序算法-CSDN博客

40d13289c0024edda6a18cc2be99dc51.png

 

实现步骤:

 
1.外循环进行多轮预排序
选择一个变量序列:

这个序列是逐渐减小的,gap的值较大时,数据可以更快的前后变动,但不容易"基本有序";gap较小时数据前后变动较慢,但更接近"基本有序"。  通常可以选取gap = n/3, gap = gap/3, ...,直到gap= 1。

但是要注意,如果直接每次都/3,可能面临的情况就是最后一组gap的值跳过了1,比如n=8时,gap第一次等于2,第二次等于0,解决方法也很简单,gap每次不是/3,而是gap=gap/3+1,就可以让gap最后一次一定会减小到1

 

2.第二层循环,每一轮预排序中进行分组
按gap进行分组:根据当前的变量gap,将待排序的数组元素下标按gap分组,总共可以分成gap组。比如gap为3时,每一组元素的首元素分别是0,1,2

 

 

3.第三层循环,分组之后,控制组里数据执行插入排序
每一组的数据有n/gap个,下标为0,gap, 2gap, 3gap,...的元素分为一组;下标为1,gap+1,2gap+1,3gap+1……的元素分为一组……


这一层循环一个需要注意的细节就是预防数组的越界:每一组分组数据的最后一个数据一般不会是数组的最后一个数据。每次选取的要插入的数据下标是end+gap,那么这个下标不能超过n-gap。比如数组有10个元素,gap为3,第一组数据最后一个数据的下标是9,要保证这一组数据访问到下标9之后,不再向后访问,因为下一次访问end为9,要插入的数据,9+gap的位置已经没有数据了。

 


4.第四层循环,实现插入排序的过程
每个数据向前扫描和移动,找到合适的位置后插入,直接在插入排序代码的基础上稍加修改即可

 

 

5.递减变量gap并重复上述分组排序过程:

每完成一轮按变量gap的分组排序后,将变量gap减小,然后重复分组排序过程,直到变量gap为1,此时整个数组恰好被分成一组,进行最后一次直接插入排序。
 

 

C语言实现代码

void ShellSort1(int* a, int n)//希尔排序升序
{int gap = n;while (gap > 1)//多组预排序,最后一组gap==1为直接插入排序{gap = gap / 3 + 1;for (int i = 0; i <gap; i++)//控制分组的组数:gap组{for (int j = i; j < n - gap; j += gap)//控制每组的插入元素个数:n/gap个{int key = a[j+gap];int end = j;while (end >= 0 && a[end] > key)//比较和移动元素{a[end + gap] = a[end];end -= gap;}a[end + gap] = key;//满足大小关系后插入到指定位置}}}
}void ShellSort2(int* a, int n)//希尔排序降序
{int gap = n;while (gap > 1)//多组预排序,最后一组gap==1为直接插入排序{gap = gap / 3 + 1;for (int i = 0; i < gap; i++)//控制分组的组数:gap组{for (int j = i; j < n - gap; j += gap)//控制每组的插入元素个数:n/gap个{int key = a[j + gap];int end = j;while (end >= 0 && a[end] < key)//比较和移动元素{a[end + gap] = a[end];end -= gap;}a[end + gap] = key;//满足大小关系后插入到指定位置}}}
}

 

🍃快速排序

快速排序由于分为多个版本和优化,同时这也是比较重要和应用较多的排序算法,所以篇幅较长,就放在单独的文章,不在本文展开讲解了

 

【数据结构与算法】快速排序万字全攻略:hoare版本、挖坑法、前后指针法、优化版、非递归实现-CSDN博客

 

🍃堆排序

堆排序需要较多的前置知识,可参考同系列其他文章,每篇文章都有单独的讲解

 

可参考下列步骤阅读:

 

先了解二叉树的基本概念

【数据结构与算法】详解二叉树 上:理论篇——二叉树的基本概念与性质-CSDN博客

再了解二叉树的应用——堆

【数据结构与算法】探索数组在堆数据结构中的妙用:从原理到实现-CSDN博客

最后再了解堆的应用——堆排序

【数据结构与算法】堆排序算法原理与实现:基于堆实现的高效排序算法-CSDN博客

 

🍃归并排序

基本思想

归并排序(Merge Sort)是一种分而治之的排序算法。它将数组分成两半,对每半部分递归地应用归并排序,然后将结果合并成一个有序数组。归并排序的关键在于合并两个已排序的数组段

2b3c79d1f05c4b4ba750409c96548f3d.gif

更多细节及优化可参考文章:

【数据结构与算法】归并排序:从理论到实践的深度剖析-CSDN博客

算法过程:

注意:

因为归并排序在合并过程中需要一个与待排序数组大小相同的临时数组来存储合并的结果。

所以直接在进入函数之后一次申请一个同样大小的空间,免去多次动态申请空间和释放的消耗

主调函数只完成空间申请和释放,以及中间的调用子函数

将归并排序的核心代码放在子函数完成

 

 子函数的任务(归并的核心):

🍃1. 分解

  • 将当前区间一分为二,即找到中间位置mid = (left + right) / 2
  • 递归地对左半部分left...mid进行归并排序。
  • 递归地对右半部分mid+1...right进行归并排序。

🍃2. 解决

  • 在归并排序中,“解决”步骤实际上是在递归调用中隐式完成的,即通过递归调用自身来实现对左右子数组的排序。
  • 当递归调用达到基本情况(即子数组只有一个元素或为空时),由于一个元素的数组自然是有序的,因此不需要进行任何操作,递归开始返回。

🍃3. 合并(以升序为例):核心代码 

  • 使用两个变量i和j,分别指向左半部分和右半部分的起始位置。
  • 比较左半部分和右半部分当前指针所指的元素,将较小的元素先存入temp数组,并移动对应的变量。
  • 重复上述步骤,直到左半部分或右半部分的所有元素都被复制到temp数组中。
  • 将左半部分或右半部分中剩余的元素(一定是某部分的元素先复制完成)直接复制到temp数组的末尾。
  • 将temp数组中的元素复制回原数组,以完成合并过程。 

 

C语言实现代码

// 归并排序递归实现升序
void Merge1(int left,int right,int* a,int* tmp)//归并排序子函数
{if (left >= right)//区间只有一个元素或不存在时不需要归并return;int mid = (left + right) / 2;//取得下标中间值Merge1(left, mid, a, tmp);//递归左区间Merge1(mid + 1, right, a, tmp);//递归右区间int begin1 = left,end1 = mid;//左区间范围int begin2 = mid + 1,end2 = right;//右区间范围int begin = left;while (begin1 <= end1 && begin2 <= end2)//二路归并{if (a[begin1] < a[begin2])tmp[begin] = a[begin1++];elsetmp[begin] = a[begin2++];begin++;}//判断哪个区间元素没有遍历完,直接搬下来while (begin1 <= end1)tmp[begin++] = a[begin1++];while (begin2 <= end2)tmp[begin++] = a[begin2++];memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));//将归并和排序之后的数据拷贝至原数组
}
void MergeSort1(int* a, int n)//归并排序主调函数
{int* tmp = (int*)malloc(sizeof(int) * n);//申请临时数组if (tmp == NULL){perror("Merge malloc\n");return;}Merge1(0, n - 1, a, tmp);//调用归并函数free(tmp);//排序完成释放空间tmp = NULL;
}

 

🍃计数排序

 基本原理

计数排序(Counting Sort)是一种非比较型排序算法,它的基本原理是通过统计每个元素的出现次数,然后利用这些信息来重建排序后的数组。

 

核心思想在于:通过统计每个元素在数组中出现的次数,来确定该元素在排序后数组中的位置。这种方法在处理具有明显范围限制且分布相对均匀的整数数据时,尤为高效。

作为一种线性时间复杂度的排序,它要求输入的数据必须是有确定范围的整数。

更多详情可阅读文章:

【数据结构与算法】详解计数排序:小范围整数排序的最佳选择-CSDN博客 

 请看下图动图演示

027b5605bab4416094da68800bedf0d6.gif

 

实现步骤

1. 确定数据范围

首先,代码通过遍历待排序数组 a,找出其中的最大值 max 和最小值 min。这两个值用于确定计数数组 count 的大小,因为计数数组需要覆盖待排序数组中所有可能出现的值(在最小值和最大值之间)。

int min = INT_MAX;
int max = INT_MIN;
for (int i = 0; i < n; i++)//求得最大值和最小值
{if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];
}

 

2. 初始化计数数组

根据最大值和最小值计算出的范围(max - min + 1),代码使用 calloc 分配了一个足够大的整数数组 count,并将所有元素初始化为 0。这个数组用于统计待排序数组中每个值出现的次数。使用 calloc 而不是 malloc 加初始化是为了确保所有元素都初始化为 0,因为计数排序需要这些初始值来正确统计。

int size = max - min + 1;
int* count = (int*)calloc(size, sizeof(int));//根据数据范围申请空间
if (count == NULL)
{perror("calloc fail\n");return;
}

 

3. 统计元素频率

接下来,代码再次遍历待排序数组 a,这次是为了统计每个元素出现的次数。对于数组 a 中的每个元素 a[i],代码通过 count[a[i] - min]++ 将 a[i] 的出现次数记录在 count 数组的相应位置上。这里减去 min 是为了将 a 中的值映射到 count 数组的有效索引范围内。

for (int i = 0; i < n; i++)//遍历原数组,将数据出现的次数写入count数组对应的位置
{count[a[i] - min]++;//核心代码1
}

 

4. 排序

代码遍历 count 数组,并根据每个值出现的次数,将对应的值依次放回原数组 a 中。这里使用了一个双层循环,外层循环遍历 count 数组的每个索引(即待排序数组中的每个可能值),内层循环(通过 while 循环实现)则根据 count[j] 的值(即该值出现的次数)将 j + min(即原始值)放回原数组 a 中。每次放回一个值后,count[j] 递减,直到该值的所有出现都被放回原数组。

int i = 0;
for (int j = 0; j < size; j++)//遍历count数组,根据数据出现次数,将数据写入原数组对应的位置
{while (count[j]--)//每写入一次,次数--{a[i++] = j + min;//核心代码2}
}

 

5. 清理资源

最后,代码释放了 count 数组占用的内存,并将其指针设置为 NULL,以避免野指针问题。

free(count);
count = NULL;

 

C语言实现代码

void CountSort1(int* a, int n)//计数排序升序
{int min = INT_MAX;int max = INT_MIN;for (int i = 0; i < n; i++)//求得最大值和最小值{if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int size = max - min + 1;int* count = (int*)calloc(size, sizeof(int));//根据数据范围申请空间if (count == NULL){perror("calloc fail\n");return;}for (int i = 0; i < n; i++)//遍历原数组,将数据出现的次数写入count数组对应的位置{count[a[i] - min]++;//核心代码1}int i = 0;for (int j = 0; j < size; j++)//遍历count数组,根据数据出现次数,将数据写入原数组对应的位置{while (count[j]--)//每写入一次,次数--{a[i++] = j + min;//核心代码2}}free(count);count = NULL;
}

 

🍃桶排序

基本思想:

桶排序(Bucket Sort)是一种分布式排序算法,它将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。最后,将各个桶中的数据有序地合并起来。

桶排序最适合用在数据分布均匀的情况下,这样每个桶中的数据量大致相同,排序效率最高。当数据分布极不均匀时,桶排序的效率会大打折扣。

算法过程

  1. 确定桶的数量:根据待排序数据的范围来确定桶的数量。
  2. 分配元素到各个桶:遍历待排序数组,将每个元素分配到对应的桶中。
  3. 对每个桶进行排序:可以使用不同的排序算法对每个桶中的元素进行排序,也可以使用递归的桶排序。
  4. 合并桶中的数据:将各个桶中的数据有序地合并成一个有序数组。

C语言实现代码

#define MAX_NUM 100 // 假设数据最大为100  
#define BUCKET_SIZE (MAX_NUM / 5) // 假设桶的数量是数据范围的1/5  void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* 将arr[i]插入到已排序序列arr[0..i-1]的适当位置 */  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  j = j - 1;  }  arr[j + 1] = key;  }  
}  void bucketSort(int arr[], int n) {  int i, j;  int bucket[BUCKET_SIZE][n]; // 假设最坏情况下每个桶都有n个元素  int count[BUCKET_SIZE] = {0}; // 每个桶中的元素数量  // 1. 分配元素到各个桶  for (i = 0; i < n; i++) {  int bi = arr[i] / (MAX_NUM / BUCKET_SIZE); // 桶的索引  bucket[bi][count[bi]++] = arr[i];  }  // 2. 对每个桶进行排序  for (i = 0; i < BUCKET_SIZE; i++) {  insertionSort(bucket[i], count[i]);  }  // 3. 合并桶中的数据  int index = 0;  for (i = 0; i < BUCKET_SIZE; i++) {  for (j = 0; j < count[i]; j++) {  arr[index++] = bucket[i][j];  }  }  
}  
 


🍃基数排序

基本思想:

基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体来说,就是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如日期、时间等)的排序,因此基数排序也不是仅适用于整数。

基数排序有两种方法:

  1. LSD(Least significant digital):从最低位开始进行排序,然后向最高位进行。
  2. MSD(Most significant digital):从最高位开始进行排序,然后向最低位进行。通常使用递归方法实现。

这里主要介绍LSD方法,因为它更直观且易于实现。

 

算法过程

  1. 找出待排序数组中的最大数,以确定最大位数。
  2. 从最低位开始,依次进行一次排序
    • 分配:根据当前位数,将元素分配到不同的桶中。
    • 收集:将桶中的元素按顺序收集起来,形成新的数组。
  3. 重复上述过程,直到最高位。

C语言实现代码

以下是一个基于LSD的基数排序的C语言实现,假设我们排序的是非负整数,并且每个数字的最大位数是已知的(或者可以动态计算)。为了简化,这里假设所有数字都是单个字符(即0-9的数字),并存储在字符数组中。

#define MAXD 10 // 假设最大位数是10(实际情况可能需要根据数据范围确定)  
#define RADIX 10 // 基数为10,因为处理的是十进制数  // 用于基数排序的桶  
int count[RADIX];  
char output[MAXD][1000]; // 假设最多有1000个数字  // 获取字符串num的最低位(这里简化为取最后一个字符代表的数字)  
int getDigit(char num[], int d) {  return num[strlen(num) - 1 - d] - '0';  
}  // 基数排序函数  
void radixSort(char arr[][10], int n) {  // 找到最大数的位数  int m = 0;  for (int i = 0; i < n; i++)  if (strlen(arr[i]) > m)  m = strlen(arr[i]);  // 从最低位到最高位进行排序  for (int d = 0; d < m; d++) {  // 初始化桶  memset(count, 0, sizeof(count));  // 将元素分配到桶中  for (int i = 0; i < n; i++)  count[getDigit(arr[i], d)]++;  // 更改count[i],使其包含实际位置信息  for (int r = 1; r < RADIX; r++)  count[r] += count[r - 1];  // 将元素收集到输出数组中  for (int i = n - 1; i >= 0; i--) {  output[count[getDigit(arr[i], d)] - 1] = arr[i];  count[getDigit(arr[i], d)]--;  }  // 将输出数组的内容复制回原数组  for (int i = 0; i < n; i++)  strcpy(arr[i], output[i]);  }  
}  

三、排序算法的性能比较与适用场景分析

 

性能比较

 

排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性
冒泡排序O(n^2)O(n^2)O(n)O(1)稳定
选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定
插入排序O(n^2)O(n^2)O(n)O(1)稳定
希尔排序O(nlogn)O(n^s) (s为常数)O(n)O(1)不稳定
快速排序O(nlogn)O(n^2)O(nlogn)O(logn)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定
计数排序O(n+k)O(n+k)O(n+k)O(k)稳定
桶排序O(n+k)O(n^2)O(n)O(n+k)稳定(平均)/不稳定(最坏)
基数排序O(d*(n+k))O(d*(n+k))O(d*(n+k))O(n+k)稳定

 

适用场景分析

  1. 冒泡排序
    • 适用场景:适用于数据量较小的情况,如简单的数据排序练习或小规模数据的排序。
    • 缺点:在数据量较大时效率极低。
  2. 选择排序
    • 适用场景:与冒泡排序类似,适用于数据量较小的情况。
    • 缺点:由于需要多次遍历未排序部分以找到最小(或最大)元素,因此效率较低。
  3. 插入排序
    • 适用场景:适用于部分有序或数据量较小的数据排序。对于几乎已经排序的数据,插入排序的效率很高。
    • 优点:在数据规模较小时,效率较高;对于部分有序的数据集,效率也较高。
  4. 希尔排序
    • 适用场景:适用于中等规模的数据排序,特别是在数据基本有序时,效率较高。
    • 优点:通过引入增量序列,减少了数据比较和移动的次数,提高了排序效率。
  5. 快速排序
    • 适用场景:适用于大规模数据的排序,是实际应用中最常用的排序算法之一。
    • 优点:平均情况下效率高,且可以通过随机选择基准元素来避免最坏情况的发生。
  6. 归并排序
    • 适用场景:适用于大规模数据的排序,特别是当需要稳定排序时。
    • 优点:稳定排序,且时间复杂度为O(nlogn),效率较高。但空间复杂度较高,不适合内存受限的环境。
  7. 堆排序
    • 适用场景:适用于需要快速选择最大(或最小)元素的场景,如堆数据结构的应用。
    • 优点:时间复杂度为O(nlogn),效率较高;且不需要额外的存储空间(除了递归所需的栈空间)。
  8. 计数排序
    • 适用场景:适用于整数数据范围较小的情况,如考试成绩、年龄等数据的排序。
    • 优点:在数据范围较小时,效率极高;且稳定排序。
  9. 桶排序
    • 适用场景:适用于数据分布均匀的情况,如正态分布的数据。
    • 优点:在数据分布均匀时,效率较高;且稳定排序(平均情况下)。
  10. 基数排序
    • 适用场景:数据范围大但位数较少,关键字可以分割成独立的数字,数据分布较均匀
    • 优点:在数据分布均匀时,效率较高;且稳定排序(平均情况下)。

 

四、总结

在探讨完十大经典排序算法后,我们可以从多个维度对这些算法进行总结,以便更好地理解它们的特点、适用场景以及性能差异。

性能总结

  1. 时间复杂度
    • 最优情况:冒泡排序、插入排序、选择排序在最优情况下时间复杂度为O(n),但这通常发生在数据已经接近有序的情况下。快速排序、归并排序、堆排序在最优情况下可以达到O(n log n)。桶排序和计数排序在特定条件下(如数据分布均匀)可以达到O(n)。
    • 平均情况:大多数比较排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序)的平均时间复杂度为O(n^2)或O(n log n)。非比较排序(如桶排序、计数排序、基数排序)在平均情况下也能达到O(n)。
    • 最差情况:冒泡排序、插入排序、选择排序的最差时间复杂度为O(n2)。快速排序在最差情况下(如每次分区都选择到最大或最小元素)也会退化到O(n2),但通过随机化选择基准元素可以显著降低这种情况的发生概率。归并排序和堆排序的最差时间复杂度始终为O(n log n)。
  2. 空间复杂度
    • 冒泡排序、插入排序、选择排序等原地排序算法的空间复杂度为O(1),即它们只使用常量额外空间。
    • 归并排序、快速排序等在某些实现中可能需要额外的空间来存储递归调用栈或临时数组,其空间复杂度为O(log n)或O(n)。
    • 桶排序、计数排序、基数排序等非比较排序算法通常需要额外的空间来存储桶、计数数组或基数队列,其空间复杂度取决于数据的分布和范围。

稳定性与适用性

  • 稳定性:排序算法的稳定性指的是在排序过程中,如果两个元素相等,它们的相对位置在排序前后保持不变。归并排序、插入排序、冒泡排序是稳定的排序算法,而快速排序、选择排序、堆排序等则是不稳定的。
  • 适用性
    • 对于小数据集或几乎有序的数据集,插入排序和冒泡排序通常表现良好。
    • 当数据量较大时,快速排序、归并排序和堆排序等更高效的算法更为适用。
    • 如果数据分布具有特定模式(如大量重复元素或有限取值范围),则可以考虑使用计数排序、桶排序或基数排序等非比较排序算法。

写在结尾

十大排序算法各有其特点和适用场景。在选择排序算法时,需要根据数据的具体特点(如规模、分布、有序程度等)以及算法的性能指标(如时间复杂度、空间复杂度、稳定性等)进行综合考虑。在实际应用中,可能还需要结合具体问题的需求和约束条件来选择合适的排序算法。通过深入了解这些算法的原理和特性,我们可以更加灵活地应对各种排序问题。

 

本文完 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/392403.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity Rigidbody 踩坑记录

1&#xff1a;两个带有刚体的物体碰撞会一直不停的弹 把被动受力的刚提的 Freeze Position 的勾选 去掉&#xff08;碰到过一次&#xff0c;有一种受力无法释放又返回给目标的 所以一直弹跳的感觉&#xff09; 2&#xff1a;子物体 和父物体 都有刚体的情况下 子物体 Freeze R…

zdpy+vue3+onlyoffice文档系统实战上课笔记 20240805

上次 上次计划 1、最近文档表格完善 2、实现登录功能 3、新建文件&#xff0c;复制文件&#xff0c;删除文件 4、其他 目前任务&#xff1a;最近文档表格完善 1、在名称前面&#xff0c;渲染这个文档的图标 2、大小的基本的单位是kb&#xff0c;超过1024kb则换成mb&#xff0…

Java | Leetcode Java题解之第318题最大单词长度乘积

题目&#xff1a; 题解&#xff1a; class Solution {public int maxProduct(String[] words) {Map<Integer, Integer> map new HashMap<Integer, Integer>();int length words.length;for (int i 0; i < length; i) {int mask 0;String word words[i];in…

Mysql中事务的读一致性问题,以及如何用MVCC解决

事务四大特性的实现&#xff1a; 原子性事务具有回滚的能力&#xff0c;InnoDB引擎使用undo log日志表来进行回滚操作。 持久性InnoDB引擎使用redo log日志表来保证数据的持久性。 事务的隔离性产生的问题&#xff1a; 脏读&#xff1a;一个事务读取到了另一个事务未提交的数…

Linux系统驱动(五)

文章目录 一、实现机制二、字符设备驱动分布实现流程三、添加自己的系统调用函数1. 找到系统调用文件2. 找到 一、实现机制 应用层 vfs层 驱动层 字符设备按照字节流顺序访问&#xff0c;但是实际它提供了无序访问的功能 vi -t sys_open 内核中通过inode号可以唯一的找到一…

请转告HPC计算AI计算单位,选对存储事半功倍

U.2 NVMe全闪混合统一存储GS 5000U是Infortrend产品中一款高性能机型。得益于搭载强劲的第五代IntelXeon处理器&#xff0c;以及支持PCIe 5.0、NVMe-oF、100GbE等多种特点&#xff0c;GS 5000U单台块级性能可达50 GB/s的读、20 GB/s的写&#xff0c;以及1300K的IOPS&#xff1b…

Xshell安装图文

1.下载 通过百度网盘分享的文件&#xff1a;Xshell安装图文 链接&#xff1a;https://pan.baidu.com/s/1k4ShbhUVQmdxpM9H8UYOSQ 提取码&#xff1a;kdxz --来自百度网盘超级会员V3的分享 2.安装 3.连接与使用 见下载

论文辅导 | 基于二次分解和BO-BiLSTM组合模型采煤工作面瓦斯涌出量预测方法研究

辅导文章 模型描述 结合变分模态分解&#xff08;VMD&#xff09;、自适应噪声完备经验模态分解&#xff08;CEEMDAN&#xff09;、贝叶斯优化算法&#xff08;BO&#xff09;和双向长短期记忆神经网络&#xff08;BiLSTM&#xff09;这4种时间序列处理方法&#xff0c;建立了…

AllReduce通信库;Reduce+LayerNorm+Broadcast 算子;LayerNorm(层归一化)和Broadcast(广播)操作;

目录 AllReduce通信库 一、定义与作用 二、常见AllReduce通信库 三、AllReduce通信算法 四、总结 Reduce+LayerNorm+Broadcast 算子 1. Reduce 算子 2. LayerNorm 算子 3. Broadcast 算子 组合作用 LayerNorm(层归一化)和Broadcast(广播)操作 提出的创新方案解析 优点与潜在…

项目实战_图书管理系统(简易版)

你能学到什么 一个简单的项目——图书管理系统&#xff08;浏览器&#xff1a;谷歌&#xff09;基础版我们只做两个功能&#xff08;因为其它的功能涉及的会比较多&#xff0c;索性就放在升级版里了&#xff0c;基础版先入个门&#xff09; 登录: ⽤⼾输⼊账号,密码完成登录功…

登录相关功能的优化【JWT令牌+拦截器+跨域】

登录相关功能的优化 登录后显示当前登录用户el-dropdown: Element - The worlds most popular Vue UI framework <el-dropdown style"float: right; height: 60px; line-height: 60px"><span class"el-dropdown-link" style"color: white;…

音视频开发 sdl库

介绍 SDL (Simple DirectMedia Layer) 是一个跨平台的开源多媒体库,它提供了底层访问多种硬件的接口,如音频、视频、输入设备等。它主要用于游戏开发,但也可用于其他类型的多媒体应用程序。下面是 SDL 的一些主要特点: 跨平台性: SDL 支持多种操作系统,包括 Windows、macOS、L…

HashMap中 put()方法的流程、扩容的思路(源码分析~)

文章目录 put() 方法的流程扩容流程为什么它会按照2的幂次方进行扩容呢&#xff1f; put() 方法的流程 下面我们通过分析源码来总结一下 put() 方法的流程 扩容流程 根据上图的分析&#xff0c;就可以总结出 HashMap 的扩容流程&#xff1a; 在插入元素时&#xff0c;会先…

C# 设计模式之原型模式

总目录 前言 在软件系统中&#xff0c;当创建一个类的实例的过程很昂贵或很复杂&#xff0c;并且我们需要创建多个这样类的实例时&#xff0c;如果我们用new操作符去创建这样的类实例&#xff0c;这未免会增加创建类的复杂度和耗费更多的内存空间&#xff0c;因为这样在内存中…

复现一下最近学习的漏洞(sqlab 1-10)

第一个问题&#xff1a;为什么不能用#来闭合单引号呢&#xff1f; 在进行URL地址栏传参的时候&#xff0c;是有一套编码规范的。他不会编码英文、数字和某些符号。但是#它会进行编码。也就是%23。&#xff08;先转ascii码&#xff0c;然后再转十六进制&#xff0c;之后加上%就是…

软甲测试定义和分类

软件测试定义 使用人工和自动手段来运行或测试某个系统的过程&#xff0c;其目的在于检验他是否满足规定的需求或弄清预期结果与实际结果之间的差别 软件测试目的 为了发现程序存在的代码或业务逻辑错误 – 第一优先级发现错误为了检验产品是否符合用户需求 – 跟用户要求实…

函数实例讲解(四)

文章目录 提取不重复值&#xff08;INDEX、MATCH、COUNTIF&#xff09;1、INDEX2、MATCH3、COUNTIF 提取不重复的值的经典套路&#xff08;LARGE、SMALL、ROW&#xff09;1、ROW2、LARGE3、SMALL&#xff09; 制作Excel动态查询表四舍五入函数(ROUND、ROUNDUP、ROUNDDOWN&#…

20240806 每日AI必读资讯

英伟达最强AI芯片曝重大设计缺陷&#xff0c;中国特供版意外曝光&#xff01; - 由于Blackwell GPU的设计缺陷&#xff0c;英伟达发货时间不得不推迟3个月 - GB200包含了2个Blackwell GPU和1个Grace CPU。问题出在连接2个Blackwell GPU的关键电路 - 意味着对于Meta、谷歌、微…

AI在医学领域:医学成像中针对深度神经网络(DNN)的对抗性攻击及其防御策略

关键词&#xff1a;对抗性攻击、医学图像、深度神经网络、模型安全、鲁棒性 机器学习&#xff08;ML&#xff09;是医学领域快速发展的一个分支&#xff0c;它利用计算机科学和统计学的方法来解决医学问题。众所周知&#xff0c;攻击者可能通过故意为机器学习分类器创建输入来…

VoNR网络架构与网元 IMS终端号码结构(VoLTE和VoNR适用)

目录 1. VoNR网络架构与网元 1.1 VoNR架构 vs VoLTE架构 1.2 回顾语音网络的演进与“分离” 1.3 TS23.228给出的5G的VoNR国际漫游 Home Routed 方案架构图 1.4 VoNR 网络架构图&#xff08;2022版&#xff09; 1.5 IMS 网元分类&#xff08;VoNR VoLTE 适用&#xff09…