排序大全（java版）

排序复杂度

package paixu;

/**
 * @author mengwen E-mail: meng_wen@126.com
 * @date 创建时间：2016年12月8日 下午3:18:59
 * @version 1.0
 * @parameter
 * @since
 * @return
 */
public class Sort {
    public int[] data = new int[] {8,30,1,45,5,89,9,0,54,34,2,25,56,8,76,200,90,33,25,25,25,23,
            333,22,12,80};
    static final String result = "0,1,2,5,8,8,9,12,22,23,25,25,25,25,30,33,34,45,54,56,76,80,89,90,200,333";

    public static void main(String[] args) {
        // 冒泡排序
        bubbleSort(new Sort().data);
        // 选择排序
        selectSort(new Sort().data);
        // 优化的选择排序
        selectSort2(new Sort().data);
        // 插入排序
        InsertSort(new Sort().data);
        // 希尔排序
        shellSort(new Sort().data);
        // 快速排序
        quicksortResult(new Sort().data);
        //堆排序
        heapSort(new Sort().data);
        //桶排序  将数组分到有限数量的桶子里
        bucketSort(new Sort().data,500);
        //归并排序
        mergeSort(new Sort().data);
    }

    //---------------------------------------------------------------------------------------------------------------
    /**
     * 冒泡排序 O(N^2)
     * 冒泡排序算法的步骤：

      1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

      2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

      3.针对所有的元素重复以上的步骤，除了最后一个。

      4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     * @param data
     */
    public static void bubbleSort(int[] data) {
        int temp;
        boolean didSwap;
        for (int i = 0; i < data.length - 1; i++) {
            didSwap = false;
            for (int j = 1; j < data.length - i; j++) {
                if (data[j - 1] > data[j]) {
                    temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                    didSwap = true;
                }
            }
             if(didSwap == false)
                    break;

        }
        prints("冒泡排序结果:", data);
    }
    //---------------------------------------------------------------------------------------------------------------

