会python真的可以为所欲为0(回)
359天前
这里还有人吗1(回)
544天前这里还有人吗0(回)
544天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
769天前到处都是羊，不想上班0(回)
849天前
鸽子
0(回)
853天前/** |
* 希尔排序：我们选择步长为：15,7,3,1 我们选择步长公式为：2^k-1,2^(k-1)-1,……,15,7,3,1 |
* (2^4-1,2^3-1,2^2-1,2^1-1) 注意所有排序都是从小到大排。 |
*/ |
public class ShellSort { |
/** |
* 排序算法的实现，对数组中指定的元素进行排序 |
* |
* @param array |
* 待排序的数组 |
* @param from |
* 从哪里开始排序 |
* @param end |
* 排到哪里 |
* @param c |
* 比较器 |
*/ |
public void sort(Integer[] array, int from, int end) { |
// 初始步长，实质为每轮的分组数 |
int step = initialStep(end - from + 1); |
// 第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值 |
for (; step >= 1; step = (step + 1) / 2 - 1) { |
// 对每轮里的每个分组进行循环 |
for (int groupIndex = 0; groupIndex < step; groupIndex++) { |
// 对每组进行直接插入排序 |
insertSort(array, groupIndex, step, end); |
} |
} |
} |
/** |
* 直接插入排序实现 |
* |
* @param array |
* 待排序数组 |
* @param groupIndex |
* 对每轮的哪一组进行排序 |
* @param step |
* 步长 |
* @param end |
* 整个数组要排哪个元素止 |
* @param c |
* 比较器 |
*/ |
public void insertSort(Integer[] array, int groupIndex, int step, int end) { |
int startIndex = groupIndex;// 从哪里开始排序 |
int endIndex = startIndex;// 排到哪里 |
/* |
* 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内， |
* 如果在数组范围内，则继续循环，直到索引超现数组范围 |
*/ |
while ((endIndex + step) <= end) { |
endIndex += step; |
} |
// i为每小组里的第二个元素开始 |
for (int i = groupIndex + step; i <= end; i += step) { |
for (int j = groupIndex; j < i; j += step) { |
Integer insertedElem = array[i]; |
// 从有序数组中最一个元素开始查找第一个大于待插入的元素 |
if ((array[j].compareTo(insertedElem)) >= 0) { |
// 找到插入点后，从插入点开始向后所有元素后移一位 |
move(array, j, i - step, step); |
array[j] = insertedElem; |
break; |
} |
} |
} |
} |
/** |
* 根据数组长度求初始步长 |
* |
* 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k 为排序轮次 |
* |
* 初始步长：step = 2^k-1 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值（因 |
* 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4） |
* |
* 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把 2^k 表 达式 转换成 step 表达式，则 |
* 2^k-1 可使用 (step + 1)*2-1 替换（因为 step+1 相当于第k-1 轮的步长，所以在 step+1 基础上乘以 2 |
* 就相当于 2^k 了），即步长与数组长度的关系不等式为 (step + 1)*2 - 1 < len -1 |
* |
* @param len |
* 数组长度 |
* @return |
*/ |
public static int initialStep(int len) { |
/* |
* 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推: |
* 1,3,7,15,...,2^(k-1)-1,2^k-1 |
* 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不用分组，此时直接退化为直接插入排序 |
*/ |
int step = 1; |
// 试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长 |
while ((step + 1) * 2 - 1 < len - 1) { |
step = (step + 1) * 2 - 1; |
} |
System.out.println("初始步长 : " + step); |
return step; |
} |
/** |
* 以指定的步长将数组元素后移，步长指定每个元素间的间隔 |
* |
* @param array |
* 待排序数组 |
* @param startIndex |
* 从哪里开始移 |
* @param endIndex |
* 到哪个元素止 |
* @param step |
* 步长 |
*/ |
protected final void move(Integer[] array, int startIndex, int endIndex, |
int step) { |
for (int i = endIndex; i >= startIndex; i -= step) { |
array[i + step] = array[i]; |
} |
} |
/** |
* 测试 |
* |
* @param args |
*/ |
public static void main(String[] args) { |
Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 }; |
ShellSort shellSort = new ShellSort(); |
shellSort.sort(intgArr, 0, intgArr.length - 1); |
for (Integer intObj : intgArr) { |
System.out.print(intObj + " "); |
} |
} |
} |
