简述几种排序算法的区别

[kukyxs]

No description provided.

[kami-zeros]

这边简单介绍几个经典排序算法：

1.冒泡排序（BubbleSort）：

• 算法简介：冒泡排序是一种简单的排序算法。

• 算法思想：它重复地走访要排序的数列，一次比较两个元素，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。

• 算法分析：冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。但是简单啊！！！

• 优点：稳定

• 缺点：慢，每次只能移动两个相邻的数据。

2.快速排序（QuickSort）：

• 算法简介：快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。

• 算法思想：选择一个基准元素（一般选择序列最左边的值作为基准数据，其实基准的选择对算法是有影响的），将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序。

• 算法分析：快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，但对于内存非常有限的机器来说，它不是一个好的选择。

• 优点：极快，数据移动少；

• 缺点：不稳定（在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序）

3.归并排序（MergeSort）：

• 算法简介：归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。

• 算法思想：首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止。

• 算法分析：归并排序和选择排序（包括堆/直接选择）一样，归并排序的性能不受输入数据的影响，比选择排序稍微快一点，但是需要多一倍的内存空间，因为它需要一个额外的数组。

• 优点：稳定；

• 缺点：占内存

4.选择排序（SelectionSort）：

• 算法简介：选择排序也是一种简单的排序。

• 算法思想：第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；以此类推，直到最后。

• 算法分析：所以用到它的时候，数据规模越小越好，无论什么数据进去都是O(n2)的时间复杂度。唯一的好处可能就是不占用额外的内存空间了吧。

5.堆排序（Heapsort）：

• 算法简介：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

• 算法思想：堆排序会将所有的数据建成一个堆，最大的数据在堆顶（此堆为初始的无序区），然后将堆顶数据和序列的最后一个数据交换，由此得到新的无序区和有序区，且满足<=的值；接下来再次重建堆（因为交换后新的堆顶可能违反堆的性质，因此需要对当前无序区调整为新堆），交换数据，依次下去，就可以排序所有的数据。

• 算法分析：堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

6.插入排序（InsertSort）：

• 算法简介：插入排序是一种简单排序算法。

• 算法思想：将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。即先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。

• 算法分析：插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。但是它比冒泡排序快2倍。一般在数据大于1000或重复排序超过200的数据下使用。

• 优点：稳定，快

• 缺点：比较次数不一定，数据重复向后移动。

7.希尔排序（ShellSort）：

• 算法简介：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

• 算法思想：先将整个待排序元素序列分割成若干子序列（就是分成几个组且个数相同）（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

• 算法分析：Shell排序比冒泡排序快5倍，比插入排序大致快2倍。比快排，归并，堆排慢很多（有时在小数组中比快速排序和堆排序快）。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。

8.基数排序（RadixSort）：

• 算法简介：基数排序和通常的排序算法并不走同样的路线，它是一种比较新颖的算法。

• 算法思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

• 算法分析：它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。

参考链接：
(https://blog.csdn.net/m0_37962600/article/details/81475585)
(https://www.cnblogs.com/onepixel/articles/7674659.html)