您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

常用的排序算法

时间:2023-04-27 13:35:35  来源:  作者:编码小哥


排序算法是计算机科学领域中非常重要的基础算法之一,主要应用于数据处理中,将未排序的数据按照一定规则排列,以便后续的计算和数据分析。目前常用的排序算法有多种,包括冒泡排序、插入排序、选择排序、归并排序、快速排序等。本文将逐一介绍每一种排序算法的具体实现方法、优缺点以及时间复杂度等。

一、冒泡排序

冒泡排序是一种简单易懂的排序算法,它的基本思路是将待排序的元素比较相邻的两个数,如果前面的数大于后面的数,则交换它们的位置。这样一轮比较下来,最大的数就会被移动到数列的末尾。接下来,再对剩下的数列进行相同的操作,直到排序完成。

冒泡排序的具体实现如下:

void bubble_sort(int arr[], int len)

{

int i, j, temp;

for(i = 0; i < len - 1; i++)

{

for(j = len - 1; j > i; j--)

{

if(arr[j] < arr[j - 1])

{

temp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = temp;

}

}

}

}

冒泡排序的优点是实现简单易懂,缺点是时间复杂度较高,为O(n^2),在数据量较大的情况下比较耗时,不适合处理大规模数据。

二、插入排序

插入排序是一种直观、简单的排序算法,它的基本思路是将待排序的元素逐个插入到已排好序的序列中,以保证插入后的序列仍然有序。插入排序分为直接插入排序和希尔排序两种。

1. 直接插入排序

直接插入排序的具体实现如下:

void insert_sort(int arr[], int len)

{

int i, j, temp;

for(i = 1; i < len; i++)

{

temp = arr[i];

j = i - 1;

while(j >= 0 && arr[j] > temp)

{

arr[j + 1] = arr[j];

j--;

}

arr[j + 1] = temp;

}

}

直接插入排序的优点是实现简单,对于数据量较小的情况下性能较好。缺点是时间复杂度为O(n^2),同样不适合处理大规模数据。

2. 希尔排序

希尔排序是插入排序的一种改进算法,它的基本思路是通过将序列分成若干个子序列来进行插入排序,使得整个序列基本有序,然后再对整个序列进行插入排序。希尔排序具有时间复杂度为O(n^(3/2))的优点,在实际应用中性能较好。

希尔排序的具体实现如下:

void shell_sort(int arr[], int len)

{

int i, j, gap, temp;

for(gap = len / 2; gap > 0; gap /= 2)

{

for(i = gap; i < len; i++)

{

temp = arr[i];

j = i - gap;

while(j >= 0 && arr[j] > temp)

{

arr[j + gap] = arr[j];

j -= gap;

}

arr[j + gap] = temp;

}

}

}

三、选择排序

选择排序是一种简单直观的排序算法,它的基本思路是将待排序的序列分成已排序和未排序两部分,从未排序的部分中找到最小的元素,将其放到已排序部分的末尾。接着再从未排序部分中继续寻找最小的元素,重复上述过程,直到最终排序完成。

选择排序的具体实现如下:

void select_sort(int arr[], int len)

{

int i, j, k, temp;

for(i = 0; i < len - 1; i++)

{

k = i;

for(j = i + 1; j < len; j++)

{

if(arr[j] < arr[k])

{

k = j;

}

}

if(k != i)

{

temp = arr[i];

arr[i] = arr[k];

arr[k] = temp;

}

}

}

选择排序的优点是实现简单直观,缺点是时间复杂度较高,为O(n^2),同样不适合处理大规模数据。

四、归并排序

归并排序是一种非常高效的排序算法,它的基本思路是分治法,将待排序的序列分成若干个单独的子序列,分别对每个子序列进行排序,最后将排序好的子序列合并,形成一个排好序的序列。

归并排序的具体实现如下:

void merge_sort(int arr[], int len)

{

int *a = arr;

int *b = (int*)malloc(len*sizeof(int));

int seg, start;

for(seg = 1; seg < len; seg += seg)

{

for(start = 0; start < len; start += seg+seg)

{

int low = start, mid = min(start+seg, len), high = min(start+seg+seg, len);

int k = low;

int start1 = low, end1 = mid;

int start2 = mid, end2 = high;

while(start1 < end1 && start2 < end2)

{

b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];

}

while(start1 < end1) {

b[k++] = a[start1++];

}

while(start2 < end2)

{

b[k++] = a[start2++];

}

}

int *temp = a;

a = b;

b = temp;

}

if(a != arr)

