自己写的shell排序和堆排序，效率很差，比直接插入还差，诚求大神找BUG，

Question

下面是自己的算法实现
希尔排序：
package sort;import java.util.Random;public class ShellSort {
public static void main(String[] args) {
int[] array = new int[100000];
Random r   = new Random();

for(int i = 0;i<array.length-1;i++){
array[i] = r.nextInt(1000000);
}
Long l1 = System.currentTimeMillis();
shellSort(array);
Long l2 = System.currentTimeMillis();
System.out.println((l2-l1)+"");

} public static void shellSort(int[] array) {
int step = array.length / 2;
// 设定I为步长,步长终止条件为i大于等于1，步长以/2的方式递减，这个组成循环不变式，初始条件，步长=length/2，每次步长=步长/2，终止条件，步长>0
for (int i = step; i >= 1; i = i / 2) {
// 设定m为每一组里面的开头，开头由0-（步长-1）,共使用插入排序排序m个数组。
for (int m = 0; m < i; m++) {
//下面是插入排序，这个应该分离出来。
// 设定开始排序的数字位置为m（开头）+i；
for (int n = m + i; n < array.length; n = n + i) {
int g = n;
while (g-i >= 0) {
if (array[g] < array[g - i]) {
int a = array[g];
array[g] = array[g - i];
array[g - i] = a;
} else {
// 这一步错误，因为步长为2的时候如果第二个大于第一个，就直接退出了，所以就完蛋了，以后的都没有排
// break;
}
g = g - i;
}
}
}
}
}
}堆排序：
package sort;import java.util.Random;public class HeapSort {
public static void main(String[] args) {
int[] array = new int[100000];
Random r   = new Random();

for(int i = 0;i<array.length-1;i++){
array[i] = r.nextInt(1000000);
}
Long l1 = System.currentTimeMillis();
sort(array);
Long l2 = System.currentTimeMillis();
System.out.println((l2-l1)+"");

} public static void heapSort(int[] array, int i,int size) {

int leftChildPosition = 2 * i;
int rightChildPosition = 2 * i + 1;
int max = -1; if (array[i] < array[leftChildPosition]) {
max = leftChildPosition;
} if (array[rightChildPosition] < size) {
if (array[rightChildPosition] > array[leftChildPosition]) {
max = rightChildPosition;
}
} if (max != -1) {
int change = array[max];
array[max] = array[i];
array[i] = change;
if (max <= size / 2 - 1) {
heapSort(array, max,size);
}

} } public static void buildSort(int[] array, int size) {
int i;
// 从最后一个非叶子节点开始，对每个非叶子节点进型最小根调整，保证每个根节点都是其子树中的最小值
for (i = size / 2 - 1; i >= 0; i--) {
heapSort(array, i,size);
} } public static void sort(int[] array) {
buildSort(array,array.length);
for (int a = array.length - 1; a >= 0; a--) {
array[0] = array[a];
buildSort(array,a);
}
}}
直接插入：
package sort;import java.util.Random;//
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[100000];
Random r   = new Random();

for(int i = 0;i<array.length-1;i++){
array[i] = r.nextInt(1000000);
}
Long l1 = System.currentTimeMillis();
insertSort(array);
Long l2 = System.currentTimeMillis();
// for(int i = 0;i<array.length;i++){
// System.out.println(array[i]);
// }
System.out.println((l2-l1)+"");
}
public static void insertSort(int[] array){
for(int i = 1;i<array.length;i++){
int middle = array[i];
for(int m = i-1 ; m>=0; m-- ){

if(middle<array[m]){
array[m+1] = array[m];
//极限情况处理，有两种情况停止内层循环，一种是当遇到比自己小的东西时，一种是遍历完了数组的时候。
if(m==0){
array[m] = middle;
break;
}
}else{
array[m+1] = middle;
break;
}
}
}
}
}
现在的情况是，排序十万条数据，如果是shell排序，那么是30秒，如果是堆排序，十秒，如果是直接插入，六秒，这是为什么啊！求大神相助，找算法中的不对的地方啊啊啊啊！！！！算法

Answer 1

用java自带的比较器java.util.Comparator更简单，速度应该很快。

Answer 2

shell排序是直接插入排序写错了，应该是
while (g> m) {
if (array[g] < array[g - i]) {
int a = array[g];
array[g] = array[g - i];
array[g - i] = a;
} else {
// 这一步错误，因为步长为2的时候如果第二个大于第一个，就直接退出了，所以就完蛋了，以后的都没有排
 break;
}
g = g - i;
}看来算法我真应该好好复习一下了！！

Answer 3

希尔排序我写过一个练习从0到3000W，倒序排序，150ms左右，感觉已经比较实用了。快速排序超过10000就报内存溢出，伤不起