shell排序算法思想
shell排序其实是插入排序的升级版，我们可以把数组分成h组，对每组 进行排序，然后不断的缩短h,当h缩短为1时就退化成了插入排序。
shell排序算法实现
public static void main(String[] args) {
int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
int[] sortList = shellSort(arr);
for (int i : sortList) {
System.out.print(i + " ");
}
}
/**
* shell sort
*
* @param arr
* @return
*/
private static int[] shellSort(int[] arr) {
if (arr.length == 0) return null;
// 计算出步长
int h = 1;
int N = arr.length;
while (h < N / 3) h = (h * 3 + 1);
//控制步长
while (h >= 1) {
//插入排序
for (int i = h; i < N; i++) {
for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
int temp = arr[j - h];
arr[j - h] = arr[j];
arr[j] = temp;
}
}
h = h / 3;
}
return arr;
}
算法复杂度
1.算法的最坏时间复杂度为O(n^2)
2.算法的最好时间复杂度为O(n)
3.算法的空间复杂度为O(n)
算法稳定性
1 shell排序是不稳定的
想看更多完整版请点击：shell排序
