插入排序和归并排序(示例代码)

栏目: 类库 · 发布时间: 2021-03-04

来源:51cto.com

简介  这篇文章主要介绍了插入排序和归并排序(示例代码)以及相关的经验技巧,文章约3327字,浏览量410,点赞数3,值得参考!

插入排序思想:在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使这n个数也是排好顺序的。如此反复循环,直到全部排好顺序.(当待排序数据全部有序时,时间复杂度为O(N),最坏情况下时间复杂度为O(N*N),与待排序数据的状态有关).


public class InsertSort {
    public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2)
            return ;
        for(int i = 1; i < arr.length; i++) {
            for(int j = i -1; j >= 0 && arr[j] > arr[j+1]; j--)
                swap(arr, j , j+1);
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = new int[] {3,434,24,656,57,54,88,66};
        System.out.print("原始数组:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
            System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
        insertSort(arr);
        System.out.print("插入排序后:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
                System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
    }

}

运行结果:
技术图片

归并排序思想:用采用递归的方法将已有序的子序列两路合并,得到完全有序的序列,时间复杂度为O(N*logN),空间复杂度为O(N).


public class MergeSort {
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2)
            return ;
        sortProgress(arr, 0, arr.length - 1);
    }
    public static void sortProgress(int[] arr, int L, int R) {
        if(L == R)
            return ;
        int mid = L + ((R - L) >> 1);
         sortProgress(arr, L, mid);
         sortProgress(arr, mid+1, R);
        merge(arr, L, mid, R);
    }
    public static void merge(int[] arr, int L, int mid, int R){
        int[] help = new int[R- L + 1];
        int i = 0;
        int p1 = L;
        int p2  = mid + 1;
        while(p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] < arr[p2]? arr[p1++]: arr[p2++];
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2 <= R) {
            help[i++] = arr[p2++];
        }
        for(i = 0; i < help.length; i++)
            arr[L + i] = help[i];
    }
    public static void main(String[] args)
    {
        int[] arr = new int[] {45,3,5445,34,676,545,66,88};
        System.out.print("原始数组:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
            System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
        mergeSort(arr);
        System.out.print("归并排序后:");
        for(int i = 0; i < arr.length; i++)
        if(i != arr.length - 1)
            System.out.print(arr[i]+" ");
        else
            System.out.println(arr[i]);

    }
}

运行结果:
技术图片

插入排序优点:稳定排序
缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候
归并排序优点:效率高,时间复杂度为O(N*logN),是一种稳定的算法.
缺点:归并排序需要O(n)的辅助空间,而与之效率相同的快排和堆排分别需要O(logn)和O(1)的辅助空间,在同类算法中归并排序的空间复杂度略高


以上就是本文的全部内容,希望对大家的学习有所帮助,版权归原作者或者来源机构所有,感谢作者,如果未能解决你的问题,请参考以下文章。

排序算法总结-选择排序、插入排序、归并排序和快速排序(示例代码)

直接插入排序 ,折半插入排序 ,简单选择排序, 希尔排序 ,冒泡排序 ,快速排序 ,堆排序 ,归并排序的图示以及代码,十分清楚

排序算法——归并排序(示例代码)

插入和归并排序(示例代码)

九种经典排序算法详解(冒泡排序,插入排序,选择排序,快速排序,归并排序,堆排序,计数排序,桶排序,基数排序)(示例代码)