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

【排序算法（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 { 2public static void main(String[] args) { 3 4 5 6int[] arr = new int[20]; 7int[] arr1 = new int[arr.length]; 8for (int i = 0; i < arr.length; i++) { 9arr[i] = new Random().nextInt() % 1000; 10arr1[i] = arr[i]; 11} 12System.out.println(Arrays.toString(arr)); 13shellSort(arr); 14sort(arr1); 15System.out.println(Arrays.toString(arr)); 16} 17 18public static void shellSort(int[] arr){ 19 20/** 21* 虽然嵌套了三个循环，但是数据的交换次数并不多 22*/ 23int second = 0; 24for (int gap = arr.length/2; gap >= 1 ; gap/=2) { 25for (int i = gap; i < arr.length; i++) { 26int j = i; 27//分组后，每一组先排序前面的，再排序后面的 28while (j-gap >= 0 && arr[j] < arr[j-gap]){ 29second++; 30swap(arr,j,j-gap); 31j -= gap; 32} 33} 34} 35System.out.println("希尔排序交换次数："+second); 36} 37 38/** 39* 基本的冒泡排序 40*/ 41public static void sort(int[] arr){ 42int second = 0; 43for (int i = 0; i < arr.length - 1; i++) { 44for (int j = 0; j < arr.length -1; j++) { 45if(arr[j] > arr[j+1]){ 46swap(arr,j,j+1); 47second++; 48} 49} 50} 51System.out.println("冒泡排序交换次数："+second); 52 53} 54public static void swap(int[] arr,int a,int b){ 55int tmp = arr[a]; 56arr[a] = arr[b]; 57arr[b] = tmp; 58} 59 }

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