{

int i;

for(i = 0; i < len; i++)

{

b[i] = a[i];

}

b = a;

}

free(b);

}

归并排序的优点是具有时间复杂度为O(nlogn)的优点,适合处理大规模的数据。缺点是空间开销较大,需要额外的内存空间进行归并操作。

五、快速排序

快速排序是一种高效的排序算法,它的基本思路是分治法,选取一个中间的基准值,将序列分成两个子序列,一边小于基准值,一边大于基准值,再对这两个子序列进行递归操作,直到排序完成。

快速排序的具体实现如下:

void quick_sort(int arr[], int left, int right)

{

int i, j, pivot, temp;

if(left < right)

{

i = left;

j = right;

pivot = arr[left];

while(i < j)

{

while(i < j && arr[j] >= pivot)

{

j--;

}

if(i < j)

{

arr[i++] = arr[j];

}

while(i < j && arr[i] < pivot)

{

i++;

}

if(i < j)

{

arr[j--] = arr[i];

}

}

arr[i] = pivot;

quick_sort(arr, left, i - 1);

quick_sort(arr, i + 1, right);

}

}

快速排序的优点是具有时间复杂度为O(nlogn)的优点,适合处理大规模的数据。缺点是对于特殊情况下容易出现性能退化,需要进行优化。

小结

各种排序算法各有优缺点,在实际应用中需要根据具体场景选择适合的排序算法,以求得最佳的性能和效率。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
诱导付费、自动扣费……微短剧被质疑借助算法精准“围猎”老年人
诱导付费、自动扣费、重复收费&hellip;&hellip;聚焦身边的消费烦心事⑦丨一些微短剧被质疑借助算法精准“围猎”老年人中工网北京3月31日电(工人日报&mdash;中工网记者刘兵)...【详细内容】
2024-04-01  Search: 算法  点击:(6)  评论:(0)  加入收藏
分析网站SEO快速排名算法对网站具体的影响效果
亲爱的朋友们,今天我想和大家分享一个我们都关心的话题&mdash;&mdash;网站SEO快速排名算法对网站我们身处一个信息爆炸的时代,如何在海量的信息中脱颖而出,成为了一个我们不得...【详细内容】
2024-03-28  Search: 算法  点击:(12)  评论:(0)  加入收藏
当prompt策略遇上分治算法,南加大、微软让大模型炼成「火眼金睛」
近年来,大语言模型(LLMs)由于其通用的问题处理能力而引起了大量的关注。现有研究表明,适当的提示设计(prompt enginerring),例如思维链(Chain-of-Thoughts),可以解锁 LLM 在不同领域的...【详细内容】
2024-03-12  Search: 算法  点击:(12)  评论:(0)  加入收藏
谷歌宣布更新搜索算法:打击AI生成内容,提高搜索结果质量
IT之家 3 月 6 日消息,谷歌于当地时间 5 日发文宣布,针对用户对搜索结果质量下降的反馈,将对算法进行调整,旨在打击 AI 生成的内容以及内容农场等垃圾信息,使用户能够看到更多“...【详细内容】
2024-03-06  Search: 算法  点击:(38)  评论:(0)  加入收藏
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  Search: 算法  点击:(13)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03  Search: 算法  点击:(50)  评论:(0)  加入收藏
简易百科之什么是搜索引擎的PageRank算法?
简易百科之什么是搜索引擎的PageRank算法?在互联网时代,搜索引擎是我们获取信息的重要工具。而PageRank算法则是搜索引擎的核心技术之一,它决定了网页在搜索结果中的排名。那么...【详细内容】
2024-01-24  Search: 算法  点击:(50)  评论:(0)  加入收藏
PageRank算法揭秘:搜索引擎背后的魔法师的工作原理
PageRank(PR)算法是由谷歌创始人之一的拉里&middot;佩奇LarryPage命名的一种衡量网站页面重要性的方法。根据谷歌的说法,PageRank通过计算页面链接的数量和质量来粗略估计分...【详细内容】
2024-01-23  Search: 算法  点击:(44)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  Search: 算法  点击:(44)  评论:(0)  加入收藏
百度最新的搜索引擎算法是什么样的?
百度搜索引擎算法是百度用来决定网页排名的算法。它是百度搜索技术的核心,也是百度作为全球最大的中文搜索引擎的基石。随着互联网的发展和用户需求的不断变化,百度搜索引擎算...【详细内容】
2024-01-10  Search: 算法  点击:(86)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(13)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(50)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(44)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(96)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(63)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条