排序算法

内排序(全部记录放在内存中)有可以分为以下几类：

(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
　　(2)、选择排序：简单选择排序、堆排序。
　　(3)、交换排序：冒泡排序、快速排序。
　　(4)、归并排序
　　(5)、基数排序

总结

二、平均时间复杂度
　　O(n^2):直接插入排序，简单选择排序，冒泡排序。
　　在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
　　O(nlogn):快速排序，归并排序，希尔排序，堆排序。
　　其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。
三、排序算法的选择
　　1.数据规模较小
　　（1）待排序列基本序的情况下，可以选择直接插入排序；
　　（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
　　2.数据规模不是很大
　　（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
　　（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
　　3.数据规模很大
　　（1）对稳定性有求，则可考虑归并排序。
　 （2）对稳定性没要求，宜用堆排序
　　4.序列初始基本有序（正序），宜用直接插入，冒泡

常见排序列表

快速排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 快速排序 时间复杂度为O(nlogn)， 不稳定
 * 当n较大时使用快排比较好，当序列基本有序时用快排反而不好。
 * 基本思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 *
 * Created by weiyongjun on 2020/7/16
 */
public class QuickSort {

    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3, 0};
        quickSort(ar);
        System.out.println(1);
    }

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }
    
    private static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pos = getPosition(array, left, right);
        quickSort(array, left, pos - 1);
        quickSort(array, pos + 1, right);
    }

    //优化后的实现，不需要swap交换
    private static int getPosition(int[] array, int left, int right) {
        int temp = array[left];
        while (left < right) {
            while (left < right && array[right] >= temp) {
                right--;
            }
            if (left < right) {
                array[left++] = array[right];
            }
            while (left < right && array[left] <= temp) {
                left++;
            }
            if (left < right) {
                array[right--] = array[left];
            }
        }
        array[left] = temp;
        return left;
    }
}

归并排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 归并排序 归并排序是稳定的排序方法。 　　
 * 归并排序的时间复杂度为O(nlogn)。空间复杂度O(n) 　　
 * 速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
思想：是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
 * Created by weiyongjun on 2020/7/16
 */
public class MergeSort {

    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3};
        mergeSort(ar);
        System.out.println(1);
    }

    public static void mergeSort(int[] array) {
        mergeSort(array, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;//防止越界
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid + 1, right);
        }
    }

    //归并排序，需要一个辅助数组，最后将辅助数组赋值回去
    private static void merge(int[] array, int leftP, int rightP, int rightB) {
        int[] temp = new int[rightB - leftP + 1];
        int mid = rightP - 1;
        int i = leftP;
        int j = rightP;
        int k = 0;
        while (i <= mid && j <= rightB) {
            temp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        while (j <= rightB) {
            temp[k++] = array[j++];
        }
        for (int m = 0; m < temp.length; m++) {
            array[leftP + m] = temp[m];
        }
    }
}

冒泡排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 冒泡排序
 * Created by weiyongjun on 2020/7/15
 * 是一种稳定的排序算法，平均时间复杂度O(n^2),最好时间复杂度O(n)
 * 基本思想就是：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
 */
public class BubbleSort {
    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3};
        bubbleSort(ar);
        System.out.println(1);
    }

    //这个代码，无论什么情况下，时间复杂度都是O(n^2)。下面有优化后的代码，时间复杂度为O(n)
    public static void bubbleSort(int[] array) {
        for(int i=array.length-1 ;i>0;i--) {
            for(int j=0;j<i;j++) {
                swap(array, j, j+1);
            }
        }
    }

    private static void swap(int[] array, int i,int j) {
        if(array[j] <array[i]) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    //优化后的代码，能够实现在最好时间复杂度为O(n)
    public void bubbleSortB(int[] arr) {
        boolean didSwap;
        for(int i = 0, len = arr.length; i < len - 1; i++) {
            didSwap = false;
            for(int j = 0; j < len - i - 1; j++) {
                if(arr[j + 1] < arr[j]) {
                    swap(arr, j, j + 1);
                    didSwap = true;
                }
            }
            if(didSwap == false) {
                return;
            }
        }
    }

}

