编程马拉松 Day04 希尔排序、归并排序、快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static void shellSort(Integer arr[]) {
    long before = System.currentTimeMillis();
    int m = 1;
    //获取的m值，与数组长度相关
    //子数组的部分有序的程度取决于m的值，而如何选取m的值是一项数学难题，在这里我们采用`1 4 13 40 121 364`这样的序列来作为希尔排序中m的值。
    while (m < arr.length / 3) m = 3 * m + 1;//1 4 13 40 121 364...
    while (m >= 1) {//每轮循环结束时,m缩小3倍，直到收敛为1时，退化为插入排序
        for (int i = m; i < arr.length; i++) {//从m开始
            int temp = arr[i];//采用temp存放待插入元素
            int j = i;
            //取 arr[i],arr[i-m],arr[i-2m] ... 做插入排序
            while (j >= m && temp < arr[j - m]) {
                arr[j] = arr[j - m];
                j -= m;
            }
            arr[j] = temp;
        }
        m = m / 3;
    }
    long after = System.currentTimeMillis();
    System.out.println("希尔排序耗时：" + (after - before) + "ms");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public static void mergeSort(Integer arr[]) {
    long before = System.currentTimeMillis();
    mergeSort(arr, 0, arr.length - 1);
    long after = System.currentTimeMillis();
    System.out.println("归并排序耗时：" + (after - before) + "ms");
}

public static void mergeSort(Integer arr[], int low, int high) {
    if (high <= low) return;
    int mid = (low + high) / 2;
    mergeSort(arr, low, mid);//将左半部分排序
    mergeSort(arr, mid + 1, high);//将右半部分排序
    merge(arr, low, mid, high);//对左右两个有序数组进行归并操作
}

public static void merge(Integer arr[], int low, int mid, int high) {
    int i = low; //设i为左边有序数组的首索引
    int j = mid + 1;//设j为右边有序数组的首索引
    //将原数组先拷贝一份，在合并中使用
    Integer aux[] = Arrays.copyOf(arr, arr.length);
    for (int k = low; k <= high; k++) {
        //若i的索引>mid，表明左边元素均已并入新的有序数组，此时只需将右边有序数组的剩余元素并入新的有序数组
        if (i > mid) {
            arr[k] = aux[j++];
        } else if (j > high) {//若i的索引>mid，表明左边元素均已并入新的有序数组，此时只需将右边有序数组的剩余元素并入新的有序数组
            arr[k] = aux[i++];
        } else if (aux[j] < aux[i]) {//取左右有序数组中为并入新的有新数组中的的较小元素，将其并入到新的有序数组中
            arr[k] = aux[j++];
        } else {
            arr[k] = aux[i++];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static void quickSort(Integer arr[]) {
    long before = System.currentTimeMillis();
    quickSort(arr, 0, arr.length - 1);
    long after = System.currentTimeMillis();
    System.out.println("快速排序耗时：" + (after - before) + "ms");
}

public static void quickSort(Integer arr[], int low, int high) {
    if (high <= low) return;
    int j = partition(arr, low, high);//获取切分点
    quickSort(arr, low, j - 1);//对左子数组进行排序
    quickSort(arr, j + 1, high);//对右子数组进行排序
}

public static int partition(Integer arr[], int low, int high) {
    int v = arr[low];//将首元素作为参考值
    int i = low + 1;//记录当前数组的起点
    int j = high;//记录当前数组的终点
    while (true) {
        while (arr[i] <= v && i < high) {
            i++;//若arr[i]不大于v，则向后扫描
        }
        while (arr[j] >= v && j > low) {
            j--;//若arr[j]不小于v，则向前扫描
        }
        if (i >= j) break;
        swap(arr, i, j);
    }
    swap(arr, low, j);
    return j;
}