Java 与常用排序算法

Comparison

 

• 时间复杂度
• 空间复杂度

　　　　算法在计算机上所占用的存储空间，包括存储算法本身所占用的存储空间、算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

　　　　但在评估一个算法的优良性的时候，前两个基本是固定的，只有算法运行是临时占用的存储空间才会随着数据量的增大而有较大影响。因此，一般以程序运行时占用的临时存储大小作为评估指标。

　　 

快速排序 (Divide and Conquer)

    public void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int p = partition(arr, l, r);  // divide and conquer
            quickSort(arr, l, p - 1);
            quickSort(arr, p + 1, r);
        }
    }

    // select the first element as pivot
    // use do while loop
    public int partition(int[] arr, int l, int r) {
        int i, j, pivot, tmp;
        pivot = arr[l];
        i = l;
        j = r + 1;

        do {
            for (i++; i < r && arr[i] <= pivot; i++) ;// do while loop, less than or equal to pivot
            for (j--; j > l && arr[j] > pivot; j--) ;// do while loop, greater than pivot

            // swap arr i,j
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        } while (i < j);
        if (i > j) {  // cross line, swap back
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        arr[l] = arr[j];  // place the pivot to appropriate position
        arr[j] = pivot;

        return j;
    }

Best: O(nlogn); Worst: O(n^2)  Average: O(nlogn)   1.38nlogn

归并排序 (Divide and Conquer)

 　　void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);      // divide and conquer
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    void merge(int[] arr, int l, int m, int r) {
        int i, j, k, n1, n2;
        n1 = m - l + 1;   // size of the left part arr
        n2 = r - m;        // size of the right part arr

        int[] L = new int[n1];  // tmp arrays
        int[] R = new int[n2];

        // copy elements to the tmp arrays
        for (i = 0; i < n1; i++) {
            L[i] = arr[l + i];
        }
        for (j = 0; j < n2; j++) {
            R[j] = arr[m + 1 + j];
        }

        i = j = 0;
        k = l;  // point at the beginning position

        // Copy smaller elements back to arr (overwrite)
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        // copy the remaining elements
        while (i < n1) {
            arr[k++] = L[i++];
        }
        while (j < n2) {
            arr[k++] = R[j++];
        }
    }

always: O(nlogn)

堆排序 From wikipedia  (Transform and Conquer)

注意，建堆过程可能与代码中不太一样，代码中数组已存在，图示中是逐渐插入过程。

基本思想： 

　　创建堆(-->maxHeapify) --> 反复的调用del_max()函数获取最大值

　　　　排序具体过程：　　

1. 1. 建立一个堆H[0..n-1]
   2. 把堆首（最大值）和堆尾互换
   3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
   4. 重复步骤2，直到堆的尺寸为1

public class HeapSort {
    private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
    public static void main(String[] args) {
        buildMaxHeapify(sort);    // build a max heap
        heapSort(sort);             // sort the array
        print(sort);
    }

    private static void buildMaxHeapify(int[] data){
        //没有子节点的才需要创建最大堆，从最后一个的父节点开始
        int startIndex = getParentIndex(data.length - 1);
        //从尾端开始创建最大堆，每次都是正确的堆
        for (int i = startIndex; i >= 0; i--) {
            maxHeapify(data, data.length, i);
        }
    }

    /**
     * 创建最大堆
     * @param data
     * @param heapSize需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
     * @param index当前需要创建最大堆的位置
     */
    private static void maxHeapify(int[] data, int heapSize, int index){
        // 当前点与左右子节点比较
        int left = getChildLeftIndex(index);
        int right = getChildRightIndex(index);

        int largest = index;
        if (left < heapSize && data[index] < data[left]) {
            largest = left;
        }
        if (right < heapSize && data[largest] < data[right]) {
            largest = right;
        }
        //得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
        if (largest != index) {
            int temp = data[index];
            data[index] = data[largest];
            data[largest] = temp;
            maxHeapify(data, heapSize, largest);    // recursive to the root node
        }
    }

    /**
     * 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
     * @param data
     */
    private static void heapSort(int[] data) {
        //末尾与头交换，交换后调整最大堆
        for (int i = data.length - 1; i > 0; i--) {     // i--, ignore the last one element for length i
            int temp = data[0];
            data[0] = data[i];      // put it to the end
            data[i] = temp;
            maxHeapify(data, i, 0);
        }
    }

    /**
     * 父节点位置
     * @param current
     * @return
     */
    private static int getParentIndex(int current){
        return (current - 1) >> 1;         // shift one bit to the right, equals to (current -1) / 2
    }

    /**
     * 左子节点position注意括号，加法优先级更高
     * @param current
     * @return
     */
    private static int getChildLeftIndex(int current){
        return (current << 1) + 1;
    }

    /**
     * 右子节点position
     * @param current
     * @return
     */
    private static int getChildRightIndex(int current){
        return (current << 1) + 2;
    }

    private static void print(int[] data){
        int pre = -2;
        for (int i = 0; i < data.length; i++) {
            if (pre < (int)getLog(i+1)) {
                pre = (int)getLog(i+1);
                System.out.println();
            }
            System.out.print(data[i] + " |");
        }
    }

    /**
     * 以2为底的对数
     * @param param
     * @return
     */
    private static double getLog(double param){
        return Math.log(param)/Math.log(2);
    }
}

avg: O(nlogn)  <= 2nlogn   在随机文件上时间测试的结果显示heapsort比快速排序要慢，但是可以比得上mergeSort. (来源于算法设计与分析基础 2rd Edition P228)

选择排序

    void selectSort(int[] arr){
        int min;
        for(int i = 0;i<arr.length-1;i++){
            min = i;
            for(int j=i;j<arr.length;j++){
                if(arr[min] > arr[j]){         // find the smallest elements
                    min = j;
                }
            }
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }

Best: O(n^2); Worst: O(n^2) Average: O(n^2)

冒泡排序

    void bubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j = arr.length-1; j > i; j--){
                if(arr[j] < arr[j-1]){    // find the smallest through bubble
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
    }

Best: O(n^2); Worst: O(n^2) Average: O(n^2)

此代码实现的最佳时间消耗 O(n^2), 若要使最佳情况时间开销达到O(n)，可以设置一个sentinel实现：当不发生交换的时候就break退出，完成了排序。

插入排序

    void insertSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }

        int i, j;
        int temp;
        for (i = 1; i < arr.length; i++) {
            temp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {  // in-place
                arr[j + 1] = arr[j];    // shift
            }
            arr[j + 1] = temp;
        }
    }

Best: O(n); Worst: O(n^2) Average: O(n^2)

Java工具类排序 

java.util.Arrays.sort(arr);

•  The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. 比上面的快速排序更快。

计算Java程序运行时间：

long startTime = System.nanoTime();
//code
long endTime = System.nanoTime();
System.out.println("Took "+(endTime - startTime) + " ns"); 

 Test It:

public static void main(String[] args) {
        int arr[] = {1, 3, 1, 8, 4, 8,3,23,2};
        Main main = new Main();
        long startTime = System.nanoTime();
//        main.quickSort(arr, 0, arr.length - 1);
//        main.selectSort(arr);
//        main.insertSort(arr);
//        main.bubbleSort(arr);

//code
        long endTime = System.nanoTime();
        System.out.println("Took "+(endTime - startTime) + " ns");
        for (int a : arr) {
            System.out.println(a);
        }
    }