本文主要是介绍基础算法| 常用排序算法小结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

转载自：https://mp.weixin.qq.com/s/Qsll45WSkWZrYexWi7v5qg

排序基础

排序的定义

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

排序的分类

排序可分为内排序和外排序。

所谓内排序就是所有的数据和操作都在内存中完成。

而外排序就是说需要排序的数据太大，无法全部塞进内存，需要在内存和外存之间多次数据交换才能完成的排序。

算法优劣的术语说明

⚫稳定：如果Ai=Aj，开始Ai在Aj前面，排完序之后Ai依然在Aj前面。

⚫不稳定：如果Ai=Aj，开始Ai在Aj前面，而排完序以后Ai有可能跑到Aj后面去了。

⚫时间复杂度：一个算法执行完所消耗的时间。

⚫空间复杂度：执行一个算法需要消耗的内存空间大小。

常见算法的复杂度及稳定性

1、冒泡排序(Bubble Sort)

常规冒泡排序

基本原理：

1）从序列的最左边开始，将两两相邻的两个元素（例如A[0]和A[1], A[1]和A[2], A[2]和A[3]等等）进行比较。将小的放左边，将大的放右边。例如A[i] > A[i+1]，那么就交换A[i]和A[i+1]的位置。那么经过一轮比较交换以后，A[n]里的值必然是A[0]~A[n]中的最大值。

2） 对剩下的元素A[0]~A[n-1]也进行上述操作。完成后A[n-1]里面存的就是A[0]~A[n-1]中的最大值。

3） 不断对剩下的元素进行上述操作，直到剩下元素只有A[0]时，排序完成。

冒泡排序改进版

此方法可称为定向冒泡排序，它和冒泡排序的不同之处在于，定向冒泡从左到右把最大数搬到最后面的时候，再反向从右往左把最小值搬到最左边

                                                               动态图

定向冒泡的优势：比如对序列{4, 5, 6, 7, 8, 2}排序，传统冒泡要访问5次序列，而定向冒泡排序只需要访问一次就OK了。

2、选择排序(Selection Sort)

基本原理：

1）先从A[0]~A[n]中找最小元素A[i]，交换A[0]和A[i]的位置。

2）再从剩下的元素A[1]~A[n]中找最小元素A[j]，交换A[1]和A[j]的位置。

3）不断在剩下的元素中找最小的元素丢到开头，直到剩下最后一个元素。

选择排序每次将最小值丢到开头的时候，有可能会打乱相等元素的位置。因此，它是不稳定的。

也注意区分其和冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

3、插入排序(Insertion Sort)

基本原理：

1）从A[0]开始，则A[0]可认为是已排序列。

2）取出下一个元素(比如A[1])，在已排序列中从右往左扫描，如果已排序列中的元素大于取出的元素（(A[1])），那么就将该元素（已排序列中的）往后挪一个位置。

3）直到在已排序列中找到一个小于等于取出元素的元素。将取出元素插入该元素（已排序列中的）后一个位置。

4）不断重复步骤2-3.直到所有元素都插入到已排序列。

可以看出，关于相等元素，排序前后并不会改变他们的位置。因此，插入排序又是稳定的。

4、希尔排序(Shell Sort)

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。其中希尔排序是基于以下几点做出改进的：

1）直接插入排序对于几乎排好的数据有着极高的效率。基本可以达到线性排序时的效率。

2）但是对于一般的乱序数据来说，直接插入排序由于每次只能将数据往后搬一位，从这点上来说它效率又是及其低下的。

基本原理：

1）将无序数据分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行直接插入排序；

2）然后再选择一个更小的增量，再将数据分割为多个子序列进行直接插入排序......

3）不断重复步骤2，直到最后增量变为1，即对所有数据使用直接插入排序（此时所有数据几乎都排好了，直接插入效率较高），最终排序完成。

值得一提的是，由于数据划分为多个区域，在每个区域中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。因此希尔排序是不稳定的排序。

5、归并排序(Merge Sort)

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。效率为O(nlogn)，1945年由冯·诺伊曼首次提出。归并排序的实现分为递归实现与非递归(迭代)实现。

这里我们讨论递归实现。归并排序依赖于归并操作。归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

基本原理：

1）申请内存空间A，大小为两个已排序列之和。

2）设定两个指针，分别指向两个已排序列的首元素。

3）比较两个指针指向的元素大小，将小的那个元素丢进内存空间A。同时指向该元素的指针向前（后？）移动一位。

4）不断重复步骤3），直到任何一个序列的元素全被丢进空间A。那么就把另外一个序列剩下的所有元素丢进空间A。

归并排序是稳定的算法。

6、快速排序(Quick Sort)

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：开始选取一个基准数，通过一趟排序将基准数移到序列的合适位置，使得，左边的这部分都小于等于基准数，右边的部分都大于等于基准数，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

那么，对于一个序列，怎样才能使基准数移动到正确位置，以便能使左边的数都小于等于它，右边的数都大于等于它呢？还是以数组A[N]为例，为大家慢慢道来：

1）设置两个变量i、j，排序开始的时候：i=0，j=N；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j；

6）3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束。

快速排序是不稳定的排序算法。

这篇关于基础算法| 常用排序算法小结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！