vlambda博客
学习文章列表

今天来聊一聊常见的几种排序算法。分别是冒泡排序、选择排序、堆排序、插入排序、归并排序、快速排序和希尔排序。

冒泡排序（Bubble Sort）

冒泡排序是一种经典的交换排序算法，通过交换数据元素的位置进行排序。

冒泡排序的基本思想：

冒泡算法就是从无序序列头部开始，进行两两比较，根据大小交换位置，直到将最大（或最小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分。然后继续这个过程，直到全部数据元素都排列好。

冒泡排序的运行过程：

1、比较相邻的两个元素，如果第一个比第二个大（或者小），就交换这两个元素。

2、对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对，这样完成后最后一个元素就会是最大（或最小）的元素。

3、针对所有的元素重复以上的步骤，除了最后已经选出的有序元素。

4、持续每次对越来越少的无序元素重复上面的步骤，知道没有任何一对元素需要比较，则完成排序。无序序列变成有序序列。

冒泡排序性能分析：

1、时间复杂度

当原始序列为正序排列时（即已经是有序序列），这个时候为最好情况，此时时间复杂度为O(n)；

当原始序列为逆序排列时，此时为最坏情况，此时时间复杂度为O(n^2)；

当原始序列杂乱无章时，此时平均时间复杂度为O(n^2)。

2、空间复杂度

冒泡排序过程中需要一个临时变量来进行两两交换，所以需要的额外空间为1，所以空间复杂度为O(1)。

3、稳定性

冒泡排序在排序过程中，元素两两交换的时候，相同元素的前后顺序并没有改变（相同元素进行比较时不更改顺序），所以冒泡排序是一种稳定排序算法。

冒泡排序Swift实现：

选择排序（Select Sort）

选择排序是通过不断的选择序列中最大（或最小）的元素来进行排序。

选择排序的基本思想：

选择排序就是不断从未排序队列中选择最大（或者最小）的元素放在已经排序队列的队尾，直到所有元素都排好顺序。

选择排序的运行过程：

1、首先在原始序列中找到最大（或最小）元素，存放到排序序列的起始位置。

2、再从剩余未排序元素中继续寻找最大（或最小）元素，然后放到已排序序列的末尾。

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

选择排序性能分析：

1、时间复杂度

选择排序平均时间复杂度为O(n^2)

2、空间复杂度

选择排序的空间复杂度为O(1)

3、稳定性

选择排序是不稳定的排序算法。因为在选出未排序队列中最大或者最小的元素之后，把这个元素放到已排序队列的队尾实际上就是把这个最大或最小元素和未排序队列中的第一个元素交换位置。这样就可能会改变数组中元素的顺序，所以选择排序是不稳定的算法排序。

选择排序Swift实现：

堆排序（Heap Sort）

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

堆排序的基本思想：

从最大（最小）堆的顶部不断取走堆顶元素放到有序序列中，直到堆的元素被全部取完。堆排序完全依赖于最大（最小）堆的相关操作。

堆排序的运行过程：

1、创建一个最大（或最小堆）。

2、把堆首和堆尾元素互换。

3、把堆的大小减一，重新构造一个最大（最小）堆。

4、重复上述步骤2和3，直到堆的大小减少为1。

堆排序的性能分析：

1、时间复杂度

堆排序的时间复杂度为O(n*logn)。调整堆的时间复杂度为O(logn)，然后有n个节点，所以堆排序的时间复杂度为O(n*logn)。

2、空间复杂度

堆排序的空间复杂度为O(1)

3、稳定性

堆排序是不稳定的排序算法。我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

堆排序Swift实现：

插入排序（Insertion Sort）

插入排序是一种通过不断的将数据元素插入到合适的位置进行排序的算法。

插入排序的基本思想：

顺序的把待排序的序列中的各个元素按其关键字的大小，插入到已经排序的序列的适当位置。

插入排序的运行过程：

1、将待排序序列的第一个元素看做是一个有序序列，把第二个元素到最后一个元素当成是未排序序列；

2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入到有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

插入排序的性能分析：

1、时间复杂度

插入排序的平均时间复杂度为O(n^2)

2、空间复杂度

插入排序的空间复杂度为O(1)

3、稳定性

插入排序是稳定的排序算法

插入排序Swift实现：

归并排序（Merge Sort）

归并排序是创建在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，并且各层分治递归可以同时进行。

归并排序的基本思想：

把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序的子序列合并为整体有序序列。

归并排序的运行过程：

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2、设定两个指针，最初位置分别为两个已经排序序列的起始位置

3、比较两个指针所指向的元素，选择相对较小（或者大）的元素放入到合并空间，并移动指针到下一位置

4、重复上述步骤3直到某一指针到达序列尾

5、将另一序列剩下的所有元素直接复制到合并序列尾

归并排序示例：

归并排序的性能分析：

1、时间复杂度

归并排序的时间复杂度为O(n*logn)

2、空间复杂度

归并排序的空间复杂度为O(1)

3、稳定性

归并排序是稳定的排序算法

归并排序Swift实现：

快速排序（Quick Sort）

快速排序是一种交换排序算法，通过交换元素的位置进行排序。

快速排序的基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，一次达到整个数据变成有序序列。

快速排序的运行过程：

1、从序列中挑出一个元素，称为“基准”，一般是选取序列的第一个元素。

2、重新排序数列，所有比基准值小的元素摆放到基准前面，所有比基准值大的元素摆在基准后面（相同的数可以放在任一边）。在这个分区结束之后，该基准就处于数列的中间位置，这个称为分区操作。

3、递归的把小于基准值元素的子数列和大于基准值元素的子数列排序

4、直到序列的大小是0或者1，也就是所有的元素都已经被排序好了，递归结束。

快速排序的性能分析

1、时间复杂度

快速排序通常被认为在同数量级的排序方法中平均性能是最好的。快速排序的平均时间复杂度为O(n*logn)

2、空间复杂度

快速排序的空间复杂度为O(logn)

3、稳定性

快速排序是一种不稳定的排序算法

快速排序Swift实现：

希尔排序（Shell Sort）

希尔排序是一种典型的插入排序算法，通过对原始序列进行分组进行排序。

希尔排序的基本思想：

先将整个待排序的序列分割成若干子序列分别进行直接插入排序，待整个序列基本有序的时候，在对全体依次进行插入排序。

希尔排序运行过程示例：

希尔排序的性能分析：

1、时间复杂度

希尔排序的平均时间复杂度会比O(n²)好一些。

2、空间复杂度

希尔排序的空间复杂度为O(1)

3、稳定性

希尔排序的是不稳定的排序算法

希尔排序Swift实现：