六大排序复习

找出当前元素到末尾元素最小值.放在当前区间首位。

代码如下:

 public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            swap(arr,min,i);
        }
    }

下面代码对上述代码性能进行优化:

public static void selectSortOP(int[] arr){
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            int min = left;
            int max = left;
            for (int i = left + 1; i <= right; i++) {
                if(arr[min] > arr[i]){
                    min = i;
                }
                if(arr[max] < arr[i]){
                    max = i;
                }
            }
            swap(arr,left,min);
            if(max == left){
                max = min;
            }
            swap(arr,max,right);
            left++;
            right--;
        }
    }

依次排序数组首个元素到当前位置元素

public static void insertionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j] < arr[j - 1]){
                    swap(arr,j,j - 1);
                }
            }
        }
    }

将上述代码进行优化得;

public static void insertionSortBS(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            int left = 0;
            int right = i;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(arr[mid] > tmp){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = tmp;
        }
    }

将数组看做一个二叉树,将最大元素放置首位,开始逐一下沉,完成排序

 public static void  pushSort(int[] arr){
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(arr,i,arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            shiftDown(arr,0,i);
        }
    }
    private static void shiftDown(int[] arr, int i, int length) {
        while(2 * i + 1 < length){
            int j = 2 * i + 1;
            if(j + 1 < length && arr[j] < arr[j + 1]){
                j = j + 1;
            }
            if(arr[i] > arr[j]){
                break;
            }else{
                swap(arr,i,j);
            }
            i = j;
        }
    }

public static void shellSort(int[] arr){
        int gap = arr.length / 2;
        while(gap > 1){
            insertionSortGap(arr,gap);
            gap = gap >> 1;
        }
        insertionSortGap(arr,1);
    }
    private static void insertionSortGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j = j - gap) {
                swap(arr,j,j - gap);
            }
        }
    }

public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0, arr.length - 1);
    }
    private static void mergeSortInternal(int[] arr, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSortInternal(arr,left,mid);
        mergeSortInternal(arr,mid + 1,right);
        merge(arr,left,mid,right);
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmpArr = new int[right - left + 1];
        for (int i = 0; i < tmpArr.length; i++) {
            tmpArr[i] = arr[left + i];
        }
        int i = left;
        int j = mid + 1;
        for (int k = i; k <= right; k++) {
            if(i > mid){
                arr[k] = tmpArr[j - left];
                j++;
            }else if(j > right){
                arr[k] = tmpArr[i - left];
                i++;
            }else if(tmpArr[i - left] > tmpArr[j - left]){
                arr[k] = tmpArr[j - left];
                j++;
            }else{
                arr[k] = tmpArr[i - left];
                i++;
            }
        }
    }

一路快排

public static void quickSort1(int[] arr){
        quickSort1Helper(arr,0,arr.length - 1);
    }
    private static void quickSort1Helper(int[] arr, int left, int right) {
        int x = left + (right - left) / 2;
        swap(arr,x,left);
        if(right - left <= 2){
            //更高效的处理
            insertionSort(arr);
            return;
        }
        int p = partition(arr,left,right);
        quickSort1Helper(arr,left,p - 1);
        quickSort1Helper(arr, p + 1, right);
    }
    private static int partition(int[] arr, int left, int right) {
        int val = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if(arr[i] < val){
                swap(arr,i,j + 1);
                j++;
            }
        }
        swap(arr,left,j);
        return j;
    }

二路快排

public static void quickSort2(int[] arr){
        quickSort2helper(arr,0,arr.length - 1);
    }
    private static void quickSort2helper(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }
        int p = partition2(arr,l,r);
        quickSort2helper(arr,l,p - 1);
        quickSort2helper(arr,p + 1,r);
    }
    private static int partition2(int[] arr, int l, int r) {
        int x = l + (r - l) / 2;
        swap(arr,l,x);
        int val = arr[l];
        int i = l + 1;
        int j = r;
        while(true){
            while(i <= j && arr[i] < val){
                i++;
            }
            while(i <= j && arr[j] > val){
                j--;
            }
            if(i > j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }

三路快排

public static void quickSort3(int[] arr){
        quickSort3helper(arr,0,arr.length - 1);
    }
    private static void quickSort3helper(int[] arr, int l, int r) {
        if(l >= r){
            return;
        }
        int p = partition3(arr,l,r);
        quickSort3helper(arr,l,p - 1);
        quickSort3helper(arr,p + 1,r);
    }
    private static int partition3(int[] arr, int l, int r) {
        int x = l + (r - l) / 2;
        swap(arr,l,x);
        int lt = l;
        int i = l;
        int gt = r + 1;
        int val = arr[l];
        while(i < gt){
            if(arr[i] < val){
                swap(arr,lt + 1,i);
                lt++;
                i++;
            }else if(arr[i] > val){
                swap(arr,gt - 1,i);
                gt--;
            }else{
                i++;
            }
        }
        swap(arr,l,gt - 1);
        return gt - 1;
    }