java快速排序和合并排序简单性能对比

 

结果：

2097151

合并排序执行时间：443

合并排序递归树深度：4194301

快速排序执行时间：207

快速排序递归树深度：2795757

 

 

package com.zte.it.study.sort;

 

import java.util.Arrays;

 

/**

 * 类名: 排序算法比较 <br/>

 * 功能: TODO ADD FUNCTION. <br/>

 * 时间：2015-3-6 下午6:55:52

 * 

 * @author 10156351

 * @version

 * @since JDK 1.6

 */

public class 排序算法比较

{

    static int recursive = 0;

 

    /**

     * main:(这里用一句话描述这个方法的作用). <br/>

     * 

     * @author 10156351

     * @param args

     * @since JDK 1.6

     */

    public static void main(String[] args)

    {

        int num = Integer.MAX_VALUE >> 10;

        System.out.println(num);

        int[] array = new int[num];

        int[] array2 = new int[num];

        int[] array3 = new int[num];

        int[] array4 = new int[num];

        for (int i = 0; i < num; i++)

        {

            array[i] = (int) (Math.random() * Integer.MAX_VALUE);

            array2[i] = array[i];

            array3[i] = array[i];

            array4[i] = array[i];

        }

        long startTime = System.currentTimeMillis();

        recursive = 0;

        mergeSort(array);

        System.out.println("合并排序执行时间：" + (System.currentTimeMillis() - startTime));

        System.out.println("合并排序递归树深度：" + recursive);

 

        //

        startTime = System.currentTimeMillis();

        recursive = 0;

        quicksort(array2, 0, num - 1);

        System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));

        System.out.println("快速排序递归树深度：" + recursive);

 

        // startTime = System.currentTimeMillis();

        // recursive = 0;

        // quickSort2(array3, 0, num - 1);

        // System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));

        // System.out.println("快速排序递归树深度：" + recursive);

        //

        // startTime = System.currentTimeMillis();

        // recursive = 0;

        // quickSort3(array4, 0, num - 1);

        // System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));

        // System.out.println("快速排序递归树深度：" + recursive);

 

//        for (int i = 0; i < num / 1024; i++)

//        {

//            System.out.print(array2[i] + "    ");

//            if (i % 20 == 19)

//                System.out.println(array2[i]);

//        }

    }

 

    public static void quicksort(int[] v, int left, int right)

    {

        recursive++;

        if (left < right)

        {

            int key = v[left];

            int low = left;

            int high = right;

            while (low < high)

            {

                while (low < high && v[high] > key)

                {

                    high--;

                }

                if (low < high)

                {

                    v[low] = v[high];

                    low++;

                }

 

                while (low < high && v[low] < key)

                {

                    low++;

                }

                if (low < high)

                {

                    v[high] = v[low];

                    high--;

                }

            }

            v[low] = key;

            quicksort(v, left, low - 1);

            quicksort(v, low + 1, right);

        }

    }

 

    public static int[] quickSort2(int[] targetArr, int start, int end)

    {

        recursive++;

        int i = start + 1, j = end;

        int key = targetArr[start];

        if (start >= end)

            return targetArr;

 

        /*

         * 从i++和j--两个方向搜索不满足条件的值并交换

         * 

         * 条件为：i++方向小于key，j--方向大于key

         */

        while (true)

        {

            while (targetArr[j] > key)

                j--;

            while (targetArr[i] < key && i < j)

                i++;

            if (i >= j)

                break;

            swap(targetArr, i, j);

            if (targetArr[i] == key)

            {

                j--;

            }

            else

            {

                i++;

            }

        }

 

        /* 关键数据放到‘中间’ */

        swap(targetArr, start, j);

 

        if (start < i - 1)

        {

            quickSort2(targetArr, start, i - 1);

        }

        if (j + 1 < end)

        {

            quickSort2(targetArr, j + 1, end);

        }

 

        return targetArr;

    }

 

    public static void quickSort3(int[] targetArr, int start, int end)

    {

        recursive++;

        int i = start, j = end;

        int key = targetArr[start];

 

        while (i < j)

        {

            /* 按j--方向遍历目标数组，直到比key小的值为止 */

            while (j > i && targetArr[j] >= key)

            {

                j--;

            }

            if (i < j)

            {

                /* targetArr[i]已经保存在key中，可将后面的数填入 */

                targetArr[i] = targetArr[j];

            }

            /* 按i++方向遍历目标数组，直到比key大的值为止 */

            while (i < j && targetArr[i] <= key)

            /* 此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。 */

            {

                i++;

            }

            if (i < j)

            {

                /* targetArr[j]已保存在targetArr[i]中，可将前面的值填入 */

                targetArr[j] = targetArr[i];

            }

        }

        /* 此时i==j */

        targetArr[i] = key;

 

        if (i - start > 1)

        {

            /* 递归调用，把key前面的完成排序 */

            quickSort3(targetArr, start, i - 1);

        }

        if (end - j > 1)

        {

            /* 递归调用，把key后面的完成排序 */

            quickSort3(targetArr, j + 1, end);

        }

    }

 

    public static void swap(int[] arr, int start, int end)

    {

        int tmp = arr[start];

        arr[start] = arr[end];

        arr[end] = tmp;

    }

 

    public static void mergeSort(int[] array)

    {

        recursive++;

        int length = array.length;

        int middle = length / 2;

 

        if (length > 1)

        {

 

            int[] left = Arrays.copyOfRange(array, 0, middle);// 拷贝数组array的左半部分

            int[] right = Arrays.copyOfRange(array, middle, length);// 拷贝数组array的右半部分

            mergeSort(left);// 递归array的左半部分

            mergeSort(right);// 递归array的右半部分

            merge(array, left, right);// 数组左半部分、右半部分合并到Array

        }

    }

 

    // 合并数组，升序

    private static void merge(int[] result, int[] left, int[] right)

    {

 

        int i = 0, l = 0, r = 0;

 

        while (l < left.length && r < right.length)

        {

 

            if (left[l] < right[r])

            {

                result[i] = left[l];

                i++;

                l++;

            }

            else

            {

                result[i] = right[r];

                i++;

                r++;

            }

        }

 

        while (r < right.length)

        {// 如果右边剩下合并右边的

            result[i] = right[r];

            r++;

            i++;

        }

 

        while (l < left.length)

        {

            result[i] = left[l];

            l++;

            i++;

        }

    }

}