排序算法之插入类排序算法
时间：2010-07-19 来源：wwwzyf
放暑假了，但是自己不能给自己放假呀，下学期就大四了，要找工作，要准备，所以现在复习一下数据结构之
类的基础但是又很重要的一些东西，先看下这些简单的排序算法吧。这篇文章主要说的是插入类排序算法中的
直接插入排序，折半插入排序和希尔排序。我将这几个简单的算法写到了一个C文件中进行测试，下面就是这
个C文件：
下面简单介绍一下，源程序中也有些简单的注释，相信有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<[email protected]> * Created Time: 2010年07月18日 星期日 20时05分46秒 * File Name: sort.c * Description: 这个文件是我再复习插入类排序时候写的代码 * */
#include <stdio.h> #include <stdlib.h>
/** * 直接插入排序的算法，比较简单的一个算法 * @: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语言描述 耿国华 高等教育出版社）的解释，为了节省空间， 提高效率，就使用了数组的第一个元素作为监视哨，这样就有了处男如的数组首先得空出第一个位置。然后就是在新摆放的数组中找到每次新插入的元素的位置，放进去，就行了。
然后就是折半插入排序：这个是再前面的直接插入排序的基础上改进了查找位置的算法，查找插入位置的时候 使用了二分搜索，也就是折半查找，因此能提高一些效率。
最后就是希尔排序，要理解希尔排序，关键得知道这么一点，再直接插入排序中，如果数组本来就具有一定的 顺序，那么就基本不怎么交换，因此效率会得到显著提升，希尔排序就是利用了直接插入排序的这个优点，将 原数组分成几份序列，给定增量（也就是隔几个划分为同一个序列）。每个序列组内进行直接插入排序，然后 每排一次就换一个已经变小的增量，继续分组排序，这样，最后基本上都已经是有序的序列在排序了，因此， 效率得到了显著的提高。
好了，插入类排序就写到这了。后面还有交换类排序，选择类排序分配类排序等等。我会逐一攻破他们，哈 哈。努力中。
相关阅读 更多 +
排行榜 更多 +
