有序序列排序用时最短的算法

㈠ 以下哪种排序算法对进行的排序最快

1.选择排序：不稳定，时间复杂度
O(n^2)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
2.插入排序：稳定，时间复杂度
O(n^2)
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]
又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤
L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]
≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。
3.冒泡排序：稳定，时间复杂度
O(n^2)
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
4.堆排序：不稳定，时间复杂度
O(nlog
n)
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
5.归并排序：稳定，时间复杂度
O(nlog
n)
设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。
6.快速排序：不稳定，时间复杂度
最理想
O(nlogn)
最差时间O(n^2)
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
几种排序的时间复杂度，可以参考一下

㈡ 想在含有n个元素的序列中得到最小的前k个元素，最好采用什么排序算法

想在含有n个元素的序列中得到最小的前k个元素，最好采用什么排序算法是堆排序。

堆排序利用堆数据结构而设计的一种排序算法，堆排序是一种选择排序，平均时间复杂度均为O(nlogn)，堆排序具有不稳定性。

堆排序作为具有以下性质的完全二叉树：大顶堆每个结点的值都大于或等于其左右孩子结点的值，或者小顶堆每个结点的值都小于或等于其左右孩子结点的值。

(2)有序序列排序用时最短的算法扩展阅读：

堆排序的基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

㈢ 如果输入元素为排好的顺序什么算法最慢结束的排序算法

如果元素完全有序，快速排序的性能是O(n^2)，应该就是快排最慢。

㈣ 面试必会八大排序算法（Python）

一、插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法适用于少量数据的排序，时间复杂度为O(n^2)。

插入排算法是稳定的排序方法。

步骤

①从第一个元素开始，该元素可以认为已经被排序

②取出下一个元素，在已经排序的元素序列中从后向前扫描

③如果该元素（已排序）大于新元素，将该元素移到下一位置

④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤将新元素插入到该位置中

⑥重复步骤2

排序演示

算法实现

二、冒泡排序

介绍

冒泡排序（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)排序：基数排序，此外还有桶、箱排序。

㈤ 初始状态有序的表,哪种排序方式最快

用直接插入排序最快。

表格，又称为表，既是一种可视化交流模式，又是一种组织整理数据的手段。人们在通讯交流、科学研究以及数据分析活动当中广泛采用着形形色色的表格。各种表格常常会出现在印刷介质、手写记录、计算机软件、建筑装饰、交通标志等许许多多地方。

随着上下文的不同，用来确切描述表格的惯例和术语也会有所变化。此外，在种类、结构、灵活性、标注法、表达方法以及使用方面，不同的表格之间也炯然各异。在各种书籍和技术文章当中，表格通常放在带有编号和标题的浮动区域内，以此区别于文章的正文部分。

排版

先将表格的左右宽度适当缩小，再将整个表格调整到文档的居中位置，然后进行以下操作：

① 用"表格和边框"工具栏上的"对齐"按钮，将最后一行以外的各行设置为垂直居中；

② 用"表格和边框"工具栏上的"对齐"按钮，将最后一行设置为底端对齐；

表格中文字的方向可使用工具栏上的"更改文字方向"按钮进行调整。

方法

好的排序方法可以有效提高排序速度，提高排序效果。

在计算机领域主要使用数据排序方法根据占用内存的方式不同分为2大类：内部排序方法与外部排序方法。

内部排序方法

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择排序、交换排序、归并排序和基数排序。

㈥ 初始序列基本有序时,什么排序所用时间最短

直接插入或冒泡！！

㈦ 如何比较哪个算法运行时间最短冒泡排序算法。

在某些情况下第一种算法会更优，在极端情况下第二种算法会更优。
比较方法主要如下：
1. 理论推理法：计算一轮排序后执行的各类实际操作次数。
注：操作分为两类，一类是比较操作，一类是赋值操作
比较操作一般比赋值操作要快捷。计算同一组数据在两者的比较和赋值操作次数即可知道哪个更优。
2. 实践验证法：在同一运行环境下，对同一组数据进行排序操作，比较两者的运行时间即可知道哪个更优。

㈧ 常见排序算法归纳

排序算法一般分类：

比较两个相邻的元素，将值大的元素交换至右端。

依次比较两个相邻的数，将小数放到前面，大数放到后面

即在第一趟：首先比较第1个数和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此一直继续下去，直到比较最后两个数，将小数放前，大数放后。然后重复第一趟步骤，直到所有排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较。

第二趟完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较。

依次类推......

输出结果：

冒泡排序的优点： 每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

用时间复杂度来说：

从一个数组中随机选出一个数N，通过一趟排序将数组分割成三个部分，1、小于N的区域 2、等于N的区域 3、大于N的区域，然后再按照此方法对小于区的和大于区分别递归进行，从而达到整个数据变成有序数组。

如下图：

假设最开始的基准数据为数组的第一个元素23，则首先用一个临时变量去存储基准数据，即 tmp=23 ，然后分别从数组的两端扫描数组，设两个指示标志： low 指向起始位置， high 指向末尾。

首先从后半部分开始，如果 扫描到的值大于基准数据 就让 high-1 ，如果发现有元素比该基准数据的值小，比如上面的 18 <= tmp ，就让 high位置的值赋值给low位置 ，结果如下：

然后开始从前往后扫描，如果扫描到的值小于基准数据就让 low+1 ，如果发现有元素大于基准数据的值，比如上图 46 >= tmp ，就再将 low 位置的值赋值给 high 位置的值，指针移动并且数据交换后的结果如下：

然后再开始从前往后遍历，直到 low=high 结束循环，此时low或者high的下标就是 基准数据23在该数组中的正确索引位置 ，如下图所示：

这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。

然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。

输出结果：

最好情况下快排每次能恰好均分序列，那么时间复杂度就是O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为O(n^2)。

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

将一个数据插入到 已经排好序的有序数据 中

第一趟排序：

用数组的第二个数与第一个数( 看成是已有序的数据 )比较

第二趟排序：

用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较

在第二步中：

...

后面依此类推

输出结果：

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

举例：数组 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始数据： 5 2 8 4 9 1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的数据 {2 8 4 9 5} 进行比较，2最小，

排序结果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的数据 {8 4 9 5} 进行比较，4最小，8和4交换

排序结果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他数据 {8 9 5} 进行比较，5最小，8和5交换

排序结果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他数据 {9 8} 进行比较，8最小，8和9交换

排序结果： 1 2 4 5 8 9

输出结果：

归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

比如我们对 [8,4,5,7,1,3,6,2] 这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。

输出结果：

㈨ 在各类算法中那种算法排序是最快的

说句实话，没有最快这一说。

1. 如果不在乎浪费空间，应该是桶排序最快

2. 如果整体基本有序，插入排序最快

3. 如果考虑综合情况，快速排序更加实用常见（希尔排序、堆排序等各种排序也各有优劣）

4. 一般情况下，冒泡这种排序仅仅是名字起的有趣罢了，不太好用