排序算法：Java实现希尔排序

希尔排序的思路是先分组再整合

先对下标进行分组，比如当数组长度为20时，一开始选定一个间隔值为10

对数组进行排序，每隔10个元素比较大小并交换，以下标为间隔，1和11比较、2和12比较......10和20比较

然后间隔值减半，从10到5，(1,6,11,16)比较、（2,7,12,17）比较.....(5,10,15,20)比较

间隔值逐步减半，再从5到2，从2到1，间隔值为1时也就是整个数组的元素进行排序

因为一开始分组交换时，没有顾及到不同组之间元素的前后关系，所以这是一个不稳定的排序算法

代码示例

 1 public class ShellSortDemo {

 2     public static void main(String[] args) {

 3

 4

 5

 6         int[] arr = new int[20];

 7         int[] arr1 = new int[arr.length];

 8         for (int i = 0; i < arr.length; i++) {

 9             arr[i] = new Random().nextInt() % 1000;

10             arr1[i] = arr[i];

11         }

12         System.out.println(Arrays.toString(arr));

13         shellSort(arr);

14         sort(arr1);

15         System.out.println(Arrays.toString(arr));

16     }

17

18     public static void shellSort(int[] arr){

19

20         /**

21          * 虽然嵌套了三个循环，但是数据的交换次数并不多

22          */

23         int second = 0;

24         for (int gap = arr.length/2; gap >= 1 ; gap/=2) {

25             for (int i = gap; i < arr.length; i++) {

26                 int j = i;

27                 //分组后，每一组先排序前面的，再排序后面的

28                 while (j-gap >= 0 && arr[j] < arr[j-gap]){

29                     second++;

30                     swap(arr,j,j-gap);

31                     j -= gap;

32                 }

33             }

34         }

35         System.out.println("希尔排序交换次数："+second);

36     }

37

38     /**

39      * 基本的冒泡排序

40      */

41     public static void sort(int[] arr){

42         int second = 0;

43         for (int i = 0; i < arr.length - 1; i++) {

44             for (int j = 0; j < arr.length -1; j++) {

45                 if(arr[j] > arr[j+1]){

46                     swap(arr,j,j+1);

47                     second++;

48                 }

49             }

50         }

51         System.out.println("冒泡排序交换次数："+second);

52

53     }

54     public static void swap(int[] arr,int a,int b){

55         int tmp = arr[a];

56         arr[a] = arr[b];

57         arr[b] = tmp;

58     }

59 }

希尔排序代码主要是三个循环和一个判断，虽然写了三个循环，但是比较了一下，数据交换次数比冒泡排序少了很多。

巴特西

排序算法：Java实现希尔排序

最新文章

热门文章