几种常见排序算法的分析

左手的ㄟ右手 2022-07-17 04:24 259阅读 0赞

# 几种常见排序算法的分析 #

## 摘要 ##

> 插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序和基数排序是计算机科学中常用的几种排序算法。本文简要的介绍了这几种算法的思路，并给出了公认的这些算法的时间复杂度表。在本文的最后，通过实验比较了各种算法的执行效率，并做了一些分析。

## 前言 ##

> 冒泡排序是最简单的排序算法，在所有算法中平均效率是最低的，但便于理解，适用于记录个数ｎ较小的排序中；选择排序适用于记录个数ｎ较小而记录本身信息量较大的排序中；插入排序适用于记录个数ｎ较小而原数组基本有序的排序中；希尔排序适用于记录个数较大而记录本身信息量较小的排序中；快速排序是从平均时间性能而言最佳的算法，适用于记录个数ｎ较大而记录无序的排序中；归并排序适用于记录个数ｎ较大而记录信息量也较大的排序中；基数排序适合于ｎ值很大而关键字较小的序列。

## 排序算法概述 ##

*  排序定义: 所谓计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法(Sortingalgorithm)则是一种能将一串数据依照特定的方式进行排列的一种算法。
 *  排序方式: 利用所需重排记录的排序码(SortKey)的值的大小，按照升序或降序将原纪录的顺序重新安排。

## 插入排序算法介绍 ##

插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。

> 插入排序的算法思路：  
> （1） 设置监视哨r\[0\]，将待插入纪录的值赋值给r\[0\]；  
> （2） 设置开始查找的位置j；  
> （3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r\[0\].key≥r\[j\].key为止；  
> （4） 将r\[0\]插入r\[j+1\]的位置上。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

## 希尔排序算法介绍 ##

> 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量d\_t=1(d\_t < d\_(t-1) < ⋯ < d\_2 < d\_1)，即所有记录放在同一组中进行直接插入排序为止。  
> 该方法实质上是一种分组插入方法。  
> 比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比\[2\] 较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。  
> 一般的初次取序列的一半为增量，以后每次减半，直到增量为1。  
> 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

## 冒泡排序算法介绍 ##

假如一个数组有n个数，那么我们可以从第一个数开始从头到尾两两比较，当前一个数比后一个数大时，则交换他们的位置，直到最大的一个数被排在了数组的后尾。然后最后一个数固定，不再需要比较，只需要按照刚刚的方法重复比较前面的n-1个数，知道排出顺序。

## 快速排序算法介绍 ##

快速排序（Quicksort）是对冒泡排序的一种改进。  
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
设要排序的数组是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

> 算法是：  
> 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；  
> 2）以第一个数组元素作为关键数据，赋值给key，即 key=A\[0\]；  
> 3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A\[J\]，并与key交换；  
> 4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A\[I\]，与key交换；  
> 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)

## 选择排序算法介绍 ##

选择排序的基本思想：第1趟，在待排序记录r\[1\]~r\[n\]中选出最小的记录，将它与r\[1\]交换；第2趟，在待排序记录r\[2\]~r\[n\]中选出最小的记录，将它与r\[2\]交换；以此类推，第i趟在待排序记录r\[i\]~r\[n\]中选出最小的记录，将它与r\[i\]交换，使有序序列不断增长直到全部排序完毕。

## 归并排序算法介绍 ##

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

> 归并过程为：比较a\[i\]和a\[j\]的大小，若a\[i\]≤a\[j\]，则将第一个有序表中的元素a\[i\]复制到r\[k\]中，并令i和k分别加上1；否则将第二个有序表中的元素a\[j\]复制到r\[k\]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间\[s,t\]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间\[s,t\]。

## 基数排序算法介绍 ##

基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。  
它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

不妨通过一个具体的实例来展示一下，基数排序是如何进行的。 设有一个初始序列为: R \{50, 123, 543, 187, 49, 30, 0, 2, 11, 100\}。我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。所以我们不妨把0~9视为10个桶。  
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R\[0\] = 50，个位数上是0，将这个数存入编号为0的桶中。（如图1）

![基数排序][20160831153305057]

#### 图1 基数排序 ####

分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。  
这时，得到的序列就是个位数上呈递增趋势的序列。  
按照个位数排序： \{50, 30, 0, 100, 11, 2, 123, 543, 187, 49\}。  
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

## 附排序算法代码[java语言实现][java] ##

[20160831153305057]: /images/20220717/64710d9e175c43cbb9dc2f3c34d815af.png
[java]: http://blog.csdn.net/jcq521045349/article/details/52389685