思想：待排序的記錄按增量分割若干區(qū)域，然后對(duì)每個(gè)區(qū)域的對(duì)應(yīng)的元素進(jìn)行insertionSort胯陋。
增量為n/2，即將序列分成兩份,注意：增量按需而定
排序前
Paste_Image.png
插入排序后
Paste_Image.png
兩個(gè)區(qū)域內(nèi)的元素對(duì)應(yīng)逐一排序
Paste_Image.png
增量為n/5
排序前
Paste_Image.png
以此類推...
Java展現(xiàn)其思想
package sortingAlgo;
import java.util.Arrays;
import java.util.Random;
/**
* @author 水皮蛋
* 思想：待排序的記錄按增量分割若干區(qū)域袱箱，然后對(duì)每個(gè)區(qū)域的對(duì)應(yīng)的元素進(jìn)行
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = createRandomArray();
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(shellSort(arr)));
}
/**
* 每個(gè)增量區(qū)進(jìn)行元素對(duì)應(yīng)插入排序
*
* @param arr
* @param d
* @return
*/
public static int[] shellInsertSort(int[] arr, int d) {
int n = arr.length, j = 0, key = 0;
// i是未排序的第一個(gè)角標(biāo)
for (int i = d; i < n; i++) {
j = i - d;
key = arr[i];
while (j >= 0 && arr[j] > key) {
arr[j + d] = arr[j];
j -= d;
}
arr[j + d] = key;
}
return arr;
}
/**
* 每輪增量排序依次
*
* @param arr
* @return
*/
public static int[] shellSort(int[] arr) {
if (arr == null)
throw new NullPointerException();
int n = arr.length;
if (!(n > 1))
return null;
// 定義增量
int d = n / 2;
while (d >= 1) {
shellInsertSort(arr, d);
d /= 2;
}
return arr;
}
/**
* 使用Random類產(chǎn)生隨機(jī)數(shù)組的對(duì)象
*
* @return 隨機(jī)數(shù)組
*/
public static int[] createRandomArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100);
}
return array;
}
}
