算法读书笔记-排序算法-初级排序

排序算法基本结构

在一个排序算法类中可以包含以下几个基本方法（将这几个方法抽象出来后会使代码的可读性变高）

    public static void exch(Comparable[] a,int i,int j){Comparable temp = a[i];a[i] = a[j]; a[j] = temp;}//交换两个数
    
    public static boolean less(Comparable v,Comparable w){return v.compareTo(w)<0;}//比较两个元素的大小，若v比w小返回ture否则返回false
    
    public static boolean isSorted(Comparable[] a){//判断是否按照从小到大排序
        for(int i=1;i<a.length;i++){
            if(less(a[i-1],a[i])) return false;
        }
        return true;
    } 
    
    public void show(Comparable[] a){
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }

选择排序

基本思路:从当前位置起，选出他后面数字的最小值然后和当前位置交换。
时间复杂度：O(n^2)

示例代码

public static void Selection(Comparable[] a){
        int min;//用于记录最小值的位置
        for(int i = 0;i<a.length-1;i++){
            min = i;
            for(int j=i;j<a.length;j++){//找到最小值的位置
                if(less(a[j],a[min])){
                    min = j;
                }
            }
            exch(a, min, i);
        }
    }

插入排序

基本思路：从第一个数开始，将当前的数按序插入到之前序列中（保持在当前数之前的序列是有序的
时间复杂度:O(n^2）（在序列部分是有序的情况下效率较高）

示例代码

    public static void Insertion(Comparable[] a){
        for(int i=0;i<a.length;i++){
            Comparable temp;
            for(int j=i;j>0;j--){
                temp = a[j];
                if(less(temp,a[j])) a[j]=a[j-1];//exch(a, i, j);使用交换的方法插入
                else a[j] = temp;
            }
                
        }
    }

希尔排序

基本思路：通过一个h的值将数组变成一个h有序数组（这些数组任意间隔h个单位距离都是有序的）,通过产生一个值的序列将多个不同有序数组交织起来就完成了排序。
时间复杂度：O（nlgn）（在中等规模的数据时效率较好）

示例代码

public static void Shell(Comparable[] a){
        int h=1;
        int N = a.length;
        while(h<N/3) h = h*3+1;//生成递增序列，也可以通过给定一个递增序列进行排序
        while(h>=1){
            for(int i=h;i<N;i++){
                for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h) 
                    exch(a, j, j-h);
            }
            h=h/3;
        }   
    }