排序方法有哪几种（排序方法）

大家好，今日小科来聊聊一篇关于排序方法有哪几种，排序方法的文章，现在让我们往下看看吧！

1、插入排序

2、插入是最简单、最直观的排序算法。它的工作原理是在排序后的序列中从后向前扫描未排序的数据，找到对应的位置并插入。

3、算法步骤：

4、1)要排序第一个序列的第一个元素被视为有序序列，第二个元素到最后一个元素被视为未排序序列。

5、2)从头到尾扫描无序序列，将每个扫描的元素插入有序序列的适当位置。(如果要插入的元素等于有序序列中的一个元素，则将要插入的元素插入到等于的元素之后。)

6、谢尔分类

7、Hill排序，也称为降序增量排序算法，是插入排序的一个更高效的改进版本。然而，希尔排序算法是不稳定的。

8、希尔排序基于插入排序的以下两个属性：

9、在对几乎排序的数据进行操作时，插入排序是高效的，即可以达到线性排序的效率。

10、但是插入排序一般效率很低，因为插入排序一次只能移动一位数据。

11、Hill排序的基本思路是：首先，将待排序的整个记录序列分成若干子序列进行直接插入排序。当整个序列中的记录都是“基本有序”时，直接插入所有记录并依次排序。

12、算法步骤：

13、1)选择一个增量序列t1，t2，tk，其中titj，tk=1；

14、2)根据增量序号k，对序列进行k次排序；

15、3)每次排序时，根据对应的增量ti，将待排序的列分成若干个长度为m的子序列，每个子表直接插入排序。当增量因子只有1时，整个序列被当作一个表，表的长度就是整个序列的长度。

16、选择排序法

17、选择排序也是一种简单直观的排序算法。

18、算法步骤：

19、1)首先，在未排序的序列中找到最小(最大)的元素，并将其存储在已排序序列的开头。

20、2)继续从剩余的未排序元素中寻找最小(最大)的元素，然后放在排序后的序列的末尾。

21、3)重复第二步，直到所有元素都排序完毕。

22、冒泡排序

23、冒泡排序也是一种简单直观的排序算法。它反复访问要排序的序列，一次比较两个元素，如果它们的顺序不对，就切换它们。访问序列的工作一直重复到不需要交换为止，也就是说序列已经排序了。这种算法的名字来源于较小的元素会通过交换慢慢“浮”到序列的顶端。

24、算法步骤：

25、1)比较相邻元素。如果第一个比第二个大，两个都换。

26、2)对每对相邻的元素做同样的工作，从开头的第一对到结尾的最后一对。在这一步之后，最后一个元素将是最大的数字。

27、3)对除最后一个元素之外的所有元素重复上述步骤。

28、4)每次对越来越少的元素继续重复上述步骤，直到没有任何要比较的数字对。

29、合并分类

30、归并排序是一种基于归并操作的有效排序算法。这个算法是分而治之的典型应用。

31、算法步骤：

32、申请一个大小为两个排序序列之和的空间，这个空间用来存放合并后的序列。

33、设置两个指针，初始位置分别是两个排序序列的起始位置。

34、比较两个指针指向的元素，选择一个相对较小的元素放入合并空间，将指针移动到下一个位置。

35、重复步骤3，直到指针到达序列的末尾。

36、将另一个序列的所有剩余元素直接复制到合并序列的末尾。

37、快速排序

38、快速排序是由Tony Hall开发的一种排序算法。平均来说，对N个项目进行排序需要 (n log n)次比较。在最坏的情况下，需要进行 (N2)比较，但这种情况并不常见。事实上，快速排序通常比其他 (n log n)算法快得多，因为其内部循环可以在大多数架构中高效实现。

39、快速排序使用分治策略将一个列表分成两个子列表。

40、算法步骤：

41、1从序列中挑出一个元素，称之为“pivot”。

42、2重新排列顺序，所有小于基准值的元素放在基准前面，所有大于基准值的元素放在基准后面(相同的数字可以在两边)。在这个分区退出后，基准位于系列的中间。这称为分区操作。

