欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

冒泡、归并和快速的算法试验

程序员文章站 2022-06-22 12:54:57
1. 冒泡、归并和快速的算法试验 1.1. 冒泡排序 / 冒泡排序 / private void bubbleSort(int[] arr) { for (int i = arr.length; i 0; i ) { for (int j = arr.length 1; j arr.length i ......

1. 冒泡、归并和快速的算法试验

1.1. 冒泡排序

/**
 * 冒泡排序
 */
private void bubblesort(int[] arr) {
    for (int i = arr.length; i > 0; i--) {
        for (int j = arr.length - 1; j > arr.length - i; j--) {
            if (arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
}

1.2. 快速排序

 /**
 * 快速排序
 */
private void qsort(int[] arr, int head, int tail) {
    if (arr == null || head >= tail || arr.length == 0) {
        return;
    }
    int i = head, j = tail, q = arr[(i + j) / 2];

    while (i < j) {
        while (arr[i] < q) {
            ++i;
        }

        while (arr[j] > q) {
            --j;
        }

        if (i < j) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            ++i;
            --j;
        } else if (i == j) {
            ++i;
        }
    }

    qsort(arr, head, j);
    qsort(arr, i, tail);

}

1.3. 归并排序

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

1.4. 测试代码

@test
public void testspeed(){
    random random = new random();
    int arrs[] = new int[30000];
    for (int i = 0; i < arrs.length; i++) {
        arrs[i] = random.nextint(10000);
    }

    int[] arrs2 = arrs.clone();
    int[] arrs3 = arrs.clone();
    int[] arrs4 = arrs.clone();

    long start = system.currenttimemillis();
    bubblesort(arrs);

    long end1 = system.currenttimemillis();
    log.info("冒泡排序 time:{}ms",(end1-start));

    qsort(arrs2,0,arrs2.length-1);
    long end2 = system.currenttimemillis();
    log.info("快速排序 time:{}ms",(end2-end1));

    merge_sort(arrs3);
    long end3 = system.currenttimemillis();
    log.info("归并排序 time:{}ms",(end3-end2));

    arrays.sort(arrs4);
    long end4 = system.currenttimemillis();
    log.info("java.util排序 time:{}ms",(end4-end3));
}

1.5. 测试结果

  1. 当数组长度60000时
15:35:28.609 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:8497ms
15:35:28.645 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:40ms
15:35:28.669 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:24ms
15:35:28.696 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:27ms
  1. 当数组长度30000时
15:34:48.389 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:2727ms
15:34:48.403 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:18ms
15:34:48.418 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:15ms
15:34:48.428 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:10ms
  1. 当数组长度3000时
15:33:52.156 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:22ms
15:33:52.167 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:21ms
15:33:52.171 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:4ms
15:33:52.183 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:12ms
  1. 当数组长度300时
15:33:34.345 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:3ms
15:33:34.356 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:17ms
15:33:34.357 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:1ms
15:33:34.357 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:0ms
  1. 当数组长度30时
15:33:07.920 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:0ms
15:33:07.933 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:21ms
15:33:07.933 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:0ms
15:33:07.934 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:1ms

1.6. 总结

  1. 我的测试有什么变量控制问题可以提出来
  2. 冒泡排序的时间复杂度最好是o(n),平均和最差o(n^2);快速排序最好nlog_2 n,平均也是nlog_2 n,最差n^2;归并排序最好平均和最差都是nlog_2 n。根据算法时间复杂度看,归并排序最稳定
  3. 根据实验结果看,在排序数量比较少的情况下冒泡排序效率也还可以,但一旦排序数量多了,还是快速和归并效率较高。当然我们往往就用java默认提供给我们的工具类就可以了,不用自己写算法,效率不比归并差。