    /**
     *  选择排序 O(N^2)
     *  选择排序(SelecSort)是一种简单直观的排序算法。它的工作原理如下：
     *  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
     *  然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     *  以此类推，直到所有元素均排序完毕。
     * @param data
     */
    public static void selectSort(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int k = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[k] > data[j]) {
                    k = j;
                }
            }
            if (k != i) {
                swap(data, k, i);
            }
        }
        prints("选择排序结果:", data);
    }

    //---------------------------------------------------------------------------------------------------------------
    /**
     *       选择排序的优化 O(N^2)
     *    传统的简单选择排序,每趟循环只能确定一个元素排序后的定位。
     *    我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,
     *    从而减少排序所需的循环次数。
     *    改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。
     * @param data
     */
    public static void selectSort2(int[] data) {
        int begin = 0;
        int end = data.length - 1;
        while (begin < end) {
            int min = begin;
            int max = end;
            for (int i = begin; i <= end; i++) {
                if (data[min] > data[i]) {
                    swap(data, min, i);
                }
                if (data[max] < data[i]) {
                    swap(data, max, i);
                }
            }
            ++begin;
            --end;

        }
        prints("选择排序的优化:", data);

    }
    //---------------------------------------------------------------------------------------------------------------
    /**
     * 插入排序 O(N^2)
     * 插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，
     * 直到全部插入完毕。 插入排序方法分直接插入排序和折半插入排序两种。
     * @param data
     */
    public static void InsertSort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            if (data[i - 1] > data[i]) {
                // 待排序的项
                int temp = data[i];
                // 该轮排序的最后一个元素的位置
                int end = i;
                // 如果前边的大于后边元素则交换位置，递归向前直到全部比完
                while (end > 0 && data[end - 1] > temp) {
                    data[end] = data[end - 1];
                    end--;
                }
                // 将待排序的元素插入到该位置
                data[end] = temp;
            }
        }
        prints("插入排序结果", data);
    }
    //---------------------------------------------------------------------------------------------------------------
    /** 
     *  希尔排序 当N大时，平均的时间复杂度，大约在N^1.25--1.6N^1.25之间。
     *  希尔排序（ShellSort）又称为“缩小增量排序”。该方法的基本思想是：
     *  先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，
     *  然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
     *  因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

        希尔排序是基于插入排序的以下两点性质而提出改进方法的：

       1.插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率。

       2.插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位，步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。
     * @param list
     */
    public static void shellSort(int[] list) {
        int gap = list.length / 2;
        while (1 <= gap) {
            // 把距离为 gap 的元素编为一个组，扫描所有组
            for (int i = gap; i < list.length; i++) {
                int j = 0;
                int temp = list[i];
                // 对距离为 gap 的元素组进行排序
                for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                    list[j + gap] = list[j];
                }
                list[j + gap] = temp;
            }
            System.out.format("gap = %d:\t", gap);
            gap = gap / 2; // 减小增量
        }
        prints("希尔排序结果", list);

    }
    //----------------------------------------------------------------------------------------------------------------

    // 用于输出快速排序的结果
    public static void quicksortResult(int data[]) {
        int len = data.length;
        quicksort(data, 0, len - 1);
        prints("快速排序结果", data);
    }

    /**
     * 
     * 快速排序算法的步骤：

       1.从数列中挑出一个元素，称为 "基准"，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。

       2.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

       3.递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。
       
     * 1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
     * 
     * 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
     * 
     * 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
     * 
     * 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
     * 
     * @param data
     * @param l
     * @param r
     */
    public static void quicksort(int data[], int l, int r) {
        if (l < r) {
            // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = data[l];
            while (i < j) {
                while (i < j && data[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if (i < j)
                    data[i++] = data[j];

                while (i < j && data[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if (i < j)
                    data[j--] = data[i];
            }
            data[i] = x;
            quicksort(data, l, i - 1); // 递归调用
            quicksort(data, i + 1, r);
        }
    }
    //-----------------------------------------------------------------------------------------------------
    //将元素array[k]自下往上逐步调整树形结构
     private static void adjustDownToUp(int[] array,int k,int length){
            int temp = array[k]; 
            //判断该数组最后的根节点是否有右孩子,有的话下面 2*k+1 左孩子的值要小于 length-1
            if((length-2)%2!=0){
                length =length -1;
            }
             //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
                 for(int i=2*k+1; i<length; i=2*i+1){    
                     //当末端根节点有右孩子 i这时小于 length-1,以下语句肯定会执行
                     //但如果没有右孩子，则是左孩子小于 length,当满足i=length-1 的情况是，以下语句不执行
                    if(i!=length-1 && array[i]<array[i+1]){  
                        //取节点较大的子节点的下标
                        //如果节点的右孩子>左孩子，则取右孩子节点的下标
                        i++;   
                    }
                    if(temp>=array[i]){  //根节点 >=左右子女中关键字较大者，调整结束
                        break;
                    }else{   //根节点 <左右子女中关键字较大者
                        array[k] = array[i];  //将左右子结点中较大值array[i]调整到双亲节点上
                        k = i; //【关键】修改k值，以便继续向下调整
                    }
                }
                
            
            array[k] = temp;  //被调整的结点的值放人最终位置
        }
            

     /**
      * 堆排序
      * 移除位在第一个数据的根结点，并做最大堆调整的递归运算。
      * @param list
      */
    public static void heapSort(int[] list) {

       //从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
        for(int i=(list.length-2)/2;i>=0;i--){ 
            adjustDownToUp(list, i,list.length);   
        }
        // 进行n-1次循环，完成排序

        for (int i = list.length - 1; i > 0; i--) {

            // 最后一个元素和第一元素进行交换

            int temp = list[i];

            list[i] = list[0];

            list[0] = temp;

            // 筛选 R[0] 结点，得到i-1个结点的堆

            adjustDownToUp(list, 0, i);
        }
        prints("堆排序结果",list);
    }
    //-------------------------------------------------------------------------------------------------------------
    
    /**
     * 桶排序
     * @param a
     * @param max
     */
    public static void bucketSort(int[] a, int max) {
    int[] buckets;

    if (a==null || max<1)
        return ;

    // 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
    buckets = new int[max];

    // 1. 计数
    for(int i = 0; i < a.length; i++) 
        buckets[a[i]]++; 

    // 2. 排序
    for (int i = 0, j = 0; i < max; i++) {
        while( (buckets[i]--) >0 ) {
            a[j++] = i;
        }
    }

    buckets = null;
    prints("桶排序结果", a);
}
    //------------------------------------------------------------------------------------------------------------------

    /**
     * 归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，
     * 即把待排序序列分为若干个子序列，每个子序列是有序的。
     * 然后再把有序子序列合并为整体有序序列。
     * @param data
     */
    public static void mergeSort(int[] data){
        int[] temp =new int[data.length];
        internalMergeSort(data, temp, 0, data.length-1);
        prints("归并排序结果", data);
    }
    private static void internalMergeSort(int[] a, int[] b, int left, int right){
        //当left==right的时，已经不需要再划分了
        if (left<right){
            int middle = (left+right)/2;
            internalMergeSort(a, b, left, middle);          //左子数组
            internalMergeSort(a, b, middle+1, right);       //右子数组
            mergeSortedArray(a, b, left, middle, right);    //合并两个子数组
        }
    }
    // 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
    private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
        int i=left;     
        int j=middle+1;
        int k=0;
        while ( i<=middle && j<=right){
            if (arr[i] <=arr[j]){
                temp[k++] = arr[i++];
            }
            else{
                temp[k++] = arr[j++];
            }
        }
        while (i <=middle){
            temp[k++] = arr[i++];
        }
        while ( j<=right){
            temp[k++] = arr[j++];
        }
        //把数据复制回原数组
        for (i=0; i<k; ++i){
            arr[left+i] = temp[i];
        }
    }
    //------------------------------------------------------------------------------------------------------------------
    
    //输出结果，验证正确性
    public static void prints(String str, int[] data) {
        System.out.println(str);
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < data.length; i++) {
            // System.out.print(data[i]+",");
            sb.append(data[i] + ",");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb);
        if (sb.toString().equals(result)) {
            System.out.println("和预期结果一致");
            System.out.println();
        } else {
            System.out.println("排序有误");
            System.out.println();
        }
    }
    
    /**
     * 交换data数组中下标为i和j元素的位置
     * @param data
     * @param i
     * @param j
     */
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}