关于排序以及对其测试与复杂度分析

作者: 墨小翼 | 来源:发表于2019-04-02 21:17 被阅读0次

这里先提一下最简单的排序问题的区别
1.冒泡排序

通过一个指针指向最后一个元素的位置，每次都是首元素依次与后面的元素比较然后根据大小交换，直到与指针位置的元素比较完毕，然后这个指针向前移动一个位置进行下一个子循环，直到指针移到首元素位置。
代码如下

package paixu;

public class BubbleSort {


    public static void bubblesort(int []array){
        int b=0;
        for (int i  = array.length-1;i>=0; i --) {
            for(int j=0;j< i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                }
            }

        }
    }
    public static void swap(int[]arr,int a,int b)
      //注意要数组传进交换函数来
    {
        int temp =arr[a];
        arr[a]=arr[b];
        arr[b]=temp;

    }
    public static void main(String[] args) {
        int []array1={1,2,3,6,3,5};

        bubblesort(array1);
        for (int i = 0; i < array1.length; i++) {

            System.out.println(array1[i]);

        }
    }
}

2.选择排序

与之思想类似，指针指向初始位置，每次循环把最小的数放在指针位置，然后指针向后移动1位。

public class SelectSort {

    public static void sort(int []arr){
        if (arr.length<2||arr==null)return;
        for (int i = 0; i < arr.length-1; i++) {
            int min=i;
            for (int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min])min=j;
                }
            swap(arr,i,min);
            }
        }

    public static void swap(int[] arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args){
        int []array={1,2,1,6,3,4,2};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

3.插入排序
插入排序类似于整理扑克牌，基本操作是将一个记录插入到已经排好序的有序数列中，从而得到一个有序但记录数加一的有序数列。

public class InsertSort {
  public static void sort(int []arr){
        if (arr.length<2||arr==null)return;
        for (int i = 1; i < arr.length; i++) {
            for (int j=i-1;j>=0;j--){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
    public static void swap(int[] arr,int a,int b){
        int temp=0;
        temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args){
        int []array={1,2,1,6,3,4,2};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

关于以上的三种简单排序的复杂度计算

1.冒泡排序
第一次冒泡循环n次，然后然后每次冒泡比之前循环次数－1（因为指针向前移动了一位）
n+n-1+n-2+....+1=((1+n)n)1/2=1/2n+1/2n^2
T(1/2n+1/2n^2)= O(n^2)
2.选择排序同理
3.插入排序每次插入比较的过程都是和指针位置前面的元素依次比较，
即：
0+1+2+...+n-1+n=((1+n)n)1/2=1/2n+1/2n^2
T(1/2n+1/2n^2)=O(n2)

关于排序的稳定性

稳定性是指把排序后相同的元素的位次同排序前没有改变
那稳定了有什么好处呢？
我们来想一个工作场景，给你一个表格上面是面试的人基本信息有姓名，年龄，毕业学校。我先通过其毕业学校的排名对这个列表排序，然后在通过年龄进行排序。这样如果排序算法稳定，之前通过学校排名进行的排序的结果，就会在年龄相同的人中体现出来。
显而易见冒泡排序和插入排序是稳定的,而选择排序是不稳定的，是因为选择排序的交换过程可能会把第一位次的元素换到第二位次。
举个例子
序列5 8 5 2 9，这个在执行选择排序的时候，第一遍，肯定会将array[0]=5，交换到2所在的位置，也就是 2 8 5 5 9，那么很显然，之后的排序我们就会发现，array[2]中的5会出现在原先的array[0]之前，所以选择排序不是一个稳定的排序

关于写好的算法的测试方法
因为有些方法是易想难证的，所以在打比赛时可以通过大量的数据模拟进行验证，我们也管他叫做对数器。
它的思想是这样的
我们先写一个时间复杂度高但是绝对正确的算法，再把我们希望测试的算法放在里面，通过随机数产生多组测试数据，然后通过比较两个算法的结果，来确定算法的正确性。

import java.lang.reflect.Array;
import java.util.Arrays;

public class Logarithm {
    public static void TestMethod(int []arr){
        if (arr.length<2||arr==null)return;
                for (int i = 1; i < arr.length; i++) {
                    for (int j=i-1;j>=0;j--){
                        if(arr[j]>arr[j+1]){
                            swap(arr,j,j+1);
                        }
                    }
                }
            }
    public static int [] GenerateRandeoArray(int size ,int value){
        int []arr= new int[(int)((size+1)*Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=((int) (Math.random() * (value + 1)) -(int)(Math.random()*value));
        }
        return arr;
    }
    //(value+1)*random()一定比value+1小，强制转换为int 则其范围为【0~value】了
    public static void AbsoultRightMethod(int []arr){
        Arrays.sort(arr);
    }
    public static int[]CopyArray(int[]arr){
        if(arr==null)return null;
        int []res=new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i]=arr[i];
        }
        return res;
    }
    public static boolean IsEqual(int[]arr1,int []arr2){
        if (arr1==null&&arr2!=null)return false;
        if (arr2==null&&arr1!=null)return false;
        if (arr1==null&&arr2==null)return true;
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i]!=arr2[i])return false;
        }return true;

    }
    public static void swap(int[] arr,int a,int b){
        int temp=0;
        temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args) {
            boolean success=true;
            int testtime=1;
        for (int i = 0; i < testtime; i++) {
            int[] array1=GenerateRandeoArray(100,20);
            int[]array2=CopyArray(array1);
            AbsoultRightMethod(array2);
            TestMethod(array1);
            if(!IsEqual(array1,array2)){
                success=false;
                break;
            }
            for (int i1 = 0; i1 < array1.length; i1++) {
                System.out.print(array1[i1]);
            }
            System.out.println();
            for (int i2 = 0; i2 < array2.length; i2++) {
                System.out.print(array2[i2]);
            }
            System.out.println();


        } System.out.println(success?"yes":"no");

    }
}

关于二分归并排序

这里首先要提一下的是递归思想
1.首先要知道函数的间调用是一个进栈出栈的过程


public class Stack {
    public static int method1(){
        method2();
        return 0;
    }
    public static int  method2(){
        method3();
        return 0;
    }
    public static int  method3(){
        method4();
        return 0;
    }
    public static int  method4(){
       return 0;
    }
   
}

栈

调用method1的时候method1以及其参数进栈，method1调method2的时候method2进栈......直到method4进栈。
然后method4执行完毕后会被弹出，这时method3继续执行，即执行调用了method4后的return 0;语句,然后将method3弹出.......直到所有函数都弹出，程序结束。
2.进行递归调用时也是这个道理，递归函数调用自己，把此时这个函数的个哥参数封存到栈底，然后它的子递归函数进栈，子递归函数调用自己的子函数...直到到达递归出口，即最顶端的子函数弹出，在其下面封存的函数被激活，执行，弹出，再到下一个函数激活......直到整个程序结束。

3.二分归并函数
前面提到的基本排序函数都是要一个数与剩下的数都比个遍，而二分的思想是我能不能把整体分成一半，在一半中进行比较，都比较完后我再把他们一次的整理下就好了。然后对于每个被分成一半的数我把他们看成一个整体再继续划分。这样我比较的次数就大大减少了。
这是加入了对数器测试的代码

import java.lang.reflect.Array;
import java.util.Arrays;

public class Logarithm {

    public static int merge(int []arr ,int l,int r){
        if(l==r)return 0;
        int mid =l+((r-l)>>1);
        return merge(arr,l,mid)+merge(arr,mid+1,r)+mergesort(arr,l,mid,r);
    }
    public static int mergesort(int []arr,int l,int m,int r){
        int []help=new int [r-l+1];
        int i=0;
        int p1=l;
        int p2=m+1;
        //int res=0;
        while(p1<=m&&p2<=r){
            //  res+=arr[p1]<arr[p2]?arr[p1]*(r-p2+1):0;
            help[i++]=arr[p1]>arr[p2]?arr[p2++]:arr[p1++];
        }
        while(p1<=m){
            help[i++]=arr[p1++];
        }

        while(p2<=r){
            help[i++]=arr[p2++];
        }
        for ( i = 0; i < help.length; i++) {
            arr[l+i]=help[i];
        }
        return 0;


    }
    public static int TestMethod(int []arr){
   
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return merge(arr, 0, arr.length - 1);

    }
    public static int [] GenerateRandeoArray(int size ,int value){
        int []arr= new int[(int)((size+1)*Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=((int) (Math.random() * (value + 1)) -(int)(Math.random()*value));
        }
        return arr;
    }
    //(value+1)*random()一定比value+1小，强制转换为int 则其范围为【0~value】了
    public static void AbsoultRightMethod(int []arr){
        Arrays.sort(arr);
    }
    public static int[]CopyArray(int[]arr){
        if(arr==null)return null;
        int []res=new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i]=arr[i];
        }
        return res;
    }
    public static boolean IsEqual(int[]arr1,int []arr2){
        if (arr1==null&&arr2!=null)return false;
        if (arr2==null&&arr1!=null)return false;
        if (arr1==null&&arr2==null)return true;
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i]!=arr2[i])return false;
        }return true;

    }
    public static void swap(int[] arr,int a,int b){
        int temp=0;
        temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args) {
            boolean success=true;
            int testtime=100;
        for (int i = 0; i < testtime; i++) {
            int[] array1=GenerateRandeoArray(100,20);
            int[]array2=CopyArray(array1);
            AbsoultRightMethod(array2);
            TestMethod(array1);
            if(!IsEqual(array1,array2)){
                success=false;
                break;
            }
            for (int i1 = 0; i1 < array1.length; i1++) {
                System.out.print(array1[i1]);
            }
            System.out.println();
            for (int i2 = 0; i2 < array2.length; i2++) {
                System.out.print(array2[i2]);
            }
            System.out.println();


        } System.out.println(success?"yes":"no");

    }
}

