开发者社区> 问答> 正文

求一个希尔排序法的代码

求一个希尔排序法的代码

展开
收起
知与谁同 2018-07-17 18:44:27 1366 0
2 条回答
写回答
取消 提交回答
  • 没时间自己动手写,以下也是网上的资料,供你参考的,希尔排序没有你想象的那么复杂,仔细研究下,会有好处的~~~~
    =========================================================================
    Shell排序
    Shell排序可以理解为插入排序的变种,它充分利用了插入排序的两个特点:
    1)当数据规模小的时候非常高效
    2)当给定数据已经有序时的时间代价为O(N)
    所以,Shell排序每次把数据分成若个小块,来使用插入排序,而且之后在这若个小块排好序的情况下把它们合成大一点的小块,继续使用插入排序,不停的合并小块,知道最后成一个块,并使用插入排序。

    这里每次分成若干小块是通过“增量” 来控制的,开始时增量交大,接近N/2,从而使得分割出来接近N/2个小块,逐渐的减小“增量“最终到减小到1。

    一直较好的增量序列是2^k-1,2^(k-1)-1,.....7,3,1,这样可使Shell排序时间复杂度达到O(N^1.5)
    所以我在实现Shell排序的时候采用该增量序列
    package algorithms;

    /**
    * @author yovn
    */
    public class ShellSorter<E extends Comparable<E>> extends Sorter<E> {

    /* (non-Javadoc)
    * Our delta value choose 2^k-1,2^(k-1)-1,.7,3,1.
    * complexity is O(n^1.5)
    * @see algorithms.Sorter#sort(E[], int, int)
    */
    @Override
    public void sort(E[] array, int from, int len) {

    //1.calculate the first delta value;
    int value=1;
    while((value+1)*2<len)
    {
    value=(value+1)*2-1;

    }

    for(int delta=value;delta>=1;delta=(delta+1)/2-1)
    {
    for(int i=0;i<delta;i++)
    {
    modify_insert_sort(array,from+i,len-i,delta);
    }
    }

    }

    private final void modify_insert_sort(E[] array, int from, int len,int delta) {
    if(len<=1)return;
    E tmp=null;
    for(int i=from+delta;i<from+len;i+=delta)
    {
    tmp=array[i];
    int j=i;
    for(;j>from;j-=delta)
    {
    if(tmp.compareTo(array[j-delta])<0)
    {
    array[j]=array[j-delta];
    }
    else break;
    }
    array[j]=tmp;
    }

    }
    }
    2019-07-17 22:50:23
    赞同 展开评论 打赏
  • #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAX 100
    #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]);
    }
    printf("\n");
    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 = k+gap; i < MAX; i+=gap) {
    for(j = i - gap; j >= k; j-=gap) {
    if(number[j] > number[j+gap]) {
    SWAP(number[j], number[j+gap]);
    }
    else
    break;
    }
    }
    }
    printf("\ngap = %d:", gap);
    for(i = 0; i < MAX; i++)
    printf("%d ", number[i]);
    printf("\n");
    gap /= 2;
    }
    }
    2019-07-17 22:50:23
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载