各种排序算法的总结和比较(合集3篇)

2024-02-15 14:42:21 92

各种排序算法的总结和比较第1篇

思路：

把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

动画演示：

实现代码：

算法复杂度：O(nlog2n)算法空间复杂度：O(1)算法稳定性：稳定

各种排序算法的总结和比较第2篇

选择排序的时间复杂度为 O(n²)。

代码如下：

分析：假设输入为 4, 2, 5, 1, 3第一次循环后，变为 1, 2, 5, 4, 3，1 被移动到最前第二次循环后，变为 1, 2, 5, 4, 3，2 被移动到最前的第二个位置以此类推

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的。

插入排序的时间复杂度为 O(n²)。

代码如下：

分析：假设输入为 4, 2, 5, 1, 3第一次循环后，变为 2, 4, 5, 1, 3第二次循环后，变为 2, 4, 5, 1, 3第三次循环后，变为 1, 2, 4, 5, 3以此类推

其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

快速排序是不稳定的，其时间复杂度为 O(nlogn)。

代码如下：

分析：假设输入为 4, 2, 5, 1, 3第一轮递归后，变为 3, 2, 1, 4, 5第一轮递归后，变为 1, 2, 3, 4, 5以此类推

堆排序是借助堆来实现的选择排序。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

归并排序使用了递归分治的思想。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列...倒着来看，其实就是先两两合并，然后四四合并...最终形成有序序列。

归并排序空间复杂度为 O(n)，时间复杂度为 O(nlogn)。

代码如下：

希尔排序是插入排序的一种高效率的实现。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

希尔排序时间复杂度为 O(nlogn)。

代码如下：

前提条件：待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。

计数排序空间复杂度为 O(n)，时间复杂度为 O(n)。

代码如下：

桶排序算是计数排序的一种改进和推广。基本思想：使用映射函数将待排序的数组划分成M个的子区间(桶) 。接着对每个桶中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出每个桶中的全部内容即是一个有序序列。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1，那么f(k1)<=f(k2)。也就是说第 i 个桶中的最小数据都要大于第 i - 1 个桶中最大数据。

代码如下：

基数排序是一种和前面排序方式不同的排序方式，基数排序不需要进行关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级依次增加。

代码如下：