ShellSort
【ShellSort】思想：待排序的记录按增量分割若干区域，然后对每个区域的对应的元素进行insertionSort。
增量为n/2，即将序列分成两份,注意：增量按需而定
排序前
文章图片
Paste_Image.png
插入排序后
文章图片
Paste_Image.png
两个区域内的元素对应逐一排序
文章图片
Paste_Image.png
增量为n/5
排序前
文章图片
Paste_Image.png
以此类推...
Java展现其思想
package sortingAlgo;
import java.util.Arrays;
import java.util.Random;
/**
* @author 水皮蛋
* 思想：待排序的记录按增量分割若干区域，然后对每个区域的对应的元素进行
*
*/
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)));
}/**
* 每个增量区进行元素对应插入排序
*
* @param arr
* @param d
* @return
*/
public static int[] shellInsertSort(int[] arr, int d) {
int n = arr.length, j = 0, key = 0;
// i是未排序的第一个角标
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类产生随机数组的对象
*
* @return 随机数组
*/
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;
}}推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长