常见的排序算法

常见的排序算法有：插入、希尔、选择、冒泡、归并、快速、堆排序。。。

插入排序

算法步骤
一、从数组的第二个数据开始往前比较，如果符合条件（比前面的大或者小，自定义），则让他们交换位置。
二、再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较。
三、重复步骤二，一直到数据全都排完。

public static void sort(){
        int[] ints = new int[]{8, 3, 1, 18, 12, 30};
        for (int i = 1; i < ints.length; i++) {
            int j = i;
            while (j > 0) {
                int temp;
                if (ints[j] < ints[j - 1]) {
                    temp = ints[j];
                    ints[j] = ints[j - 1];
                    ints[j - 1] = temp;
                    j--;
                } else {
                    break;
                }
            }
        }
        for (int t:ints){
            System.err.println(t);
        }
    }

希尔排序

算法步骤
一、希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。
二、 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

public static void sort(){
        int[] ints = new int[]{8, 3, 1, 18, 12, 30};
        for (int gap = ints.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < ints.length; i++) {
                int j = i;
                if (ints[j] < ints[j - gap]) {
                    int temp = ints[j];
                    while (j - gap >= 0 && temp < ints[j - gap]){
                        ints[j] = ints[j - gap];
                        j-=gap;
                    }
                    ints[j] = temp;
                }
            }
        }
        for (int a : ints)
            System.err.println(a);
    }

选择排序

算法步骤
一、首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置。
二、再从剩余未排序的元素中继续寻找最小元素，然后放到已排序序列的末尾。
三、以此类推，直到所有元素均排序完毕。

public static void sort(){
        int[] ints = new int[]{8, 3, 1, 18, 12, 30};
        for (int i = 0; i < ints.length; i++) {
            int min = ints[i];
            for (int j = i+1; j < ints.length; j++) {
                if (min > ints[j]) {
                    int temp = ints[j];
                    ints[j] = min;
                    min = temp;
                }
            }
            ints[i] = min;
        }
        for (int a:ints) {
            System.err.println(a);
        }
    }

冒泡排序

算法步骤
一、比较相邻的元素，如果前一个比后一个大，就交换位置。
二、第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
三、第二趟将第二大的数移动至倒数第二位。
四、 重复n-1趟。

public static void sort(){
        int[] ints = new int[]{8, 3, 1, 18, 12, 30};
        for (int i = 0; i < ints.length; i++) {
            for (int j = i+1; j<ints.length; j++) {
                if (ints[j] < ints[i]){
                    int temp = ints[i];
                    ints[i] = ints[j];
                    ints[j] = temp;
                }
            }
        }
        for (int a:ints) {
            System.err.println(a);
        }
    }

归并排序

算法步骤
一、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
二、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
三、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
四、重复步骤三直到某一指针达到序列尾；
五、将另一序列剩下的所有元素直接复制到合并序列尾。

public static int[] sort(int[] ints){
        int[] arr = Arrays.copyOf(ints, ints.length);
        if (arr.length >= 2) {
            int middle = (int) Math.floor(arr.length / 2);

            int[] left = Arrays.copyOfRange(arr, 0, middle);
            int[] right = Arrays.copyOfRange(arr, middle, arr.length);

            return merge(sort(left), sort(right));
        }
        return arr;
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }

快速排序

算法步骤
一、从数列中挑出一个基准值。
二、将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
三、递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

private static void sort(int[] ints, int l, int r) {
        if (l < r) {
            int i, j, temp;
            i = l;
            j = r;
            temp = ints[i];

            while (i < j) {
                while (i<j && ints[j] > temp){
                    j--;
                }
                if (i<j){
                    ints[i++] = ints[j];
                }
                while (i<j && ints[j] < temp) {
                    i++;
                }
                if (i< j) {
                    ints[j--] = ints[i];
                }
            }
            ints[i] =temp;
            sort(ints, l, j -1);
            sort(ints, i+1, r);
        }
    }

堆排序

算法步骤
一、将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
二、将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
三、重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }