几种常见排序算法的分析
泡排序是最简单的排序算法,在所有算法中平均效率是最低的,但便于理解,适用于记录个数n较小的排序中;选择排序适用于记录个数n较小而记录本身信息量较大的排序中;插入排序适用于记录个数n较小而原数组基本有序的排序中;希尔排序适用于记录个数较大而记录本身信息量较小的排序中;快速排序是从平均时间性能而言最佳的算法,适用于记录个数n较大而记录无序的排序中;归并排序适用于记录个数n较大而记录信息量也较大的排序中;基数排序适合于n值很大而关键字较小的序列。
排序算法概述
排序定义: 所谓计算机中的排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。而排序算法(Sortingalgorithm)则是一种能将一串数据依照特定的方式进行排列的一种算法。
排序方式: 利用所需重排记录的排序码(SortKey)的值的大小,按照升序或降序将原纪录的顺序重新安排。
插入排序算法介绍
插入排序是一种简单的插入排序法,其基本思想是:把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的纪录插入完为止,得到一个新的有序序列。插入排序的算法思路:
(1) 设置监视哨r[0],将待插入纪录的值赋值给r[0];
(2) 设置开始查找的位置j;
(3) 在数组中进行搜索,搜索中将第j个纪录后移,直至r[0].key≥r[j].key为止;
(4) 将r[0]插入r[j+1]的位置上。
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
希尔排序算法介绍
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2
< d1重复上述的分组和排序,直至所取的增量d_t=1(d_t < d_(t-1) < ⋯ < d_2 <
d_1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比[2]
较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。
冒泡排序算法介绍
假如一个数组有n个数,那么我们可以从第一个数开始从头到尾两两比较,当前一个数比后一个数大时,则交换他们的位置,直到最大的一个数被排在了数组的后尾。然后最后一个数固定,不再需要比较,只需要按照刚刚的方法重复比较前面的n-1个数,知道排出顺序。
快速排序算法介绍
快速排序(Quicksort)是对冒泡排序的一种改进。
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
算法是:
1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;
2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与key交换;
4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与key交换;
5)重复第3、4、5步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)
选择排序算法介绍
选择排序的基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
归并排序算法介绍
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
基数排序算法介绍
基数排序与本系列前面讲解的七种排序方法都不同,它不需要比较关键字的大小。
它是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
不妨通过一个具体的实例来展示一下,基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30,
0, 2, 11, 100}。我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是0,将这个数存入编号为0的桶中。(如图1)
图1 基数排序
分类后,我们在从各个桶中,将这些数按照从编号0到编号9的顺序依次将所有数取出来。
这时,得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14