《白话经典算法系列(冒泡、直接插入、希尔排序、直接选择、归并排序、快速排序、堆与堆排序)-----标题要长》由会员分享，可在线阅读，更多相关《白话经典算法系列(冒泡、直接插入、希尔排序、直接选择、归并排序、快速排序、堆与堆排序)-----标题要长（27页珍藏版）》请在金锄头文库上搜索。
1、白话经典算法系列（转载）白话经典算法系列（转载）原文作者：MoreWindows目录目录白话经典算法系列（转载） .1 白话经典算法系列之一 冒泡排序的三种实现.2 白话经典算法系列之二 直接插入排序的三种实现.4 白话经典算法系列之三 希尔排序的实现.6 白话经典算法系列之四 直接选择排序及交换二个数据的正确实现.9 白话经典算法系列之五 归并排序的实现.11 白话经典算法系列之六 快速排序 快速搞定.15 白话经典算法系列之七 堆与堆排序.19 二叉堆的定义二叉堆的定义 .19 堆的存储堆的存储.19 堆的操作堆的操作插入删除插入删除.20 堆的插入.21 堆的删除.21 堆化数组堆化数组
2、.22 堆排序堆排序.24 转载请标明出处，原文地址： http:/ .24白话经典算法系列之一白话经典算法系列之一 冒泡排序的三种实现冒泡排序的三种实现 冒泡排序是非常容易理解和实现，以从小到大排序举例：设数组长度为 N。1比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。2这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第 N-1 个位置。3N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。按照定义很容易写出代码：/冒泡排序 1void BubbleSort1(int a, int n)int i, j;for (i
3、= 0; i aj)Swap(aj - 1, aj);下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为 true，否则为 false。明显如果有一趟没有发生交换，说明排序已经完成。/冒泡排序 2void BubbleSort2(int a, int n)int j, k;bool flag;k = n;flag = true;while (flag)flag = false;for (j = 1; j aj)Swap(aj - 1, aj);flag = true;k-;再做进一步的优化。如果有 100 个数的数组，仅前面 10 个无序，后面 90 个都已排好序且都大于前面 10 个
4、数字，那么在第一趟遍历后，最后发生交换的位置必定小于 10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。/冒泡排序 3void BubbleSort3(int a, int n)int j, k;int flag;flag = n;while (flag 0)k = flag;flag = 0;for (j = 1; j aj)Swap(aj - 1, aj);flag = j;冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。白话经典算法系列之二白话经典算法系列之二 直接插入排序的三种实现
5、直接插入排序的三种实现 直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为 a0n-1。1. 初始时，a0自成 1 个有序区，无序区为 a1.n-1。令 i=12. 将 ai并入当前的有序区 a0i-1中形成 a0i的有序区间。3. i+并重复第二步直到 i=n-1。排序完成。下面给出严格按照定义书写的代码（由小到大排序）：void Insertsort1(int a, int n)int i, j, k;for (i = 1; i = 0; j-)if (aj j; k-
6、)ak + 1 = ak;/将 ai放到正确位置上ak + 1 = temp;这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次 ai先和前面一个数据 ai-1比较，如果 ai ai-1说明a0i也是有序的，无须调整。否则就令 j=i-1,temp=ai。然后一边将数据 aj向后移动一边向前搜索，当有数据 aj= 0 j-)aj + 1 = aj;aj + 1 = temp;再对将 aj插入到前面 a0j-1的有序区间所用的方法进行改写，用数据交换代替数据后移。如果 aj前一个数据 aj-1 aj，就交换 aj和 aj-1，再 j-直到aj-1 = 0 j-)
7、Swap(aj, aj + 1);白话经典算法系列之三白话经典算法系列之三 希尔排序的实现希尔排序的实现 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因 DLShell于 1959 年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。以 n=10 的一个数组 49, 38, 65, 97
8、, 26, 13, 27, 49, 55, 4 为例第一次 gap = 10 / 2 = 549 38 65 97 26 13 27 49 55 41A 1B2A 2B3A 3B4A 4B5A 5B 1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。第二次 gap = 5 / 2 = 2排序后13 27
9、49 55 4 49 38 65 97 261A 1B 1C 1D 1E2A 2B 2C 2D 2E第三次 gap = 2 / 2 = 14 26 13 27 38 49 49 55 97 651A 1B 1C 1D 1E 1F 1G 1H 1I 1J第四次 gap = 1 / 2 = 0 排序完成得到数组：4 13 26 27 38 49 49 55 65 97下面给出严格按照定义来写的希尔排序void shellsort1(int a, int n)int i, j, gap;for (gap = n / 2; gap 0; gap /= 2) /步长for (i = 0; i = 0 k
10、 -= gap;ak + gap = temp;很明显，上面的 shellsort1 代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从 1A 到 1E，从 2A 到 2E，可以改成从 1B 开始，先和 1A 比较，然后取 2B与 2A 比较，再取 1C 与前面自己组内的数据比较.。这种每次从数组第 gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。void shellsort2(int a, int n)int j, gap;for (gap = n / 2; gap 0; gap /= 2)for
11、(j = gap; j = 0 k -= gap;ak + gap = temp;再将直接插入排序部分用 白话经典算法系列之二 直接插入排序的三种实现 中直接插入排序的第三种方法来改写下：void shellsort3(int a, int n)int i, j, gap;for (gap = n / 2; gap 0; gap /= 2)for (i = gap; i = 0 j -= gap)Swap(aj, aj + gap);这样代码就变得非常简洁了。附注：上面希尔排序的步长选择都是从 n/2 开始，每次再减半，直到最后为 1。其实也可以有另外的更高效的步长选择，如果读者有兴趣了解，请参阅维基百科上对希尔排序步长的说明：http:/zh.wikipedia.org/wiki/%E5%B8%8C%E5
