黑马程序员技术交流社区

标题: [上海校区]JS实现希尔排序 [打印本页]

---

作者: 束玉杰    时间: 2020-1-16 15:03
标题: [上海校区]JS实现希尔排序
希尔排序：将无序数组分割成若干子序列，子序列不是逐段分割的，而是相隔特定增量的子序列，对各个子序列进行插入排序，然后再选择一个更小的增量，再将之前排序后的数组按这个增量分割成多个子序列，...,不断选择更小增量，直到增量为1时，再对序列进行一次插入排序，使序列最终成为有序序列，排序完成。
以下实例展示希尔排序的过程：
这里的首选增量为n/2,每次增量为原先的1/2,直到增量为1
30 80 49 70 65 20 44 33 56 96
第一趟：增量为5
30------------------20
     80------------------44
           49------------------33
                70-------------------56
                      65-------------------96
对每个子序列进行插入排序后序列为：
20 44 33 56 65 30 80 49 70 96
第二趟：增量为2
20-----33-----65-----80-----70
     44-----56-----30-----49-----96
对每个子序列进行插入排序后序列为：
20 30 33 44 65 49 70 56 80 96
第三趟：增量为1
直接对序列进行插入排序：
20 30 33 44 49 56 65 70 80 96

[JavaScript] 纯文本查看 复制代码

function ShellSort(arr){

                var len=arr.length;

                var gap,i;

                for(gap=Math.floor(len/2);gap>0;gap=Math.floor(gap/2)){

                        for(i=gap;i<len;i++){

                                var temp=arr;

                                var j=i-gap;

                                while(j>=0 && arr[j]>temp){

                                        arr[j+gap]=arr[j];

                                        j=j-gap;

                                }

                                if(j!=i-gap){

                                        arr[j+gap]=temp;

                                }

                        }

                        

                }

        }

        var arr=[30,80,49,70,65,20,44,33,56,96];

        ShellSort(arr);

        document.write(arr);

原文链接：https://blog.csdn.net/fendou_dexiaoniao/article/details/46591915

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2