初级排序算法

约定

首先约一些辅助函数，代码如下：

/**
 * 交换元素
 */
private static void exchange(Comparable[] a,int i,int t){
    Comparable temp = a[i];
    a[i]=a[t];
    a[t]=temp;
}

/**
 * 比较元素:前一个元素是否比后一个元素小
 */
private static boolean less(Comparable a,Comparable b){
    return a.compareTo(b)<0;
}

/**
 * 元素是否是有序的
 */
public static boolean isSorted(Comparable[] target){
    for (int i = 1; i < target.length; i++) {
        if(less(target[i],target[i-1])){
            return false;
        }
    }
    return true;
}

选择排序

核心思想就是：每趟找到最小的元素，然后通过交换的方式将它放在最左边（从左到右是从小到大的顺序），下一趟从最左边的后一个元素开始，以此类推达到排序。一个示例代码如下：

/**
 * 选择排序
 */
public static Comparable[] selectSort(Comparable[] a){
    if(null==a){
        return null;
    }

    for(int i=0;i<a.length;i++){
        int min=i;
        //先找到最小的元素
        int j=i+1;
        for(;j<a.length;j++){
            if(less(a[j],a[min])){
                min=j;
            }
        }
        //然后和最左边的元素交换
        exchange(a,i,min);
    }
    return a;
}

插入排序

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定。为了给更小的元素腾出空间，它们可能会向右移动。当索引到达数组的右端时，数组排序就完成了。 整个过程可以类比于打牌，左边放置有序的牌，将右边第一张牌插入到左边并且保证有序。 一个代码示例如下：

/**
 * 插入排序
 */
public static Comparable[] insertSort(Comparable[] target){
    if(null==target){
        return null;
    }else if(1==target.length){
        return target;
    }
    for (int i = 1; i < target.length; i++) {
        for(int k=i;k>0&&less(target[k],target[k-1]);k--){
            exchange(target,k,k-1);
        }
    }
    return target;
}

希尔排序

希尔排序是一种基于插入排序的快速排序算法，为了加快速度改进了插入排序， 交换了不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部的有序数组排序。 一个代码示例如下：

/**
 * 希尔排序:基于插入排序，优先使用这种（暂不理解）
 */
public static Comparable[] shellSort(Comparable[] target){
    if(null==target){
        return null;
    }else if(target.length==1){
        return target;
    }
    int h=1;
    while(h<target.length/3){
        h=h*3+1;
    }
    while(h>=1){
        for(int i=h;i<target.length;i++){
            for(int j=i;j>=h&&less(target[j],target[j-h]);j-=h){
                exchange(target,j,j-h);
            }
        }
        h/=3;
    }
    return target;
}

归并排序

思想就是将多个序列归并成一个有序的序列，一个代码示例如下：

//nums1和nums2原本便是是有序的，归并到res内
public void findMedianSortedArrays(int[] nums1, int[] nums2) {
    int i=0,j=0,count=0;
    int m=nums1.length;
    int n=nums2.length;

    //准备合并两个数组
    int[] res = new int[m+n];

    while(count!=(m+n)){
        //如果第一个数组已经遍历完啦,则直接将第二个数组剩余的添加到res后面（前提是原本两个数组就是有序的）
        if(i==m){
            while(j!=n){
                res[count++]=nums2[j++];
            }
            break;
        }
        //如果第二个数组遍历完啦
        if(j==n){
            while(i!=m){
                res[count++]=nums1[i++];
            }
            break;
        }
        int val1 = nums1[i];
        int val2 = nums2[j];
        res[count++]=val1<=val2? nums1[i++]:nums2[j++];
    }
}