首页 > 编程语言 > 详细

常见排序算法-----希尔排序

时间:2018-07-20 22:08:54      阅读:26      评论:0      收藏:0      [点我收藏+]

标签:col   ati   大数据   style   shells   一个   稳定性   每次   增量   

 1 // 原理 :用grap(希尔增量)将大数据组进行分组 对每一组进行排序
 2     // 在写算法的时候,可以从第grap(希尔增量)个元素开始比较,每次减少grap 即可与同一组的上个元素进行比较,当遍历完一次后
 3     // grap/2,继续循环,直到grap >0;
 4   
 5     // 插入版
 6     public static void shellSort(int[] arr) {
 7         int grap = arr.length >> 1;
 8 
 9         for (; grap > 0; grap >> 1) {
10 
11             for (int i = grap; i < arr.length; i++) {
12                 int j = i;
13                 while (j >= grap && arr[j] < arr[j - grap]) {
14                     swap(arr, j, j - grap);
15                     j -= grap;
16                 }
17             }
18 
19         }
20     }
21 
22     // 移动版
23     public static void shellSort2(int[] arr) {
24         int grap = arr.length >> 1;
25         for (; grap > 0; grap >>1) {
26             for (int i = grap; i < arr.length; i++) {
27                 int j = i;
28                 int temp = arr[i];
29                 
30                 while (j >= grap && temp < arr[j - grap]) {
31                     arr[j] = arr[j - grap];
32                     j -= grap;
33                 }
34                 arr[j] = temp;
35             }
36 
37         }
38     }

 时间复杂度为O(n^3/2) 希尔排序不是一个稳定性排序

常见排序算法-----希尔排序

标签:col   ati   大数据   style   shells   一个   稳定性   每次   增量   

原文:https://www.cnblogs.com/maxbolg/p/9343685.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号