排序算法之插入类排序算法

放暑假了，但是自己不能给自己放假呀，下学期就大四了，要找工作，要准备，所以现在复习一下数据结构之

类的基础但是又很重要的一些东西，先看下这些简单的排序算法吧。这篇文章主要说的是插入类排序算法中的

直接插入排序，折半插入排序和希尔排序。我将这几个简单的算法写到了一个C文件中进行测试，下面就是这

个C文件：

/*

 * Copyright (c) 2010-~ zhouyongfei

 *

 * The source code is released for free distribution under the terms of the GNU General Public License

 *

 *

 * Author:  alen Chou

 * Created Time: 2010年07月18日 星期日 20时05分46秒

 * File Name: sort.c

 * Description:  这个文件是我再复习插入类排序时候写的代码

 *  

 */

#include

#include

/**

 * 直接插入排序的算法，比较简单的一个算法

 * @:r[]需要进行排序的数组，length数组元素的个数

 *

 * */

void InsSort(int r[], int length)

{

int i,j;

/*

* 这块为了使用r[0]作为监视哨，所以将r数组统一后移一位

* */

for(i = length;i > 0;i--){

r[i] = r[i-1];

}

for(i = 2;i <= length;i++){

r[0] = r[i];

j=i-1;

while(r[0] < r[j]){

r[j+1] = r[j];

j = j-1;

}

r[j+1] = r[0];

}

printf("after sort:\n");

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

printf("%d ",r[i]);

}

printf("\n");

for(i = 0;i < length;i++){

r[i] = r[i+1];

}

r[length] = length ;

}

/**

 * 折半插入排序

 * @:r[]需要排序的数组，length数组元素的个数

 *

 * */

void BinSort(int r[],int length)

{

int x,low,high,mid;

int i,j;

/**

* 这块是为了使用r[0]作为监视哨，

* 所以将r数组中的每个元素统一向后移动一位

*

* */

for(i = length;i > 0;i--){

r[i] = r[i-1];

}

for(i = 2;i <= length;i++){

x = r[i];

low = 1;

high = i - 1;

while(low <= high){

mid = (low + high)/2;

if(x < r[mid])

high = mid - 1;

else 

low = mid + 1;

}

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

r[j + 1] = r[j];

r[low] = x;

}

printf("after sort:\n");

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

printf("%d ",r[i]);

}

printf("\n");

}

/**

 *

 * 对记录数组r做一趟希尔排序，length为数组的长度

 * delta为增量

 *

 * */

void ShellInsert(int r[],int length,int delta)

{

int i,j;

for(i = length;i > 0;i--){

r[i] = r[i-1];

}

for(i = 1 + delta;i <= length;i++){

if(r[i] < r[i-delta]){

r[0] = r[i];

/**

*是在当前序列中找到合适的位置插

* 入，相当于前面的直接插入排序

*

* */

for(j = i-delta;j > 0&& r[0] < r[j];j -= delta){

r[j + delta] = r[j];//是在当前序列中找到合适的位置插

//入，相当于前面的直接插入排序

}

r[j + delta] = r[0];

}

}

for(i = 0;i < length;i++){

r[i] = r[i+1];

}

r[length] = length ;

}

/**

 * 对数组记录r做希尔排序，length为数组元素

 * 的个数，delta为增量数组，n为delta的长度

 *

 * */

void ShellSort(int r[],int length,int delta[],int n)

{

int i,j;

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

ShellInsert(r,length,delta[i]);

printf("after sort:\n");

for(i = 0;i < length;i++){

printf("%d ",r[i]);

}

printf("\n");

printf("the length is %d\n",length);

}

int main(int argc, char *argv[])

{

int i;

//int arr[] = {48,62,35,77,55,14,35,98};

int arr[] = {46,55,13,42,94,17,5,70,33,22};

int delta[] = {4,2,1};

int length = sizeof(arr)/sizeof(arr[0]);

printf("before sort:\n");

for(i = 0;i < length;i++){

printf("%d ",arr[i]);

}

printf("\n");

//InsSort(arr,length);

//BinSort(arr,length);

ShellSort(arr,length,delta,sizeof(delta)/sizeof(delta[0]));

return 0;

}

下面简单介绍一下，源程序中也有些简单的注释，相信有C基础的对这些算法都非常的熟悉了，但是这些又

是工业上不常用到的算法，毕竟效率有限，所以简单的介绍下就好了，感兴趣的可以留言讨论。

首先是直接插入排序，按照我们教材（数据结构-C语言描述 耿国华 高等教育出版社）的解释，为了节省空间，

提高效率，就使用了数组的第一个元素作为监视哨，这样就有了处男如的数组首先得空出第一个位置。然后就是在新摆放的数组中找到每次新插入的元素的位置，放进去，就行了。

然后就是折半插入排序：这个是再前面的直接插入排序的基础上改进了查找位置的算法，查找插入位置的时候

使用了二分搜索，也就是折半查找，因此能提高一些效率。

最后就是希尔排序，要理解希尔排序，关键得知道这么一点，再直接插入排序中，如果数组本来就具有一定的

顺序，那么就基本不怎么交换，因此效率会得到显著提升，希尔排序就是利用了直接插入排序的这个优点，将

原数组分成几份序列，给定增量（也就是隔几个划分为同一个序列）。每个序列组内进行直接插入排序，然后

每排一次就换一个已经变小的增量，继续分组排序，这样，最后基本上都已经是有序的序列在排序了，因此，

效率得到了显著的提高。

好了，插入类排序就写到这了。后面还有交换类排序，选择类排序分配类排序等等。我会逐一攻破他们，哈

哈。努力中。