4.关于递归问题的复杂度分析
这里引入一个计算递归问题复杂度的公式，有兴趣的朋友可以去自行证明这里证明就不再多提。
master公式的使用
T(N) = a*T(N/b) + O(N^d)
a为一次递归调用分出子问题的个数
b为每个子问题的数据量
c为普通逻辑语句的个数

log(b,a) > d -> 复杂度为O(N^log(b,a))

log(b,a) = d -> 复杂度为O(N^d * logN)

log(b,a) < d -> 复杂度为O(N^d)
那么二分归并排序的Tn=1/2T(N/2)+O(N)
所以起时间复杂度为N*log(N)
好了接下来我们用这种思想试着解决一个问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16
最简单的想法是写个双重循环把它依次的遍历

    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                res += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return res;
    }

但再想想呢有没有更紧单些的复杂度更低的方法呢
我们之前在分析二分归并函数的时候就写到当一个东西从整个的循环遍历它来进行交换的时候，这样做是很低效的。而我们用二分的思想进行划分的话可以复杂度从O(n^2)降到O（n*logn）。而对于这个问题可以这样想吗？
仔细想过程会发现每次划分都是有一左一右的，而且归并的时候会有左右两边大小的比较，那么我们在每次比较的时候用一个变量记下左边小的情况然后进行累加，得出结果。

