排序算法----归并排序

排序算法----归并排序

1. 归并排序：归并排序是建立在归并 *** 作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并。

2. 归并排序的时间，空间复杂度及稳定性：

        1>. 时间复杂度：O(nlogn)；因为我们这里归并排序的过程中向下递归二分数组时的时间复杂度为O(logn)；但是再向上并的过程中，还会遍历原数组，时间复杂度为：O(n)；因此归并排序的时间复杂度为：O(nlogn)。

        2>. 空间复杂度：S(n)；因为我们在归并排序时创建了其他新的数组。

        3>. 稳定性： 稳定；因为我们在归并排序时，并不会出现大跨度的交换元素。

3. 我们可以创建一个父类：父类中封装数组的创建，排序，交换位置等方法，其他的排序方法的类都继承于这个父类，重写父类中的方法。

public abstract class Sort {
    public int[] arr;

    public Sort(){};

    //有参构造方法 创建一个数组的副本
    public Sort(int[] arr){
        this.arr = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            this.arr[i] = arr[i];
        }
    }

    //对数组进行排序
    public abstract void sort(int[] arr);

    //交换数据位置
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

4. 归并排序的过程：

//归并排序 时间复杂度为：O(nlogn) 空间复杂度为：S(n) 算法稳定性：稳定

public class MergeSort extends Sort{

    public MergeSort(int[] arr){
        super(arr);
    }
    
    @Override
    public void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); //打印排序后的数组
    }

    //将数组进行归并排序
    //L表示原数组的左端下标 R表示原数组的右端下标
    private void mergeSort(int[] arr, int L, int R) {
        if(L >= R){ //向下递归的临界条件 当L>=R时 就向上合并
            return;
        }

        int mid = (L + R) / 2; //表示数组的中间位置
        //向下对数组进行二分
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);

        if(arr[mid] > arr[mid + 1]){
            merge(arr, L, mid, R); //向上合并
        }
    }

    //将子数组向上进行合并
    
    //l表示数组的左边边界 r表示数组的右边边界 mid表示数组的中间位置
    private void merge(int[] arr, int L, int mid, int R) {
        int[] aux = new int[R - L + 1];
        for(int k = L; k <= R; k++){
            aux[k - L] = arr[k];
        }

        int i = L; //i表示左边子数组的开始位置
        int j = mid + 1; //j表示右边子数组的开始位置
        for(int k = L; k <= R; k++){ //遍历原数组
            if(i > mid){
                
                arr[k] = aux[j - L];
                j++;
            }else if(j > R){
                
                arr[k] = aux[i - L];
                i++;
            }else if(aux[i - L] < aux[j - L]){
                
                arr[k] = aux[i - L];
                i++;
            }else{
                
                arr[k] = aux[j - L];
                j++;
            }
        }
    }
}

5. 测试类：测试类中只测试排序方法是否能成功。

public class TestSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 4, 6, 7, 2, 1, 3, 8, 10};
        MergeSort mergeSort = new MergeSort(arr);
        mergeSort.sort(arr);
    }
}