排序学习笔记

简单的堆排序

public class EasyBucketSort{
    public static void main(String args[]){
        //输入0-100中任意8个数字，按从小到大排序
        int[] list= {22,45,22,65,11,88,2,90};
        
        //0到100共101个数字
        int[] a = new int[101];
        for(int i=0;i<a.length;i++){
            a[i] = 0;
        }
        
        //每个出现的数字，将a数组中对应位置加1
        for(int j=0;j<list.length;j++){
            a[list[j]]++;
        }
        
        //输出有值的a数组
        for(int n=0;n<a.length;n++){
            if(a[n]>0){
                for(int k=0;k<a[n];k++){
                    System.out.println(n);    
                }
            }
        }
        
    }
}

0到100间的整数，相当于有101个桶，哪个数出现就向哪个桶中加一个标识，最后从头开始遍历桶并输出就完成了从小到大排序。
共M个桶，待排序的数为N个，共执行了M+N+M+N次，则时间复杂度为O（M+N）。
（省略2*（M+N）中的常数2）

冒泡排序

每次比较相邻的两个元素，如果它们的顺序错误就交换他们。
比如要排序8个数，则第一次需要做这种相邻比较做7次，第一次便能确定最大一个数并将其放在最后；而第二次就只需排序7个数，比较6次……以此类推，一共要进行7次冒泡。

public class BubbleSort{
    public static void main(String args[]){
        //要从小到大排序8个数
        int[] list= {22,45,22,65,11,88,2,90};
        //n个数排序，走n-1趟
        for(int j=1;j<list.length;j++){
            //第j趟时，已经确定了j-1个数的位置，还有n-(j-1)个数待定，
            //因此只需进行n-(j-1)-1次比较，即n-j次
            for(int i=0;i<list.length-j;i++){
                int t;
                //若前面的大于后面的，则交换
                if(list[i]>list[i+1]){
                    t = list[i];
                    list[i] = list[i+1];
                    list[i+1] = t;
                }
            }
        }
        for(int k=0;k<list.length;k++){
            System.out.println(list[k]);
        }
    }
}

若要对n个数进行排序，则冒泡排序的时间复杂度为O（N*N），N的平方。

快速排序

随意找一个数作为基准数，从两端开始探测，从右向左找小于基准数的，从左向右找大于基准数的，然后交换这两个数。当两边的哨兵相遇则此次排序结束，此时基准数在其正确的顺序位置，其左侧都是比它小的，右侧都是比它大的。
其中哪侧的哨兵先行很重要，基准数在最左则右侧的哨兵先行：

public class QuickSort{
    static int[] list= {22,45,16,65,11,88,2,90};
    static int n = list.length;
    public static void main(String args[]){
        quicksort(0,n-1);
        for(int k=0;k<n;k++){
            System.out.println(list[k]);
        }
    }
    
    public static void quicksort(int left,int right){
        if(left >right){
            return;
        }
        int temp = list[left];//基准数
        int i = left,j = right;
        //左右哨兵相遇时跳出循环
        while(i!=j){
            //搜索到比基准数小的数时跳出
            while(list[j]>=temp && j>i){
                j--;
            }
            //搜索到比基准数大的数时跳出
            while(list[i]<=temp && j>i){
                i++;
            }
            //交换
            int t = list[j];
            list[j] = list[i];
            list[i] = t;
            
        }
        //此时左右哨兵相遇，将此位置与基准数交换；
        int t = list[j];
        list[j] = temp;
        list[left] = t;
        //递归，继续排基准左边的和基准右边的
        quicksort(left,j-1);
        quicksort(j+1,right);
    }
}

时间复杂度为O（NlogN）；