43、3递归排序小于参考值的元素子系列和大于参考值的元素子系列。

44、在递归的最底层，序列的大小是零或一，也就是一直排序下去。虽然它一直在递归，但这种算法总是会退出，因为在每次迭代中，它至少会将一个元素放到最后一个位置。

45、堆排序

46、堆排序是指利用堆的数据结构设计的一种排序算法。Heap是一种类似于完全二叉树的结构，同时满足heap的性质：即子节点的键值或索引总是小于(或大于)其父节点。

47、堆排序的平均时间复杂度为 (nlogn)。

48、算法步骤：

49、1)创建一个堆H[0.n-1]

50、2)交换反应器的头部(最大值)和尾部。

51、3)将堆的大小减少1，并调用shift_down(0)以便将新数组顶部的数据调整到相应的位置。

52、4)重复步骤2，直到堆栈的大小为1。

53、基数排序

54、基数排序是一种非比较整数排序算法。它的原理是把整数按照位数切割成不同的数，然后按照每个位数进行比较。由于整数也可以用特定格式表示字符串(如姓名或日期)和浮点数，所以基数排序不仅可以用于整数。

55、在讨论基数排序之前，我们先简单介绍一下桶排序：

56、算法思路：将数组分成有限个桶。每个桶都是单独排序的(可以使用另一种排序算法，或者继续以递归方式使用桶排序来排序)。桶排序是鸽巢排序的归纳结果。当数组中要排序的值均匀分布时，桶排序使用线性时间( (n))。但桶排序不是比较排序，不受O(n log n)下限的影响。简单来说，就是将数据分组，放入桶中，然后对每个桶中的数据进行排序。

57、例如，要对n个整数A[1.n]在[1.1000]

58、首先，您可以将bucket设置为范围10。具体来说，让集合B[1]存储整数[1.10]，集合B[2]存储(10.20],集合B[i]存储((i-1)*10，i*10)的整数。总共有100桶。

59、然后，扫描一个[1.n]从头到尾，并将每个A[i]放入对应的桶B[j]中。然后对这100个桶中的数字进行排序。这时候可以使用冒泡，选择，甚至快速排序。一般来说，任何排序方法都可以。

60、最后依次输出每个桶中的数字，每个桶中的数字从小到大输出，这样就得到一个所有数字排列的序列。

61、假设有n个数字和m个桶。如果数字均匀分布，平均每个桶中有n/m个数字。如果

62、如果对每个桶中的数字进行快速排序，则整个算法的复杂度为

63、O(n m * n/m * log(n/m))=O(n nlognnlogm)

64、从上式可以看出，当m接近n时，桶排序复杂度接近O(n)。

65、当然，上述复杂度的计算是基于输入的N个数均匀分布的假设。这个假设很强，但是在实际应用中效果并不是那么好。如果所有的数字都落在同一个桶里，它就退化成一个一般的排序。

66、上面提到的大部分排序算法的时间复杂度为O(n2)，也有一些排序算法的时间复杂度为O(nlogn)。但是桶排序可以实现O(n)的时间复杂度。但是桶排序的缺点是：

67、1)首先空间复杂度比较高，额外成本大。排序有两个数组的空间开销，一个是存储要排序的数组，一个是所谓的桶。比如要排序的值是从0到m-1，那么就需要M个桶，这个桶数组至少需要M个空格。

68、2)其次，要排序的元素必须在一定范围内等等。

69、稳定性、时间复杂度、空间复杂度和各种类型的稳定性汇总如下图所示：

70、时间复杂度：

71、(1)平方顺序(o(n ^ 2))排序：直接插入、直接选择、冒泡排序；

72、(2)线性对数序(O(nlog2n))排序、快速排序、堆排序和归并排序；(3) O (n (1))排序，并且(是0和1之间的常数。Hill排序(4)线性排序(O(n))排序基数排序，此外还有桶和箱排序。

73、关于稳定性：

74、稳定排序算法：冒泡排序、插入排序、归并排序和基数排序。

75、不是一个稳定的排序算法：选择排序，快速排序，希尔排序和堆排序。

本文到此结束，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！