0%

排序算法伪代码及演示

发表于 更新于

排序算法是算法的入门，但是一个都没有很系统的去掌握，在这里总结一些方便自己学习。

##插入排序(Insertion sort)

插入排序就是每一步都将一个待排序的数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

伪代码：
对于插入排序，我们将其伪代码过程命名为INSERTION-SORT，其中参数是一个数组A[1..N]，包含长度为n的要排序的一个序列，在代码中，A的元素的数目n用A.length表示(下同).

示例 1：
A<5，2，4，6，1，3>


下标j指出正要被插入的数据，在for循环（循环变量为j)的每次迭代的开始，包含数组元素A[1..j-1]的子数组构成了当前排序好的数据，剩余的子数组[j+1…n]对应于未排序的数据。事实上，元素A[1..j-1]就是原来在位置1到j-1上的数组，但现在已按序排列。

该算法的运行时间是执行每条语句的运行时间之和。在排序算法中，若输入数组已反向排序，即按递减序排序好，则导致最坏情况。需要进行INSERTION-SORT的运行时间为T(n)=O(n²)

示例 2：

##归并排序(Merge Sort)

归并排序算法完全遵循前一章中提到的分治模式，直观上其操作如下：

  • 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
  • 解决：使用归并排序递归的排序两个子序列
  • 合并：合并两个已排序的子序列以产生已排序的答案。
    当待排序的长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已排好序。

伪代码：
归并排序算法的关键操作是“合并”步骤中两个已排序序列的合并。我们通过MERGE(A，p，q，r)来完成合并，其中A是一个数组，p，q，r是数组下标，满足p<=q<r。MERGE过程将两个已经排好序的子数组归并为一个。每次比较两个子数组中最小的数据(由于子数组已排序，所以该操作仅需Θ(1)时间），将较小的数据放入合并数组中，当两个数组中的元素全部取完时，即将两个子数组合并完毕。过程MERGE需要Θ(n)的时间，其中n=r-p+1是待合并元素的总数。

在伪代码中，为每个数组中添加了一个哨兵，它包含一个特殊的值，用于简化代码，这里使用∞作为哨兵值。

下面我们将过程MERGE作为归并排序算法中的一个子程序来使用。下面过程MERGE-SORT(A，p，r)排序子数组A[p...r]中的元素。若p>=r，则该子数组最多有一个元素，所以已经排序好了。否则，分解步骤简单地计算下一个下标q，将A[p..r]分成两个子数组A[p..q]和A[q+1..r]，前者包含⌈n/2⌉个元素，后则包含⌊n/2⌋个元素。

为了排序整个序列A=<A₁，A₂，...An>，我们执行初始调用MERGE-SORT(A，1，A.length)，这里A.length等于n。

示例 1：
A=<5，2，4，7，1，3，2，6>

归并排序将规模为n的问题分解为两个规模为n/2的子问题，在合并操作中需要Θ(n)的时间，不难分析出递归排序的最坏情况运行时间T(n)=2T(n/2)+Θ(n)。应用主定理，可知，T(n)为Θ(nlgn).

示例 2：


##冒泡排序(Bubble sort)
冒泡排序反复交换相邻的未按次序排列的元素，这样一趟过去以后，最小的数字被交换到了第一位，然后再从头开始进行两两交换比较，直到第二位时结束.
伪代码：

示例：

针对冒泡排序还有两种优化：

  1. 优化一：如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个Flag做标记，默认为false，如果发生交互则置为true，每轮结束时检测Flag，如果为true则继续，如果为false则返回。

  2. 优化二：某一轮结束位置为j，但是这一轮的最后一次交换发生在lastSwap的位置，则lastSwap到j之间是排好序的，下一轮的结束点就不必是j--了，而直接到lastSwap即可。

    ##快速排序(Quick sort)
    与归并排序一样，快速排序也使用分治思想下面对一个典型的子数组A[p..r]进行快速排序的三步分治过程：

  • 分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，下表q也是划分过程的一部分。

  • 通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]进行排序

  • 因为子数组都是原址排序的，所以不需要合并操作：数组A[p..r]已经有序

    伪代码:

为了排序一个数组A的全部元素，初始调用QUICKSORT(A，1，A.length)算法的关键部分是PARTITION过程，它实现了对子数组A[p..r]的原址重排。

下图显示了PARTITION如何在一个包含8个元素的数组上进行操作的过程。

PARTITION总是选择一个x=A[r]作为主元，并围绕它来划分子数组A[p..r]。随着程序的执行，数组被划分为4个区域，如图所示:

在子数组A[p..r]上，PARTITION维护了4个区域。A[p..i]区间内所有值小于等于x，A[i+1..j-1]区间内所有的值都大于x，A[r]=x。子数组A[j..r-1]中的值可能属于任何一种情况。

PARTITION在子数组A[p..r]上的时间复杂度是Θ(n)，其中n=r-p+1

示例：


##选择排序(Selection sort)
遍历数组，遍历到i时，a0,a1…ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。
具体步骤如下：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 以此类推，直到所有元素均排序完毕。
    示例：

    ##希尔排序

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。
##算法比较
下面用一张图总结下排序算法的性能：