白话经典算法系列(冒泡、直接插入、希尔排序、直接选择、归并排

白话经典算法系列（转载）

原文作者：MoreWindows

目录

白话经典算法系列（转载） ........................................................................................................... 1

白话经典算法系列之一 冒泡排序的三种实现 ..................................................................... 2 白话经典算法系列之二 直接插入排序的三种实现 ............................................................. 4 白话经典算法系列之三 希尔排序的实现 ............................................................................. 6 白话经典算法系列之四 直接选择排序及交换二个数据的正确实现 ................................. 9 白话经典算法系列之五 归并排序的实现 ........................................................................... 11 白话经典算法系列之六 快速排序 快速搞定 ..................................................................... 15 白话经典算法系列之七 堆与堆排序 ................................................................................... 19

二叉堆的定义 ................................................................................................................. 19 堆的存储 ......................................................................................................................... 19 堆的操作——插入删除 ................................................................................................. 20 堆的插入 ......................................................................................................................... 21 堆的删除 ......................................................................................................................... 21 堆化数组 ......................................................................................................................... 22 堆排序 ............................................................................................................................. 24 转载请标明出处，原文地址：http://www.77cn.com.cn/morewindows/archive/2011/08/22/2149612.html ........................... 24

白话经典算法系列之一 冒泡排序的三种实现

冒泡排序是非常容易理解和实现，以从小到大排序举例： 设数组长度为N。

1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。

3．N=N-1，如果N不为0就重复前面二步，否则排序完成。 按照定义很容易写出代码： //冒泡排序1

void BubbleSort1(int a[], int n) { }

下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。 //冒泡排序2

void BubbleSort2(int a[], int n) {

int j, k; bool flag;

int i, j;

for (i = 0; i < n; i++)

for (j = 1; j < n - i; j++)

if (a[j - 1] > a[j])

Swap(a[j - 1], a[j]);

k = n; flag = true; while (flag)

}

}

flag = false;

for (j = 1; j < k; j++)

if (a[j - 1] > a[j]) { }

Swap(a[j - 1], a[j]); flag = true;

k--;

再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。 //冒泡排序3

void BubbleSort3(int a[], int n) {

int j, k; int flag;

flag = n; while (flag > 0) {

k = flag; flag = 0;

for (j = 1; j < k; j++)

if (a[j - 1] > a[j]) {

Swap(a[j - 1], a[j]);

}

}

}

冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。

白话经典算法系列之二 直接插入排序的三种实现

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1 2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 3. i++并重复第二步直到i==n-1。排序完成。

下面给出严格按照定义书写的代码（由小到大排序）： void Insertsort1(int a[], int n) {

int i, j, k;

for (i = 1; i < n; i++) {

//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置 for (j = i - 1; j >= 0; j--)

if (a[j] < a[i])

break;

//如找到了一个合适的位置 if (j != i - 1) {

//将比a[i]大的数据向后移

}

}

}

for (k = i - 1; k > j; k--)

a[k + 1] = a[k];

//将a[i]放到正确位置上 a[k + 1] = temp;

这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i] > a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j + 1]处。 void Insertsort2(int a[], int n) { }

再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1] > a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1] <= a[j]。这样也可以实现将一个新数据新并入到有序区间。 void Insertsort3(int a[], int n) {

int i, j; int i, j;

for (i = 1; i < n; i++)

if (a[i] < a[i - 1]) { }

int temp = a[i];

for (j = i - 1; j >= 0 && a[j] > temp; j--)

a[j + 1] = a[j];

a[j + 1] = temp;

}

for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)

Swap(a[j], a[j + 1]);

白话经典算法系列之三 希尔排序的实现

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

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。 以n=10的一个数组49, 38, 65, …… 此处隐藏：8922字，全部文档内容请下载后查看。喜欢就下载吧 ……