做网站可以用别人的源码吗,asp网站vps搬家,个人免费网页,哪里有平面设计说明 插入排序法由未排序的后半部前端取出一个值#xff0c;插入已排序前半部的适当位置#xff0c;概念简单但速度不快。 排序要加快的基本原则之一#xff0c;是让后一次的排序进行时#xff0c;尽量利用前一次排序后的结果#xff0c;以加快排序的速度#xff0c;Shel…说明 插入排序法由未排序的后半部前端取出一个值插入已排序前半部的适当位置概念简单但速度不快。 排序要加快的基本原则之一是让后一次的排序进行时尽量利用前一次排序后的结果以加快排序的速度Shell排序法即是基于此一概念来改良插入排序法。
解法 Shell排序法最初是D.L Shell于1959所提出假设要排序的元素有n个则每次进行插入排序时并不是所有的元素同时进行时而是取一段间隔。 Shell首先将间隔设定为n/2然后跳跃进行插入排序再来将间隔n/4跳跃进行排序动作再来间隔设定为n/8、n/16直到间隔为1之后的最 后一次排序终止由于上一次的排序动作都会将固定间隔内的元素排序好所以当间隔越来越小时某些元素位于正确位置的机率越高因此最后几次的排序动作将 可以大幅减低。 举个例子来说假设有一未排序的数字如右89 12 65 97 61 81 27 2 61 98 数字的总数共有10个所以第一次我们将间隔设定为10 / 2 5此时我们对间隔为5的数字进行排序如下所示 画线连结的部份表示 要一起进行排序的部份再来将间隔设定为5 / 2的商也就是2则第二次的插入排序对象如下所示 再来间隔设定为2 / 2 1此时就是单纯的插入排序了由于大部份的元素都已大致排序过了所以最后一次的插入排序几乎没作什么排序动作了 将间隔设定为n / 2是D.L Shell最初所提出在教科书中使用这个间隔比较好说明然而Shell排序法的关键在于间隔的选定例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度 其中4*(2j)2 3*(2j) 1不可超过元素总数n值使用上式找出j后代入4*(2j)2 3*(2j) 1求得第一个间隔然后将2j除以2代入求得第二个间隔再来依此类推。 后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快另外Shell排序法的概念也可以用来改良气泡排序法。
代码部分
#include stdio.h
#include stdlib.h
#include time.h
#define MAX 10
#define SWAP(x,y) {int t; t x; x y; y t;} void shellsort(int[]); int main(void) { int number[MAX] {0}; int i; srand(time(NULL)); printf(排序前); for(i 0; i MAX; i) { number[i] rand() % 100; printf(%d , number[i]); } shellsort(number); return 0;
} void shellsort(int number[]) { int i, j, k, gap, t; gap MAX / 2; while(gap 0) { for(k 0; k gap; k) { for(i kgap; i MAX; igap) { for(j i - gap; j k; j-gap) { if(number[j] number[jgap]) { SWAP(number[j], number[jgap]); } else break; } } } printf(\ngap %d, gap); for(i 0; i MAX; i) printf(%d , number[i]); printf(\n); gap / 2; }
}