堆排序

package com.spring.boot.demo.algorithm.sort;

/**
 * Created by weiyongjun on 2020/7/23
 * 原理分析可以看这个。https://www.cnblogs.com/chengxiao/p/6129630.html
 * 代码实现看自己的就可以了
 * 理解了题意以后，只需要稍微改变几个判断就可以完成从最大堆到最小堆
 */
import java.util.Arrays;

//堆的一个规律就是i节点的父节点下标是(i-1)/2,他的左右子节点下表分别是2*i+1和2*i+2；
public class DumpSort {
    public static void main(String[] args) {
       // int[] a={49,38,65,97,76,13,27,49,78,34,12,64};
        int[] a={4,6,8,5,9};
        int arrayLength=a.length;
        //循环建堆
        for(int i=0;i<arrayLength-1;i++) {
            //建堆
            buildMaxHeap(a,arrayLength-1-i);
            //交换堆顶和最后一个元素
            swap(a,0,arrayLength-1-i);
            System.out.println(Arrays.toString(a));
        }
    }
    //对data数组从0到lastIndex建大顶堆
    public static void buildMaxHeap(int[] data, int lastIndex){
        //从lastIndex处节点（最后一个节点）的父节点开始
        for(int i=(lastIndex-1)/2;i>=0;i--){//在它之前的肯定都是父节点，之后的肯定都只是子节点
            //k保存正在判断的节点 ,即正在判断的这个父节点
            int k=i;//采用临时变量来记录i的值
            //如果当前k节点的子节点存在，有可能只存在左节点，所以用k*2+1来比较
            while(k*2+1<=lastIndex){
                //k节点的左子节点的索引
                int biggerIndex=2*k+1;
                //如果biggerIndex小于lastIndex(最后一个节点)，即biggerIndex+1代表的k节点的右子节点存在
                if(biggerIndex<lastIndex){//说明有右节点
                    //如果右子节点的值较大
                    if(data[biggerIndex]<data[biggerIndex+1]){
                        //biggerIndex总是记录较大子节点的索引
                        biggerIndex++;
                    }
                }
                //如果k节点的值小于其较大的子节点的值
                if(data[k]<data[biggerIndex]){//将最大的值放到父节点，他也是下次某个循环的子节点值，也就是每次从一个小三角找到最大值，存在父节点，
                    //交换他们
                    swap(data,k,biggerIndex);
                    //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    //k=biggerIndex;//用来跳出循环 ,如果没有这句话的话，会再执行一遍从else那跳出去
                }else{
                    break;
                }
            }
        }
    }
    //交换
    private static void swap(int[] data, int i, int j) {
        int tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
}

计数排序

package com.spring.boot.demo.algorithm.sort;

/** 计数排序
 * 适合量大但是范围小， 时间和空间复杂度 O(n+k) 稳定排序，非比较排序
 * 计数排序很好的一个参考链接：https://mp.weixin.qq.com/s/Tq-hUeNv-wrF-hjKoA4nfw
 * Created by weiyongjun on 2020/7/17
 */
public class CountingSort {
    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3,0};
        countingSort(ar);
        System.out.println(1);
    }

    public static void countingSort(int[] array) {
        int max = array[0];
        int min = array[0];
        //先找数组中的最大值和最小值
        for(int i=1;i< array.length;i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }

        //统计个数
        int[] count = new int[max-min+1];
        for(int i=0;i< array.length;i++) {
            count[array[i]-min]++;
        }
        //变形，通过变形可以变成稳定排序
        for(int i=1;i< count.length;i++) {
            count[i] = count[i] + count[i-1];
        }
        int[] result = new int[array.length];
        for(int i= array.length-1;i>=0;i--) {
            result[count[array[i]-min]-1] = array[i];
            count[array[i]-min]--;
        }
        System.arraycopy(result,0,array,0, array.length);
    }
}

