排序算法 什么是计算机排序算法?

文章目录：

1. 什么是计算机排序算法?
2. 排序算法总结

一、什么是计算机排序算法?

在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是归并排序。

对n个记录的文件进行快速排序，所需要的辅助存储空间大致为O(1og2n)。

1、所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；

2、快速排序为O(logn)，为栈所需的辅助空间；

3、归并排序所需辅助空间最多，其空间复杂度为O(n)；

4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。

扩展资料

计算机排序算法的特点

1、有穷性

一个算法应包含有限的操作步骤，而不能是无限的。有穷性值在合理范围之内，如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们不把他视为有效算法。

2、确定性

算法中的每一个步骤都应当是确定的，而不应当是含糊的，摩棱两可的。算法中的每一个步骤应当不致被解释成不同含义的，而应是十分明确的。也就是说，算法的含义应当是唯一的，而不应当产生歧义性。

3、有零个或多个输入

所谓输入，即在执行算法是需要从外界取得必要的信息。

4、有一个或多个输出

算法的目的是为了求解，没有输出的算法是没有意义的。

5、有效性

算法中的每一个步骤都应当能有效的执行，并得到确定的结果。

二、排序算法总结

　　排序算法是什么?有多少种?排序算法总结又是怎样?以下是为您整理的排序算法总结，供您参考!

　　【排序算法总结】

　　排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。

　　排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。

　　稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。

　　以下来总结常用的排序算法，加深对排序的理解。

　　 冒泡排序

　　原理

　　俩俩比较相邻记录的排序码，若发生逆序，则交换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

　　性能

　　时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

　　优化

　　若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

　　代码

　 　插入排序

　　原理

　　依次选择一个待排序的数据，插入到前边已排好序的序列中。

　　性能

　　时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

　　优化

　　直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。

　　折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

　　使用场景

　　当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

　　代码

　　 希尔排序

　　原理

　　插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：

　　插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。

　　但插入排序在每次往前插入时只能将数据移动一位，效率比较低。

　　所以希尔排序的思想是：

　　先是取一个合适的gap

　　缩小间隔gap，例如去gap=ceil(gap/2)，重复上述子序列划分和排序

　　直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。

　　性能

　　开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点;其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

　　代码

　　 选择排序

　　原理

　　每次从未排序的序列中找到最小值，记录并最后存放到已排序序列的末尾

　　性能

　　时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的(把最小值交换到已排序的末尾导致的)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

　　代码

　　 快速排序

　　原理

　　分而治之思想：

　　Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q]，左边的元素都比基准小，右边的元素都比基准大;

　　Conquer：对俩个划分的数组进行递归排序;

　　Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。

　　性能

　　快排的平均时间复杂度为O(NlogN)，空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N);且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。

　　优化

　　当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。

　　所以快排的优化思路如下：

　　优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。

　　在规模较小情况下，采用直接插入排序

　　代码

　　 归并排序

　　原理

　　分而治之思想：

　　Divide：将n个元素平均划分为各含n/2个元素的子序列;

　　Conquer：递归的解决俩个规模为n/2的子问题;

　　Combine：合并俩个已排序的子序列。

　　性能

　　时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

　　优化

　　优化思路：

　　在规模较小时，合并排序可采用直接插入;

　　在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。

　　代码

　　 堆排序

　　原理

　　堆的性质：

　　是一棵完全二叉树

　　每个节点的值都大于或等于其子节点的值，为最大堆;反之为最小堆。

　　堆排序思想：

　　将待排序的序列构造成一个最大堆，此时序列的最大值为根节点

　　依次将根节点与待排序序列的最后一个元素交换

　　再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

　　性能

　　时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。

　　使用场景

　　想知道最大值或最小值时，比如优先级队列，作业调度等场景。

　　代码

　　 计数排序

　　原理

　　先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。

　　性能

　　时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。

　　使用场景

　　算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。

　　代码

　　 桶排序

　　原理

　　根据待排序列元素的大小范围，均匀独立的划分M个桶

　　将N个输入元素分布到各个桶中去

　　再对各个桶中的元素进行排序

　　此时再按次序把各桶中的元素列出来即是已排序好的。

　　性能

　　时间复杂度为O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空间复杂度为O(N+M)，算法是稳定的，且与初始序列无关。

　　使用场景

　　算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。

　　 基数排序

　　原理

　　对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：

　　MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

　　LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

　　性能

　　时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。

　 　总结

　　以上排序算法的时间、空间与稳定性的总结如下：

以上是问答百科网为你整理的2条关于排序算法的问题，希望对你有帮助！更多相关排序算法的内容请站内查找。