public class Code_SmallSum {

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

    public static int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    public static int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    // for test
    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                res += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return res;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (smallSum(arr1) != comparator(arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }https://www.keybr.com/
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

}

快速排序

在说快排前我们先去思考一个经典的荷兰国旗问题
1.题目

给定一个数组arr，和一个数num，请把小于num的数放在数组的
左边，等于num的数放在数组的中间，大于num的数放在数组的
右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

不言而喻

2.思考过程

很简单我们通过设置三个指针分别指向数组外的两端
以代表我们规划大于num和小于num的区域
再有一个指针指向数组第一个元素进行遍历
如果不等于num就与划分区域附近的元素（或左或右）进行交换
等于的话就跳过

3.实现过程中遇到的麻烦

1最开始习惯性的用了for去做便利指针的移动，但发现指针的移动是有多种条件的不适合for
2对从后面还来的数还需要判断，通过指针的不动解决
3.通过限定i++的条件即只有和自己或者相等的元素交换才能++ 来保证区域的划分

public class flag {
    public static void Flag(int[] arr, int num) {
        int small = -1;
        int big = arr.length;
        int i = 0;
        while (i < big)//
        {//通过指针的不动来控制下一次循环依旧从该位置进行判定

            if (arr[i] <num) {
                swap(arr, i++, ++small);//对换过来的数已经进行了限定，
//即限定了小于区域后面得数只可能是等于区域的数或者我自己，
//如果是大于区域的数就会重新考虑

            } else if (arr[i] > num) {
                swap(arr, --big, i);//通过指针的停留重新考录换过来的数
            } else {
                i++;
            }
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int a[] = {1, 3, 2, 6, 6, 236};
        Flag(a,5);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }

    }

}

快速排序中就是通过运用荷兰国旗问题不断地把数组化为
一边<num一边>num中间等于的部分不动支队两边递归
如果说二分归并排序运用了递归溯洄的时候那么快排则是运用了递归函数不断地向下划分的过程每次向下递归时我都把你先分成一半比一个数小一般比一个数大。

public class QuickSort {
public static int [] partion(int arr[],int l,int r ){
    int small=l-1;
    int big=r+1;
    while(l<r){
        if (arr[l]<arr[r-1]){
            swap(arr,++small,l++);
        }
        else if (arr[l]>arr[r-1]){
            swap(arr,--big,l);
        }
        else l++;
    }
    int []help=new int [2];
    help[0]=small;
    help[1]=big;
    return help;
}
public static void quick (int []arr,int l,int r){
    int []help=partion(arr, l,r);
    if(l>=r)return;
    quick(arr,l,help[0]+1);//注意这里help返回的是big和small，
    quick(arr,help[1]-1,r);
}
    public static void swap(int []arr,int a,int b){
    int temp =arr[a];
    arr[a]=arr[b];
    arr[b]=temp;

    }

