大家好，今天来为大家解答八大排序时间复杂度这个问题的一些问题点，包括所有排序的时间复杂度也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~
本文目录
一、数据结构-八大排序算法的时间复杂度 稳定性
更好：待排序已经有序，从前往后走都不用往里面插入。时间复杂度为o(n)
最坏：待排序列是逆序，每一次都要移位插入。时间复杂度o(n^2)
更好：缩小增量的插入排序，待排序已经有序。时间复杂度o(n）
一般：平均时间复杂度o(n 1.3)，最差也是时间复杂度o(n 1.3)
更好：待排序已经有序。时间复杂度o(n）
最坏：待排序是逆序。时间复杂度o(n^2）
更好：待排序无序。时间复杂度o(nlogn)
最坏:待排序已经有序，基准定义在开始。时间复杂度为o(n^2)
无论好坏:o(d(n+r))，r为基数，d为位数.
二、面试必会八大排序算法(Python)
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
算法适用于少量数据的排序，时间复杂度为O(n^2)。
①从之一个元素开始，该元素可以认为已经被排序
②取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
循环遍历列表，每次循环找出循环更大的元素排在后面；
需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。
①比较相邻的元素。如果之一个比第二个大，就交换他们两个。
②对每一对相邻元素作同样的工作，从开始之一对到结尾的最后一对。在这一点，最后的元素应该会是更大的数。
③针对所有的元素重复以上的步骤，除了最后一个。
④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。
快速排序的基本思想是：挖坑填数+分治法。
首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
①从数列中挑出一个元素，称为“基准”（pivot）；
②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；
③对所有两个小数列重复第二步，直至各区间只有一个数。
希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。
希尔排序是基于插入排序的以下两点性质而提出改进 *** 的：
·插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
·但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。
选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。
选择排序的基本思想：比较+交换。
之一趟，在待排序记录r1~ r[n]中选出最小的记录，将它与r1交换；
第二趟，在待排序记录r2~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第 i趟，在待排序记录ri~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
利用数组的特点快速指定索引的元素。
堆分为大根堆和小根堆，是完全二叉树。
大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]]>=A[i]。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，更大的值一定在堆顶。
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
自上而下递归法（假如序列共有n个元素）
①将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
②将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③重复步骤②，直到所有元素排序完毕。
①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
②设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④重复步骤③直到某一指针达到序列尾；
⑤将另一序列剩下的所有元素直接复制到合并序列尾。
基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。
基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中 r为采取的基数，而m为堆数。
在某些时候，基数排序法的效率高于其他的稳定性排序法。
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从更低位开始，依次进行一次排序。这样从更低位排序一直到更高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
MSD（Most significant digital）从最左侧高位开始进行排序。先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后.再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD（Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
各种排序的稳定性、时间复杂度、空间复杂度的总结：
平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
O(n1+§))排序，§是介于0和1之间的常数：希尔排序；
线性阶O(n)排序：基数排序，此外还有桶、箱排序。
三、八大经典排序算法原理及实现
该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。
冒泡排序算法应该是大家之一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：
按照计算时间复杂度的规则，去掉常数、去掉更高项系数，其复杂度为O(N^2)
空间复杂度就是在交换元素时那个临时变量所占的内存
给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：
我们发现之一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？
冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法
插入排序是对冒泡排序的一种改进
插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
空间复杂度就是在交换元素时那个临时变量所占的内存
由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化
其原理是从未排序的元素中选出最小值(更大值)放在已排序元素的后面
空间复杂度就是在交换元素时那个临时变量所占的内存
选择排序是不稳定的，比如 3 6 3 2 4，之一次外层循环中就会交换之一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化
希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法
其原理是将序列分割成若干子序列（由相隔某个增量的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：
希尔排序的效率取决于增量值gap的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然更好肯定是O(N)，最坏是O(N 2)
空间复杂度就是在交换元素时那个临时变量所占的内存
希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的
理解堆排序，就必须得先知道什么是堆？
当父节点的值总是大于子结点时为更大堆；反之为最小堆，下图就为一个二叉堆
一般用数组来表示堆，下标为 i的结点的父结点下标为(i-1)/2；其左右子结点分别为(2 i+ 1)、(2 i+ 2)
怎么将给定的数组序列按照堆的性质，调整为堆？
很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4]= 50的结点开始做堆调整，即从（n/2- 1）位置处向上开始做堆调整：
由于每次重新恢复堆的时间复杂度为O(logN)，共N- 1次重新恢复堆操作，再加上前面建立堆时N/ 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N* logN)。
空间复杂度就是在交换元素时那个临时变量所占的内存
由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5,堆化数组后将堆顶元素5与堆尾元素5交换，使得之一个5和第三个5的相对位置发生变化
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面挖坑填数 *** 后，能快速写出、快速排序。
其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式挖坑填数分治法
对于序列： 72 6 57 88 60 42 83 73 48 85
数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：
数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了
空间复杂度，主要是递归造成的栈空间的使用:
快速排序的优化主要在于基准数的选取
快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定
前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较+后移赋值。时间复杂度如下：
二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的
关于八大排序时间复杂度和所有排序的时间复杂度的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
