四大排序

下面为工具方法，已封装成工具类，有兴趣的同学，可以复制过去，以备调用。

 

package org.tarena.liyunhua.utils;

import java.util.Arrays;
import java.util.Random;

public class SortUtil {
    /**
     * 冒泡排序,param参数，asc为升序，desc为降序
     * 
     * @param arr
     * @param param
     * @return
     */
    public static int[] maopao(int[] arr, String param) {
        int t;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1-i; j++) {
                if (param.equals("asc")) {
                    if (arr[j + 1] < arr[j]) {
                        t = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = t;
                    }
                } else if (param.equals("desc")) {
                    if (arr[j] < arr[j + 1]) {
                        t = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = t;
                    }
                }

            }
        }
        return arr;
    }

    /**
     * 冒泡排序,默认asc方式排序
     * 基本思路：相邻两个数，比较大小，升序，大的交换位置下沉。降序，小的交换位置也往下沉.
     * @param arr
     * @return
     */
    public static int[] maopao(int[] arr) {
        int t;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1-i; j++) {
                if (arr[j + 1] < arr[j]) {
                    t = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = t;
                }

            }
        }
        return arr;
    }

    /**
     * 插入排序，param参数，asc为升序，desc为降序
     */
    public static int[] insertSort(int[] arr, String param) {
        for (int i = 1; i < arr.length; i++) {
            int k = arr[i];
            int j;
            if ("asc".equals(param.toLowerCase())) {
                for (j = i - 1; j >= 0 && k < arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = k;
            } else if ("desc".equals(param.toLowerCase())) {
                for (j = i - 1; j >= 0 && k > arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = k;
            }

        }
        return arr;
    }
    
    /**
     * 插入排序,默认asc排序

    *基本思路:将要排序的数组分成两部分，每次从后面的数组部分中取出索引最小的数组元素，
    *插入到前面数组部分的适当位置中。通常用在开始排序时，将数组的第一个
    *元素作为一组，后面的所有元素被当成另一组。
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int k = arr[i];
            int j;
            for (j = i - 1; j >= 0 && k < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = k;
        }
        return arr;
    }

    /**
     * 选择排序 ,默认升序

    *基本思路:将要排序的数组分成两部分，一部分是从小到大已经排序好的，一部是无序的，
    *从无序的部分取出最小的数组，放到已经排好序的部分的最后。
     * @param args
     */
    public static int[] xuanze(int[] arr){
        int t;
        for(int i=0;i<arr.length;i++){
            int m=i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[m]){
                    m=j;
                }
            }
            if(i!=m){
                t=arr[i];
                arr[i]=arr[m];
                arr[m]=t;
            }
        }
        return arr;
    }

    /**
     * 选择排序 ,param参数，asc为升序，desc为降序
     * @param args
     */
    public static int[] xuanze(int[] arr,String param){
        int t;
        for(int i=0;i<arr.length;i++){
            int m=i;
            for(int j=i+1;j<arr.length;j++){
                if("asc".equals(param.toLowerCase())){
                    if(arr[j]<arr[m]){
                        m=j;
                    }
                }else if("desc".equals(param.toLowerCase())){
                    if(arr[j]>arr[m]){
                        m=j;
                    }
                }
                
            }
            if(i!=m){
                t=arr[i];
                arr[i]=arr[m];
                arr[m]=t;
            }
        }
        return arr;
    }

    /**
     * 产生一个length长度的随机数组,方法
     * @param length
     * @return
     */
    public static int[] randomArrays(int length){
        int[] arr = new int[length];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=new Random().nextInt(8888);
        }
        return arr;
    }

 

//快速排序,基本思路:将一个大的数组的排序问题，分解成2个小的数组的排序，而每个小的数组的排序，
//又可继续分解成更小的2个数组，这样一直递归分解下去，直到数组的大小最大为2。

 

//下面是用main进行测试
    public static void main(String[] args) {
        
        int[] arr=SortUtil.randomArrays(8888);
        //选择排序
        //System.out.println("选择排序随机数组为: "+Arrays.toString(arr));
        System.out.println("----------选择排序 开始----------");
        long start=System.currentTimeMillis();
        SortUtil.xuanze(arr);
        //System.out.println(Arrays.toString(arr));
        System.out.println("选择排序用时      "+(System.currentTimeMillis()-start)+"  毫秒");
        System.out.println("----------选择排序 结束----------");
        
        arr=SortUtil.randomArrays(8888);
        //插入排序
        //System.out.println("插入排序随机数组为: "+Arrays.toString(arr));
        System.out.println("----------插入排序 开始----------");
        start=System.currentTimeMillis();
        SortUtil.insertSort(arr);
        //System.out.println(Arrays.toString(arr));
        System.out.println("插入排序用时      "+(System.currentTimeMillis()-start)+"  毫秒");
        System.out.println("----------插入排序 结束----------");
        
        
        arr=SortUtil.randomArrays(8888);
        // 冒泡排序
        //System.out.println("冒泡排序随机数组为: "+Arrays.toString(arr));
        System.out.println("----------冒泡排序开始----------");
        start=System.currentTimeMillis();
        SortUtil.maopao(arr);
        //System.out.println(Arrays.toString(arr));
        System.out.println("冒泡排序 用时      "+(System.currentTimeMillis()-start)+"  毫秒");
        System.out.println("----------冒泡排序 结束----------");
        
        arr=SortUtil.randomArrays(8888);
        // 快速排序(Arrays.sort)
        //System.out.println("快速排序随机数组为: "+Arrays.toString(arr));
        System.out.println("----------快速排序 开始----------");
        start=System.currentTimeMillis();
        Arrays.sort(arr);
        //System.out.println(Arrays.toString(arr));
        System.out.println("快速排序 用时      "+(System.currentTimeMillis()-start)+"  毫秒");
        System.out.println("----------快速排序 结束----------");
    }
}

随机产生8888位数组，下面为测试结果

----------选择排序 开始----------
选择排序用时      94  毫秒
----------选择排序 结束----------

----------插入排序 开始----------
插入排序用时      47  毫秒
----------插入排序 结束----------

----------冒泡排序开始----------
冒泡排序 用时      203  毫秒
----------冒泡排序 结束----------

----------快速排序 开始----------
快速排序 用时      16  毫秒
----------快速排序 结束----------

总结:

快速排序，16毫秒，当之无愧第一名

插入排序，47毫秒 ，    排在第二名

选择排序，94毫秒，     排在第三名

冒泡排序，203毫秒，远远落最后名