本文共 10198 字，大约阅读时间需要 33 分钟。

快速排序o(nlogn)

平均时间复杂度o（nlogn），最坏情况下的时间复杂度o（n^2）。

是冒泡排序的改进版，它的每一趟都定位一个基准元素，基准元素的左边的所有元素都比基准元素小，基准元素的右边的所有的元素都比基准元素大。然后对左右两边的元素接着进行递归操作，知道所有的元素都有序。

package com.lhh;import java.util.Arrays;public class QuickSort {
       public static void main(String[] args) {
           int[] arr = {
   49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};        int low = 0;        int high = arr.length - 1;        quickSort(arr, low, high);        System.out.println(Arrays.toString(arr));    }    private static void quickSort(int[] arr, int low, int high) {
           //1.递归结束条件        if (low >= high) {
               return;        }        //2.找到索引函数        int index = getIndex(arr, low, high);        //3.递归的过程        //基准元素的左半部分        quickSort(arr, low, index - 1);        //基准元素的右半部分        quickSort(arr, index + 1, high);    }    private static int getIndex(int[] arr, int low, int high) {
           //首先定义基准元素为low位置的元素        int baseNumber = arr[low];        while (low < high) {
               while (low < high && arr[high] >= baseNumber) {
                   high--;            }            //如果跳出了这个while循环，那么就代表high指向的元素小于基准元素，把该元素放到low位置            arr[low] = arr[high];            while (low < high && arr[low] <= baseNumber) {
                   low++;            }            //如果跳出了这个while循环，那么就代表low指向的元素大于基准元素，把该元素放到high位置            arr[high] = arr[low];        }        //跳出循环时，low和high是相等的，此时候low和high所指向的位置就是真正的基准位置,把baseNumber赋值过去，并且返回位置        arr[high] = baseNumber;        return high;    }}

快速排序测试:

//生成随机数，Math.random随机生成从0到1的小数        int []arr2 = new int [8000000];        for(int i=0;i<8000000;i++){
               arr2[i]=(int)(Math.random()*8000000);        }        int low = 0;        int high = arr2.length - 1;        Date date = new Date();        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat = simpleDateFormat.format(date);        System.out.println("排序前的时间");        System.out.println(dateFormat);        quickSort(arr2,low,high);//调用冒泡排序        Date date2 = new Date();        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat2 = simpleDateFormat.format(date2);        System.out.println("排序后的时间");        System.out.println(dateFormat2);

归并排序o（nlogn）

package com.lhh;import java.util.Arrays;public class MergeSort {
       public static void main(String[] args) {
           //int[] arr = {3, 89, 12, 2, 34, 46, 7, 9, 32, -8, 45};        int[] arr = {
   89, 3};        int[] temp = new int[arr.length];        int left = 0;        int right = arr.length - 1;        mergeSort(arr, left, right, temp);        System.out.println(Arrays.toString(arr));    }    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
           if (left >= right) {
               //递归结束            return;        }        int mid = (left + right) / 2;        //递归左半部分（分）        mergeSort(arr, left, mid, temp);        //递归右半部分(分)        mergeSort(arr, mid + 1, right, temp);        //治        merge(arr, left, mid, right, temp);    }    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
           int i = left;//定义左半端第一个元素的位置        int j = mid + 1;//定义右半段第一个数据元素的位置        int k = 0;//记录临时数组的下标，每次有一个元素加进去，那么需要将其加一        //首先将合并的两端的元素加到临时数组当中,直到遇到一方数据到底末尾结束while循环        while (i <= mid && j <= right) {
               if (arr[i] < arr[j]) {
                   //前段元素大于后段元素，把前段元素加入到临时数组当中                temp[k] = arr[i];                i++;            } else {
                   temp[k] = arr[j];                j++;            }            k++;        }        //弥补长短不一的情况，有可能前半段数据长，也有可能后半段数据长        //出现这样的情况，需要将还剩下的那些元素直接复制到临时数组当中即可        while (i <= mid) {
               //说明后半段元素长度较短，前半段还剩下一些数据            temp[k] = arr[i];            k++;            i++;        }        while (j <= right) {
               //说明前半段元素长度较短，后半段还剩下一些数据            temp[k] = arr[j];            k++;            j++;        }        //把temp数组中的数据再次复制到原数组当中。        k = 0;//重新让k回到起始位置        while (left <= right) {
               arr[left] = temp[k];            k++;            left++;        }    }}

测试归并排序:

//生成随机数，Math.random随机生成从0到1的小数        int []arr2 = new int [8000000];        for(int i=0;i<8000000;i++){
               arr2[i]=(int)(Math.random()*8000000);        }        int[] temp = new int[arr2.length];        int left = 0;        int right = arr2.length - 1;        Date date = new Date();        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat = simpleDateFormat.format(date);        System.out.println("排序前的时间");        System.out.println(dateFormat);        mergeSort(arr2, left, right, temp);        Date date2 = new Date();        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat2 = simpleDateFormat.format(date2);        System.out.println("排序后的时间");        System.out.println(dateFormat2);

桶排序(以空间换时间的经典排序)

桶排序过程图解:

