数组各种排序算法和复杂度分析

/*
 * Copyright (c) 2005-2015 XXX Corporation. All rights reserved.
 *
 * Project Name: test
 * File Name:    SortTest.java
 * Package Name: XXX
 * date:         2016年7月28日
 *
 */
package dt;
import java.util.Arrays;
/**
 * ClassName:   SortTest <br/>
 * Description: TODO ADD DESCRIPTION. <br/>
 * date:        2016年7月28日 上午8:25:39 <br/>
 *
 * @author      danier
 */
public class SortTest {
    static int[] a = { 5,17,16, 7,10, 9, 18,4,15,14, 3, 1, 19,0, 20,6,13, 2, 12,8,11 };
    /**
     * main: ADD DESCRIPTION. <br/>
     * 执行流程: (可选). <br/>
     * 使用方法: (可选). <br/>
     * 注意事项: (可选). <br/>
     *
     * @author danier
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        long begin = System.currentTimeMillis();
        SortTest st = new SortTest();
        st.bubbleSort();
        st.selectSort();
        st.insertSort();
        st.halfInsertSort();
        st.hillsort();
        st.mergeSort(0, a.length - 1);
        st.quickSort(0, a.length - 1);
        long over = System.currentTimeMillis();
        System.out.println("使用的时间为：" + (over - begin) + "毫秒");
        System.out.print(Arrays.toString(st.a));
    }
    //    复杂度分析：一共要比较 ((n-1)+(n-2)+...+3+2+1)=n*(n-1)/2次，所以时间复杂度是O(n^2)
    //    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，
    //    交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；
    //    如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，
    //    所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
    public void bubbleSort() {
        for (int i = a.length - 1; i > 1; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) swap(j, j + 1);
            }
        }
    }
 
    //    选择排序是不稳定算法，最好的情是已经排好顺序，只要比较n*(n-1)/2次即可，
    //    最坏情况是逆序排好的，那么还要移动O(n)次,由于是低阶故而不考虑不难得出选择排序的时间复杂度是O(n^2)
    //    比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
    public void selectSort() {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) min = j;
            }
            swap(i, min);
        }
    }
    //    插入排序的思想是这样的，第一层for循环表示要循环n次，且每次循环要操作的主体是a[i]，第二层循环是对
    //    a[i]的具体操作，是从原数祖第i个位置起，向前比较，所以插入排序的平均时间复杂度也是O(n^2).
    //    比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，
    //    如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，
    //    那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，
    //    从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
    void insertSort() {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i], j = i;
            while (j > 0 && a[j - 1] > temp) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }
    }
 

    //    1)        最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
    //    2)        最坏情况：O(nlog2n)。
    //    3)        渐进时间复杂度（平均时间复杂度）：O(nlog2n)
    //    希尔排序是不稳定的。因为在进行分组时，相同元素可能分到不同组中，改变相同元素的相对顺序
    public void hillsort() {
        int h = 1;
        while (h < a.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int i = 1; i < a.length; i++) {
                int temp = a[i], j = i;
                while (j > h - 1 && a[j - h] > temp) {
                    a[j] = a[j - h];
                    j -= h;
                }
                a[j] = temp;
            }
            h = (h - 1) / 3;
        }
    }

//    二分查找排序是稳定的，不会改变相同元素的相对顺序， 
    //    1. 时间复杂度：O(n^2)
    //    二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
    //    二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
    //    所以，二分查找排序比较次数为：x=log2n
    //    二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：
    //    1)        最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n  。即O(log2n)
    //    2)        最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)
    //    3)        渐进时间复杂度（平均时间复杂度）：O(n^2)
    void halfInsertSort() {
        for (int i = 1; i < a.length; i++) {
            if (a[i] > a[i - 1]) {
                continue;
            }
            int temp = a[i], left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (a[mid] > temp)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            for (int j = i; j > left; j--) {
                a[j] = a[j - 1];
            }
            a[left] = temp;
        }
    }
   

   public void mergeSort(int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, mid + 1, right);
   }
   private void merge(int lb, int le, int rb, int re) {
        int[] temp = new int[a.length];
        int leftbegin = lb;
        int index = lb;
        while (lb <= le && rb <= re) {
            if (a[lb] < a[rb])
                temp[index++] = a[lb++];
            else
                temp[index++] = a[rb++];
        }
        while (lb <= le) {
            temp[index++] = a[lb++];
        }
        while (rb <= re) {
            temp[index++] = a[rb++];
        }
       
        while (leftbegin <= re) {
            a[leftbegin] = temp[leftbegin];
            leftbegin++;
        }
    }