插入排序和归并排序

插入排序思想:在要排序的一组数中，假定前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]);    }}

运行结果:

归并排序思想:归并排序是利用归并的思想实现的排序方法，即分治法,分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案合在一起，即分而治之。

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)的辅助空间，在同类算法中归并排序的空间复杂度略高

更多相关文章

随机推荐