希尔排序之Java实现
一、方法一
package cn.com.zfc.lesson21.sort; /**
*
* @title ShellSort
* @describe 希尔排序 1959 年发明的
* @author 张富昌
* @date 2016年10月1日下午5:35:50
*/
public class ShellSort_1 {
// 希尔排序是对插入排序的一种改进。
// 基本思想：先将整个待排数据元素序列分割成若干个子序列，分别对各个子序列进行直接插入排序。
// 等整个序列中的数据元素“基本有序”时，在对整体元素进行一次直接插入排序
// 时间复杂度：O(n) ~ O(n^2)
public static void main(String[] args) {
// 声明整型数组
int[] array = new int[10];
// 使用循环和随机数初始化数组
for (int i = 0; i < array.length; i++) {
array[i] = (int) Math.round(Math.random() * 100);
}
System.out.println("原始数组为：");
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("排序后的数组为：");
array = shellSort(array);
for (int i : array) {
System.out.print(i + " ");
}
} /**
*
* 功能：冒泡排序的变种，希尔排序的基本思想是：首先按照一个序列递减的方法逐渐进行排序
*
* 参数：int[] array
*
* 返回类型：int[]
*/
public static int[] shellSort(int[] array) {
// 使用临时数组，替代原始数组
int[] arr = array;
// 以增量 i进行直接插入排序
int gap = arr.length;
do {
gap = gap / 2;
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= gap; j -= gap) {
// 较小的数排在前面
if (arr[j] < arr[j - gap]) {
int temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
} else {
break;
}
}
}
} while (gap > 1); return arr;
}
}
运行结果：
二、方法二
package cn.com.zfc.lesson21.sort; /**
*
* @title ShellSort
* @describe 希尔排序 1959 年发明的
* @author 张富昌
* @date 2016年10月1日下午5:35:50
*/
public class ShellSort_2 {
// 希尔排序是对插入排序的一种改进。
// 基本思想：先将整个待排数据元素序列分割成若干个子序列，分别对各个子序列进行直接插入排序。
// 等整个序列中的数据元素“基本有序”时，在对整体元素进行一次直接插入排序
// 时间复杂度：O(n) ~ O(n^2) public static void main(String[] args) {
// 声明整型数组
int[] array = new int[10];
// 使用循环和随机数初始化数组
for (int i = 0; i < array.length; i++) {
array[i] = (int) Math.round(Math.random() * 100);
}
System.out.println("原始数组为：");
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("排序后的数组为：");
array = shellSort(array);
for (int i : array) {
System.out.print(i + " ");
}
} /**
*
* 功能：冒泡排序的变种，希尔排序的基本思想是：首先按照一个序列递减的方法逐渐进行排序
*
* 参数：int[] array
*
* 返回类型：int[]
*/
public static int[] shellSort(int[] array) {
// 使用临时数组，替代原始数组
int[] arr = array;
// 以增量 i进行直接插入排序
int gap = arr.length;
// 临时变量
int j, temp;
do {
gap = gap / 2;
for (int i = gap; i < arr.length; i++) {
if (arr[i] < arr[i - gap]) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
} while (gap > 1); return arr;
}
}
运行结果：