插入排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 插入排序(对于基本有序的数组最好用)
 * 思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。 平均时间复杂度：O(n^2) 空间复杂度O(1)
 * 稳定 Created by weiyongjun on 2020/7/15
 */
public class InsertSort {

    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3};
        //  directSort(ar);
        new BinaryInsertSort().binarySort(ar);
        System.out.println(1);
    }


    //直接插入排序
    public static void directSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }

    //对直接插入排序的优化，不需要进行swap交换
    public void directSortB(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];//这样就不需要每次比较的时候都移动temp值
            int j;//因为for循环外面还需要用到j的值，因此不能在for循环里面定义j
            for (j = i - 1; j >= 0; j--) {
                if (temp < array[j]) {
                    //如果后一个小于前一个，则把前一个的值赋给后一个，且前一个的值不需要变化。因为始终使用temp在做比较
                    array[j + 1] = array[j];
                    //最后将temp放置到不满足条件的那个值得后面
                } else {
                    break;
                }

            }
            array[j + 1] = temp;
        }
    }

    //二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)。
    //二分插入排序
    static class BinaryInsertSort {

        public void binarySort(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int temp = array[i];//每次循环就是确定temp在数组中的位置
                int left = 0;
                int mid = 0;
                int right = i - 1;
                while (left <= right) {//先找到temp在数组0-i之间的位置，后面再移动数组来插入元素。
                    //每次插入的位置为最后循环结束后left或者right+1(表示顺序没变，就在原位置也就相当于最后的left=i)的位置，
                    mid = (left + right) / 2;
                    if (array[mid] > temp) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                for (int j = i - 1; j >= left; j--) {//将left后的值全部往后移一位，然后把temp放在left的位置
                    array[j + 1] = array[j];
                }
                //表示i处的值移动了
                if (left != i) {
                    array[left] = temp;
                }
            }
        }
    }
}

选择排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 选择排序
 * 基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
 * 平均时间复杂度：O(n^2)  空间复杂度O(1)  不稳定
 * Created by weiyongjun on 2020/7/15
 */
public class SelectSort {

    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3};
        selectSort(ar);
        System.out.println(1);
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minPos = i;
            for (int j = i + 1; j < array.length; j++) {
                minPos = array[minPos] > array[j] ? j : minPos;
            }
            swap(array, i, minPos);
        }

    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

基数排序

package com.spring.boot.demo.algorithm.sort;

import java.util.ArrayList;

/**
 * 基数排序  有序排序 时间复杂度：O(n * k)
 * 多关键字排序 用于大量数，很长的数进行排序时。
 * 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
 * Created by weiyongjun on 2020/7/17
 */
public class RadixSort {

    public static int[] RadixSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        // 1.先算出最大数的位数；
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        //定义0-9的一个数组，分别存储对应位的值。比如151 刚开始个位为1，则放到第二个list里面
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                //先计算个位的值，放入对应数组
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                //把list的值取出来，复制给array，则第一遍以后，array
                //里面的值都是按照个位排好序的
                for (int k = 0; k < bucketList.get(j).size(); k++) {
                    array[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
        return array;
    }

}

希尔排序

package com.spring.boot.demo.algorithm.sort;

/**
 * 希尔排序 不常用，仅作为记录. 不稳定排序 时间复杂度：O(n^1.3) 
 * Created by weiyongjun on 2020/7/15
 */
public class ShellSort {

    public static void main(String[] a) {
        int[] ar = new int[]{5, 2, 1, 3};
        shellSort(ar);
        System.out.println(1);
    }

    public static void shellSort(int[] array) {
        int h = 1;
        //这个间隔的计算是有专门的算法来验证的
        while (h <= array.length / 3) {
            h = h * 3 + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            for (int i = gap; i < array.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (array[j] < array[j - gap]) {
                        swap(array, j, j - gap);
                    }
                }
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

马老师的一首诗