归并排序、快速排序

归并排序

不断地讲无序数组分成两部分比较

实现:

import java.util.Arrays;


public class MergeSort {
    /**
     *
     * @param arr
     * @param l 数组最左边的元素
     * @param mid 中间归并的分隔
     * @param r 数组最右边的元素
     */
//    如何归并
    public static void merge(int[] arr,int l, int mid, int r){
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);

//        设置两个指针指向分开数组的头尾
        int i = l,j = mid + 1;
        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++;
            }
        }

    }

//    定义归并的方法
//    将原来的数组进行分割
    private static void sort(int[] arr,int l, int r){
        if (l >= r){
            return;
        }

        int mid = (l+r) / 2;

//        这里递归调用将数组分割到最小
        sort(arr, l, mid);
        sort(arr, mid+1, r);
//        分割后执行递归
        merge(arr, l, mid, r);
    }

    public static void sort(int[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    public static void main(String[] args) {
        int[] arr = {5,8,1,4,3};
        MergeSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
}

优化在近乎有序数组时归并排序的效率

private static void sort(int[] arr,int l,int r){

        if (l>=r){
            return;
        }

        int mid = (l+r)/2;
        sort(arr, l, r);
        sort(arr, mid + 1, r);
        if ( arr[mid] > arr[mid+1] ){
            merge(arr, l, mid, r);//优化在近乎有序数组时用归并排序时的效率
            //因为归并排序左边数组的最后一位元素小于右边第一位的时候已经确定了有序
        }

    }

归并排序在于用空间换取时间，需要另外开辟新的数组空间来进行归并

快速排序

如何进行取值分割（Partition）

实现:

public class QuickSort {

    public static void sort(int[] arr){
        int n = arr.length;
        quickSort(arr, 0, n-1);
    }

    private static void quickSort(int[] arr,int l,int r){
        if (l >= r){
            return;
        }
        //其实也是j
        int p = partition(arr,l,r);
        quickSort(arr, l, p-1);
        quickSort(arr, p+1, r);
    }

    private static int partition(int[] arr, int l, int r) {
//        先取出一个比较数
        int v = arr[l];
//        l+1是开始排列的第一个元素
        int j = l;//表示大于v元素区域一开始为空
//        i是当前访问的元素
        for (int i = l+1; i < r ; i++) {
//            若i位置的元素小于v,则j会指向此区域
            if ( arr[i] < v){
//                与j+1位置的元素互换
//             第一种写法：
                swap(arr,arr[j+1],arr[i]);
                j++;

//                第二种写法:
//                swap(arr,arr[++j],arr[i]);
            }
        }
        swap(arr,arr[l],arr[j]);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5,8,1,4,3};
        MergeSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
}

为了避免当数组近乎是有序或有大量重复时

双路排序

实现:

private static int partition(Comparable arr[],int l,int r){

        //选择一个随机数与第一个元素交换
        swap(arr, l, (int)(Math.random()*(r-l+1))+l);

        //拿出第一个元素做对比
        Comparable v = arr[l];

        //设i和j分别为左数组和右数组添加元素时指针
        int i = l+1,j=r;

        while (true){
            //若左数组下个元素小于v则考察下一个元素
            while(i<=r && arr[i].compareTo(v) <0){
                i++;
            }

            //若右数组下个元素大于v则考察下一个元素
            while(j<=l+1 && arr[j].compareTo(v) >0){
                j--;
            }
            //直到i>j时说明已经考察到了所有元素
            if(i>j){
                break;
            }

            //当两个while循环都不满足条件时
            //交换两个数组的最后一个元素使之满足v<i与v>j的条件
            swap(arr, i, j);
            i++;
            j--;
        }

        swap(arr, l, j);
        return j;
    }

三路排序

实现:

    private static void partition(Comparable arr[],int l,int r){

        //选择一个随机数与第一个元素交换
        swap(arr, l, (int)(Math.random()*(r-l+1))+l);

        //拿出第一个元素做对比
        Comparable v = arr[l];

        int lt = l;     // arr[l+1...lt] < v 指向<v的最后一个元素
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v 作为考察元素指针

        //i<gt则说明元素还为考察到最后一个
        while (i < gt){
            if(arr[i].compareTo(v) < 0){
                swap(arr, i,lt+1);
                lt++;
                i++;
            }
            else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }
        swap( arr, l, lt );

        sort(arr, l, lt-1);
        sort(arr, gt, r);
    }