    public static void main(String[] args) {
     int []a={1,3,9,1,4,3,5,3};
     quick(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

}

4.这里要提的一句是程序的运行是与数据有关系的，每次进行划分的时候我们都是按照最后一个数进行划分的，那么问题来了。如果数据是2，3，4，5，6，1呢我们需要一直从头遍历，怎么解决这样的问题呢？
很简单在划分前把最后一个数与前面随机一个数交换就好了。
代码如下

public class QuickSort1 {
public static int []partion (int []arr,int l,int r){
    int small=l-1;
    int big=r+1;//小错

    while(l<big){//不思考就写习惯性的出写了l<r
         if(arr[l]<arr[r]){
             swap(arr,++small,l++);
         }
         else if ((arr[l])>arr[r]){
             swap(arr,--big,l);
         }
         else{
             l++;
         }
     }
    int []help=new int [2];
    help[0]=small;
    help[1]=big;
    return help;
}
public static void QuickSort(int []arr,int l,int r){
    if(l>=r)return;
    swap(arr,l+(int)((r-l+1)*Math.random()),r);//从零开始一直到r-l的r-l+1个数
    int []help=partion(arr,l,r);
    QuickSort(arr,l,help[0]-1);//小错
    QuickSort(arr,help[1]+1,r);

}
public static void swap(int []arr,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;

}

    public static void main(String[] args) {
        int []a={1,2,3,1};
        QuickSort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

}

5.这里分析一下其复杂度

时间复杂度
1.最好的情况是每次都从中间划分，就正如之前说过的二分归并排序。
T（N）=O(nlog(n))
2.最不好的情况就如我们之前优化分析的情况，每次都是最后一个进行划分的标准数比前面的数都大
也就是 T(N)=T(n+n-1+...+2+1)=T(1/2n*(n-1))=O(n^2)
而通常情况，由于涉及概率问题不再深究有兴趣的盆友可以看看这位老哥的帖子
空间复杂度见图

字丑勿怪2333

堆排序
堆结构

在说堆排的时候我们先了解一下堆这种结构吧堆其实是就是数组。只是我们把数组脑补成一个完全二叉树。

2.完全二叉树包括满二叉树。

3.根节点为n的话，子节点为2*n+1

大小根堆：根节点都比子节点大的为大根堆

怎么把数组生成大根堆
想法是这样的
从最开始的跟位置不断和上一根结点比较如果比根节点大就交换指针放到根节点位置不断循环直到堆的顶部

代码如下：

package paixu;

public class Heap_Big_Initialise {
public static void HeapIntialise(int[]arr){
    for (int i = 0; i < arr.length; i++) {
        HeapInsert(arr,i);
    }
}
public static void HeapInsert(int[] arr,int i){
    while (arr[i]>arr[(i-1)/2]){
        swap(arr,i,(i-1)/2);
        i=(i-1)/2;
    }
}
public static void swap(int[]arr,int i,int j){
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;


}
public static void main(String[] args) {
   int arr[]={1,2,3,5,4};
   HeapIntialise(arr);
   for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    }
}

那怎么通过堆结构进行排序呢？
这就引入了heapify的概念了，即使删除堆顶元素的堆再次成为堆。
首先小根堆堆顶元素是一定为最小的,我们用一个数组不断得保留堆顶元素的值，然后把最底下的一个叶子结点放在堆顶，让它不断地向下和比它小的子节点交换。

代码如下

package paixu;

public class heap {

    public static void heapsort(int[]arr){
        //建堆
        for (int i = 0; i < arr.length; i++) {
            heapinsert(arr,i);
        }

        int size=arr.length-1;
       while (size>0) {
            swap(arr, 0, size--);
           heapfy(arr, size);

        }
    }
    //建大根堆用
    public static void heapinsert(int[] arr,int i){
        while (arr[i]>arr[(i-1)/2]){
            swap(arr,i,(i-1)/2);
            i=(i-1)/2;
        }
    }
    //从上往下不断比较的方法
    public static void heapfy(int []arr,int size){
        int index=0;
        int left=index*2+1;
        while(left<size){
            int large=(arr[left]>arr[left+1])&&left+1<=size?left:left+1;
            large=arr[index]>arr[large]?index:large;

            if(index==large){
                break;
            }

                swap(arr,large,index);
                index=large;
                left=index*2+1;

        }
    }
    //交换函数

    public static void swap(int[]arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;


    }
    public static void main(String[] args) {
        int arr[]={1,3,2,6};
        heapsort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

      }
}

要知道在建堆的时候会进行交换。
就如下图

image.png

所以堆排序是不稳定的

P.S.
对于二分归并排序我只要保证归并的时候左边小于等于右边就先把左边归并，就可以保证二分归并排序的稳定性。
对于快排，是可以实现稳定排序的但是已经是论文级别的难度了，这里不说了。

关于工程排序算法

IMG_0219(20190408-164936).jpg

桶排序

个人感觉桶排序是最笨拙也是最有灵魂的排序了
1.它是不基于比较的排序，时间复杂度可达到O（n）
2.它的基本想法是，比如说我对1~6六个数进行进行排序，我就申请六个数的辅助数组。然后待比较元素和数组下标一致的话该下标下的计数器++，
然后我按计数器个数一次输出辅助数组下表就好了。
3.当然这样会有数据范围与数据量的问题，数据量很大的话我就只对你数据的前几位进行桶排序，然后再对每个桶里的数据的前几位排序进行桶排序，可见这并不具有普适性。
4.但桶排序这种思想有时候能做很取巧的事。

关于桶排序思想的运用
给定一个数组，求如果排序之后，相邻两数的最大差值，要求时
间复杂度O(N)，且要求不能用非基于比较的排序
这个方法很精妙
1.给我n个数我就准备n+1个桶，通过遍历我得到最大值和最小值，计算最大值最小值的差值，把这个插值分成n份，标记到从1号桶到n号桶上，0号桶上放置最小值，n号桶上放置最大值。
2.然后我遍历待排序数组，把每个数组都与最小值相减，用这个差值去除之前分得每个桶每份的差值，得到要放入桶的序号，然后判断该桶内最大值和最小值和刚放进去的这个数的关系，刷新。这样我只要用一个全局变量MAX记录相邻最大值和后一个桶的最小值的插值之中最大的那个就好了。

那么问题来了

我为什么要有把差值分成n份呢即我为何要准备n+1个桶呢，重点来了由于鸽巢原理必有一个桶是空的这就保证了我的max是不可能在一个桶里的两个数的差值取到的。而只可能是两个及以上（中间有空桶）的桶之间取到的

具体关于n分的详细分析

代码

package basic_class_01;
import java.util.Arrays;


public class 桶排序 {

        public static int maxGap(int[] nums) {
            if (nums == null || nums.length < 2) {
                return 0;
            }
            int len = nums.length;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
            if (min == max) {
                return 0;
            }
            boolean[] hasNum = new boolean[len + 1];
            int[] maxs = new int[len + 1];
            int[] mins = new int[len + 1];
            int bid = 0;
            for (int i = 0; i < len; i++) {
                bid = bucket(nums[i], len, min, max);
                mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
                maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
                hasNum[bid] = true;
            }
            int res = 0;
            int lastMax = maxs[0];
            int i = 1;
            for (; i <= len; i++) {
                if (hasNum[i]) {
                    res = Math.max(res, mins[i] - lastMax);
                    lastMax = maxs[i];
                }
            }
            return res;
        }

        public static int bucket(long num, long len, long min, long max) {
            return (int) ((num - min) * len / (max - min));
        }

        // for test
        public static int comparator(int[] nums) {
            if (nums == null || nums.length < 2) {
                return 0;
            }
            Arrays.sort(nums);
            int gap = Integer.MIN_VALUE;
            for (int i = 1; i < nums.length; i++) {
                gap = Math.max(nums[i] - nums[i - 1], gap);
            }
            return gap;
        }


    public static void main(String[] args) {
        int []a={1,4};
        System.out.println(maxGap(a));
}

}

关于排序以及对其测试与复杂度分析

关于以上的三种简单排序的复杂度计算

关于排序的稳定性

关于二分归并排序

小和问题

快速排序

堆排序

关于工程排序算法

桶排序

那么问题来了

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读