Java常见的排序算法详解

Java常见的排序算法详解
一、直接插入排序
 
整个区间被分为
 
有序区间
 
无序区间
 
每次选择无序区间的第一个元素,在有序区间内选择合适的位置插入。
 
   public static void insertSort(int[] arr){
 
        for (int i = 1; i < arr.length; i++) {
 
            int tmp = arr[i];
 
            int j = i - 1;
 
            for ( ; j >= 0 ; j--) {
 
                if (arr[j] > tmp){
 
                    arr[j + 1] = arr[j];
 
                }else{
 
                    //arr[j + 1] = tmp;//只要j回退的时候,遇到了比tmp小的元素,就结束了这次的比较
 
                    break;
 
                }
 
            }
 
            //j回退到了小于0的地方
 
            arr[j + 1] = tmp;
 
        }
 
    }
 
    public static void main(String[] args) {
 
        int[] array = {6,10,9,3,5};
 
        insertSort(array);
 
        System.out.println(Arrays.toString(array));
 
    }
 
}
 
输出结果:
 
时间复杂度:最好O(N)–>数据本身是有序的;
 
* 最坏O(N^2);–>数据逆序;
 
* 当一组数据,数据量不大且趋近于有序,此时用插入排序时间更快,越有序越快。
 
空间复杂度:O(1);
 
稳定性:稳定的排序;
 
一个稳定的排序可以实现为不稳定的排序,但是一个本身就不稳定的排序不可以变成稳定的排序。
 
二、希尔排序
 
希尔排序法又称缩小增量法。
 
希尔排序法的本质是插入排序,只不过是将待排序的序列按某种规则分成几个子序列,分别对几个子序列进行直接插入排序。这个规则就是增量,增量选取很重要,增量一般选序列长度一半,然后逐半递减,直到最后一个增量为1,为1相当于直接插入排序。
 
public static void shell(int[] arr,int gap){
 
    for (int i = 1; i < arr.length; i++) {
 
        int tmp = arr[i];
 
        int j = i - gap;
 
        for (; j >= 0 ; j-=gap) {
 
            if(tmp < arr[j]){
 
                arr[j + gap] = arr[j];
 
            }else{
 
                break;
 
            }
 
        }
 
        arr[j+gap] = tmp;
 
    }
 
}
 
    public static  void shellSort(int[] arr) {
 
        int gap = arr.length;
 
        //增量在缩小,最后一组的增量为1
 
        while (gap > 1){
 
            gap /= 2;
 
            shell(arr,gap);
 
        }
 
        shell(arr,1);
 
    }
 
    public static void main(String[] args) {
 
        int[] array = {9,1,2,5,7,4,8,6,3,5};
 
        shellSort(array);
 
        System.out.println(Arrays.toString(array));

推荐阅读