public static void radixSort(int[] arr) {
           //针对各位进行排序处理        //以空间换时间的排序算法，因为二维数组里面的每一个一维数组的长度的都设置为了arr.length。以防止所有的        //位数都放在同一个桶里面的情况。        int[][] bucket = new int[10][arr.length];        //为了记录每一个桶里面存放的数据的个数，比如bucketElementCount[0]=1表示第一个桶有一个数据。        int[] bucketElementCount = new int[10];//总共十个桶，每个桶记录存放的数据的个数 //根据个位进行排序,放入到对应的桶当中        for (int i = 0; i < arr.length; i++) {
               int gewei = arr[i] % 10;            bucket[gewei][bucketElementCount[gewei]] = arr[i];            bucketElementCount[gewei]++;//把放到桶里面的数据的个数加一。        }        int index = 0;        //取出按照个位排好序放入到桶中的元素，并且重新放入到arr数组当中。        for (int i = 0; i < bucket.length; i++) {
               if (bucketElementCount[i] > 0) {
                   //代表该桶里面有数据，遍历一下，把所有的数据取出来                for (int k = 0; k < bucketElementCount[i]; k++) {
                       arr[index++] = bucket[i][k];//放到了arr中后要让index+1，为了存放下一个数据。                }            }            //！！！！清空每一桶当中所存放的数据的个数，为了进行百位排序的时候的操作。            bucketElementCount[i] = 0;        }        System.out.println("第一轮的桶排序的结果:" + Arrays.toString(arr));        //***************************************        //根据百位进行排序,放入到对应的桶当中        for (int i = 0; i < arr.length; i++) {
               int shiwei = arr[i] / 10 % 10;//获得百位数据            bucket[shiwei][bucketElementCount[shiwei]] = arr[i];            bucketElementCount[shiwei]++;//把放到桶里面的数据的个数加一。        }        index = 0;        //取出按照个位排好序放入到桶中的元素，并且重新放入到arr数组当中。        for (int i = 0; i < bucket.length; i++) {
               if (bucketElementCount[i] > 0) {
                   //代表该桶里面有数据，遍历一下，把所有的数据取出来                for (int k = 0; k < bucketElementCount[i]; k++) {
                       arr[index++] = bucket[i][k];//放到了arr中后要让index+1，为了存放下一个数据。                }            }            //！！！！清空每一桶当中所存放的数据的个数，为了进行百位排序的时候的操作。            bucketElementCount[i] = 0;        }        System.out.println("第二轮的桶排序的结果:" + Arrays.toString(arr));        ///**********************************************        //根据百位进行排序,放入到对应的桶当中        for (int i = 0; i < arr.length; i++) {
               int baiwei = arr[i] / 100 % 10;//获得百位数据            bucket[baiwei][bucketElementCount[baiwei]] = arr[i];            bucketElementCount[baiwei]++;//把放到桶里面的数据的个数加一。        }        index = 0;        //取出按照个位排好序放入到桶中的元素，并且重新放入到arr数组当中。        for (int i = 0; i < bucket.length; i++) {
               if (bucketElementCount[i] > 0) {
                   //代表该桶里面有数据，遍历一下，把所有的数据取出来                for (int k = 0; k < bucketElementCount[i]; k++) {
                       arr[index++] = bucket[i][k];//放到了arr中后要让index+1，为了存放下一个数据。                }            }            //！！！！清空每一桶当中所存放的数据的个数，为了进行百位排序的时候的操作。            bucketElementCount[i] = 0;        }        System.out.println("第三轮的桶排序的结果:" + Arrays.toString(arr));        }

具体实现:

public static void radixSort(int[] arr) {
           //针对各位进行排序处理        //以空间换时间的排序算法，因为二维数组里面的每一个一维数组的长度的都设置为了arr.length。以防止所有的        //位数都放在同一个桶里面的情况。        int[][] bucket = new int[10][arr.length];        //为了记录每一个桶里面存放的数据的个数，比如bucketElementCount[0]=1表示第一个桶有一个数据。        int[] bucketElementCount = new int[10];//总共十个桶，每个桶记录存放的数据的个数        int max = 0;        //求出一个数组当中的最大的元素，然后求出它的位数。        for (int i = 0; i < arr.length; i++) {
               if (max < arr[i]) {
                   max = arr[i];            }        }        //根据最大值确定位数,把位数当做需要桶排序的次数。        int digitalCount = (max + "").length();//很巧妙        for (int x = 0, n = 1; x < digitalCount; x++, n *= 10) {
               //根据个位进行排序,放入到对应的桶当中            for (int i = 0; i < arr.length; i++) {
                   int digital = arr[i] / n % 10;                bucket[digital][bucketElementCount[digital]] = arr[i];                bucketElementCount[digital]++;//把放到桶里面的数据的个数加一。            }            int index = 0;            //取出按照个位排好序放入到桶中的元素，并且重新放入到arr数组当中。            for (int i = 0; i < bucket.length; i++) {
                   if (bucketElementCount[i] > 0) {
                       //代表该桶里面有数据，遍历一下，把所有的数据取出来                    for (int k = 0; k < bucketElementCount[i]; k++) {
                           arr[index++] = bucket[i][k];//放到了arr中后要让index+1，为了存放下一个数据。                    }                }                //！！！！清空每一桶当中所存放的数据的个数，为了进行百位排序的时候的操作。                bucketElementCount[i] = 0;            }            System.out.println("第一轮的桶排序的结果:" + Arrays.toString(arr));        }    }

测试数据:

//生成随机数，Math.random随机生成从0到1的小数        int[] arr2 = new int[8000000];        for (int i = 0; i < 8000000; i++) {
               arr2[i] = (int) (Math.random() * 800000);        }        Date date = new Date();        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat = simpleDateFormat.format(date);        System.out.println("排序前的时间");        System.out.println(dateFormat);        radixSort(arr2);        Date date2 = new Date();        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");        String dateFormat2 = simpleDateFormat.format(date2);        System.out.println("排序后的时间");        System.out.println(dateFormat2);

转载地址：http://srlen.baihongyu.com/