文章目录

• Arrays.sort() JDK1.8实质
• 归并
• 快排
• 希尔排序

Arrays.sort() JDK1.8实质

1. 大小超过286吗？

是→数据具不具备结构，有点结构则归并排序，没有则快速排序

否→数据小于47吗？超过用快速排序，不超过用插入排序

归并

public class mergeSort {
    public int[] copyOfRange(int[] array, int left, int right){
        int len = right - left;
        int[] newArray = new int[len];
        int j = 0;
        for (int i = left; i < right; i++){
            newArray[j] = array[i];
            j++;
        }
        return newArray;
    }
    public int[] mergeSort(int[] array){
        int len = array.length;
        if (len < 2)
            return array;
        int midIndex = len / 2;
        int[] left = copyOfRange(array, 0, midIndex);
        int[] right = copyOfRange(array, midIndex, len);

        return merge(mergeSort(left),mergeSort(right));
    }
    public int[] merge(int[] a1, int[] a2){
        int[] a3 = new int[a1.length + a2.length];
        int i = 0;
        int j = 0;
        int index = 0;
        while (i < a1.length && j < a2.length){
            if (a1[i] > a2[j]){
                a3[index] = a2[j];
                index++;
                j++;
            } else {
                a3[index] = a1[i];
                index++;
                i++;
            }
        }
        while (i < a1.length){
            a3[index] = a1[i];
            index++;
            i++;
        }
        while (j < a2.length){
            a3[index] = a2[j];
            index++;
            j++;
        }
        return a3;
    }
}

快排

class QuikSort2 {
    public void sort(int[] array){
        int len = array.length;
        if (len < 1)
            return;
        quikSort(array,0,len - 1);
    }

    private void quikSort(int[] array, int left, int right) {
        if (left > right)
            return;
        int i = left;
        int j =right;
        int pivot = array[left];
        while (i < j){
            while (i < j && array[j] >= pivot){
                j--;
            }
            while (i < j && array[i] <= pivot){
                i++;
            }
            if (i < j ){
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
//        基准归位，交换中间和基准
        array[left] = array[i];
        array[i] = pivot;
        quikcSort(array, 0, i - 1);
        quikcSort(array, i + 1, right);
    }

     public static void main(String[] args) {
         int[] a = {5, 2, 10};
         QuikSort2 quikSort2 = new QuikSort2();
         quikSort2.sort(a);
         for (int i = 0; i < a.length; i++)
             System.out.print(a[i] + " ");
     }
}

希尔排序

package com.fhy.cet6.sort;

public class shellSort {
    public static void ShellSort(int[] array){
        int len = array.length;
        if (len < 1)
            return;
        int gap = len / 2;
        while (gap > 0){
        //往后走
            for (int i = gap; i < len; i++){
                int preIndex = i - gap;
                int tmep = array[i];//记住当前的值
                while (preIndex >= 0 && array[preIndex] > tmep){
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = tmep;
            }
            gap/=2;
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 10,7,4,3,11};
        ShellSort(a);
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
    }
}