当前位置: 代码迷 >> Java相关 >> 小弟实践证明 各种排序算法(快速,堆,希尔,合并)还是快速排序最快,该怎么处理
  详细解决方案

小弟实践证明 各种排序算法(快速,堆,希尔,合并)还是快速排序最快,该怎么处理

热度:2877   发布时间:2013-02-25 21:47:48.0
小弟实践证明 各种排序算法(快速,堆,希尔,合并)还是快速排序最快
小弟不才 自己写的几种排序算法如下 不知道哪里可以改进 求算法大侠指点指点

Java code
package com.algorithm;import java.util.Arrays;public class SortRunner {    public static void main(String args[]) {        // int data[] = new int[] { 12, 5, 9, 8, 16, 3, 1, 7, 4, 0, 11, 2,        // 19,        // 14, 13, 15, 6, 18, 20, 17, 10 };        long baseSize = 1000000L;        int n = (int) (Math.random() * baseSize);        int[] data = new int[n];        for (int i = 0; i < n; i++) {            data[i] = (int) (Math.random() * baseSize);        }        int[] commonData = data.clone();        long commonBefore = System.currentTimeMillis();        // commonSort(commonData);        long commonAfter = System.currentTimeMillis();        System.out.println("CommonSort " + (commonAfter - commonBefore));        int[] quickData = data.clone();        long quickBefore = System.currentTimeMillis();        quickSort(quickData, 0, quickData.length - 1);        long quickAfter = System.currentTimeMillis();        System.out.println("QuickSort " + (quickAfter - quickBefore));        int[] shellData = data.clone();        long shellBefore = System.currentTimeMillis();        shellSort(shellData);        long shellAfter = System.currentTimeMillis();        System.out.println("ShellSort " + (shellAfter - shellBefore));        int[] mergeData = data.clone();        long mergeBefore = System.currentTimeMillis();        mergeSort(mergeData, 0, mergeData.length - 1);        long mergeAfter = System.currentTimeMillis();        System.out.println("MergeSort " + (mergeAfter - mergeBefore));        int[] heapData = data.clone();        long heapBefore = System.currentTimeMillis();        heapSort(heapData);        long heapAfter = System.currentTimeMillis();        System.out.println("HeapSort " + (heapAfter - heapBefore));        System.out.println();        // print(data);        // print(commonData);        // print(quickData);        // print(shellData);        // print(mergeData);        // print(heapData);    }    /**     * 冒泡排序     */    public static void commonSort(int[] data) {        for (int i = 0; i < data.length; i++) {            for (int j = 0; j < i; j++) {                if (data[j] > data[i]) {                    int temp = data[j];                    data[j] = data[i];                    data[i] = temp;                }            }        }    }    /**     * 快速排序     */    public static void quickSort(int[] data, int left, int right) {        if (left >= right) {            return;        }        int n = data[left];        int l = left;        int r = right;        while (l < r) {            while (data[r] >= n && l < r) {                --r;            }            data[l] = data[r];            while (data[l] <= n && l < r) {                ++l;            }            data[r] = data[l];        }        data[r] = n;        quickSort(data, left, r - 1);        quickSort(data, r + 1, right);    }    /**     * 希尔排序     */    public static void shellSort(int[] data) {        int length = data.length;        int n = length;        while ((n = n / 2) >= 1) {            for (int i = 0; i < n; i++) {                for (int j = i; j < length; j += n) {                    int k = j;                    while (k >= 0 && k + n < length && data[k] > data[k + n]) {                        int temp = data[k + n];                        data[k + n] = data[k];                        data[k] = temp;                        k -= n;                    }                }            }        }    }    /**     * 合并排序     */    public static void mergeSort(int[] data, int left, int right) {        if (left >= right) {            return;        }        int middle = (left + right) / 2;        mergeSort(data, left, middle);        mergeSort(data, middle + 1, right);        int[] temp = new int[right - left + 1];        int i = left;        int j = middle + 1;        int k = 0;        while (k <= right) {            if (i > middle) {                while (j <= right) {                    temp[k++] = data[j++];                }                break;            } else if (j > right) {                while (i <= middle) {                    temp[k++] = data[i++];                }                break;            }            if (data[i] < data[j]) {                temp[k++] = data[i++];            } else {                temp[k++] = data[j++];            }        }        k = 0;        for (i = left; i <= right; i++) {            data[i] = temp[k++];        }    }    /**     * 堆排序     */    public static void heapSort(int[] data) {        int length = data.length;        // 建堆        for (int i = length / 2 - 1; i >= 0; i--) {            adjustHeap(i, data, length);        }        for (int i = length - 1; i >= 0; i--) {            int temp = data[0];            data[0] = data[i];            data[i] = temp;            adjustHeap(0, data, i);        }    }    private static void adjustHeap(int parent, int[] data, int length) {        int left = parent * 2 + 1;        int right = left + 1;        int max_index = parent;        if (left < length && data[left] > data[max_index]) {            max_index = left;        }        if (right < length && data[right] > data[max_index]) {            max_index = right;        }        if (max_index != parent) {            int temp = data[parent];            data[parent] = data[max_index];            data[max_index] = temp;            adjustHeap(max_index, data, length);        }    }    public static void print(int[] data, int left, int right) {        for (int i = left; i <= right; i++) {            System.out.print(data[i] + " ");        }        int[] array = new int[] { 1, 2, 3, 4 };        Arrays.sort(array);        System.out.println();    }    public static void print(int[] data) {        for (int i = 0; i < data.length; i++) {            System.out.print(data[i] + " ");        }        System.out.println();    }}
  相关解决方案