七大排序算法总结

前面介绍了七大算法的思想与实现步骤，下面来做一个归总。

排序方法	平均复杂度	最坏复杂度	最好复杂度	辅助空间	稳定性
直接选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
冒泡排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
直接插入排序	O(n^2)	O(n^2)	O(n^2)	O(1)	稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(1)	不稳定
希尔排序	O(nlogn)~O(n^2)	O(n^1.3)	O(n^2)	O(logn)~O(n)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定

直接选择排序

思想

直接选择排序，整体思想是将数据分成两个区域，有序区与无序区。排序的时候是每次从无序区中选择出最小的数，然后插入到有序区中的最末尾，从而形成更大的有序区。直到无序区中的数为零，结束排序。

步骤

假设排序数组为a[0…n-1];

1. 首先有序区中的个数为0，令i = 0。从无序区中选择最小的数，加入到有序区a[i]中。使得有序区为a[0..i],无序区为a[i...n-1]
2. 完成后 i++ ,然后继续前面的步骤，直到 i = n-1 为止。使得全部数都在有序区中。

冒泡排序

思想

冒泡排序主要是相邻的两个数两两进行比较，拿从小到大说明，进行冒泡排序后会将大的数沉到底部，将小得数浮到顶部。所以冒泡说法由此得名。

步骤

以从小到大为例，排序数组大小为n。

1. 第N = 0趟排序开始都从a[0]开始与其下面的相邻的数进行比较，如果大于相邻的数则交换他们的位置。
2. 继续与下一个相邻的数进行比较，大于相邻的就交换，最后进行比较n-1次后，第N = 0趟排序结束，最大的数就在数组的a[n-1]处。
3. 重复前面的步骤，直到 N = n-1,排序结束。

直接插入排序

思想

直接插入排序的基本思想是:将需要排序的关键数与前面已经排好序的数据从后往前进行比较，使其插入到合适的位置。

步骤

排序数组为a[0...n]

1. 将a[0]作为起始数据，从a[1]开始作为关键字向前进行比较，若小于前面所遇到的比较数，则交换两个比较数的位置，否则直接进行下一个关键字的比较。
2. 重复前面的步骤，直到将a[n]作为关键字进行比较。比较完以后则排序结束。

归并排序

思想

归并排序是一个效率相对较高的排序算法，它采用的是分治的思想，将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。

步骤

1. 将待排序的序列采用分治思想将其划分成若干组，使其有序，其中可采用递归进行划分。
2. 将有序的组分别进行归并操作，其中借助一个辅助数组，将左右划分的有序组从头开始进行比较，将较小的数加入到辅助数组中，且较小的所在有序数组向后自增，再与原来比较的数进行比较。
3. 重复上面2的步骤，直到所有数据比较完毕，或者将还有剩余数未比较的有序数据直接按原有的顺序加入到辅助数组中,最后将已经排好序的辅助数组加入到原有数组的相应位置。
4. 重复上面的2、3步骤，直到所有的左右划分归并完毕。

快速排序

思想

快速排序的主要思想是：将一个待排序序列分成两个部分，以其中的一个数据作为分界线，其中一部分小于这个分界线的数据，另一部分大于这个分界线的数据。因为采用递归的思想，再对这两个序列进行快速排序，直到所以的数据都是有序的。

步骤

假设待排序的数组为a[0...n-1]

1. 一般都将第一个数a[i] (i = 0) 作为关键数，即快速排序的分界数。先从数组的后面开始即初值j = n-1，逐个向前进行遍历与选的的关键数进行比较(j--)，若大于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且i++记录此时的i、j。
2. 停止前面的遍历，再从数组的第i个位置开始向后进行遍历，逐个与关键数进行比较(i++)，若小于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且j--记录此时的i、j。
3. 重复上面的步骤，直到i==j就结束本次快速排序。
4. 此时已经将其按关键数分成两个部分，再重复前面的步骤，对划分的部分进行快速排序，直到划分的组中的数据个数为1即此时所有数据有序。

希尔排序

思想

希尔排序是记录增量来进行分组，再对分组内部进行直接插入排序，随着增量的不断减小，直到增量减小到1时，即每个分组中的数据量为1，此时排序结束。

步骤

设待排序的数组为a[0...n-1]

1. 一般开始取增量数d=n/2。从a[0]~a[d-1]将数组中数据之间的间隔为增量数d的倍数归为相同组。
2. 依次对每组中的数据进行直接插入排序，使其有序。
3. 再增量数d=d/2，重复上面的步骤，直到d=1为止。

堆排序

思想

堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。堆排序分为大根堆与小根堆，大根堆（小根堆）表示在完全二叉树中，所用的非叶子节点都大于等于（小于等于）他们左右子节点（存在）。所以堆的顶点不是最大数就是最小数。这样的话我们就可以借助这种性质，每次都取出大根堆（小根堆）的顶点数，形成有序序列。

步骤

1. 首先生成小根堆或大根堆，这里以小根堆为例。我们可以将每一个非叶子节点都看做是一个最小的完全二叉树，将他们都生成小根堆，从最后一个非叶子节点开始，把其当做是根节点，逐步向前进行创建小根堆。例如上图中的大根堆，将其变成小根堆的步骤，先以30为根节点，根据小根堆的性质，需要与10互换位置;再以60为根节点，发现需要与15互换位置；最后与70为根节点，需要与原来30的位置即现在交换位置的10互换位置，最终形成小根堆。
2. 然后就是取出形成的小根堆得顶点值，将其与堆中第N(N=n)个节点互换位置，即a[N-1]。
3. 此时小根堆被破坏，再重新生产小根堆N--，但此时要生成的数的范围为a[0...N-1]。
4. 重复上面的步骤2、3，直到N=1，即a[0]，排序结束。

如有不足之处欢迎指出，全部代码已经放到github上，有需要的可以下载。

github地址：https://github.com/idisfkj/Arithmetic

转载请指明出处 idisfkj博客：https://idisfkj.github.io