排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序。

而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

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

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

1. 冒泡排序

1.1 算法步骤

* 冒泡排序，每一趟排序都把最大的值留到了最后。每排序依一次就确定了一个值。
* 优化方案：如果某趟排序没有交换过位置，就说明已经有序了，可以提前结束排序。

1.2 动画演示

1.3 参考代码

public static void bubbleFun(int [] arr){
        for(int i=0;i<arr.length-1;i++){
            //检测是否发生交换
            boolean flag=false;
            //比较相邻的两个元素，大的放到后面，实现把最后的放到末尾
            for (int j = 0; j <arr.length-1-i ; j++) {
                if(arr[j]>arr[j+1]){
                    flag=true; //一旦进行交换，就把flag设置成true
                    int temp;
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
            }
            if(!flag){
                break;
            }
            System.out.println("排序"+i+"次后的序列");
            System.out.println(Arrays.toString(arr));
        }
    }

2. 选择排序

2.1 算法步骤

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.2 动画演示

2.3 参考代码

public static void chooseFun(int []arr){
        //这里需要进行n-1轮比较，最后一个自然就有序了
        for (int i = 0; i <arr.length-1 ; i++) {
            //初始化一个最小值的下标
            int min=i;
            for (int j = i+1; j <arr.length ; j++) {
                //循环查找最小值的所在的下标
                if (arr[j]<arr[min]){
                    min=j;
                }
            }
            //交换最小值到前面
            if(min!=i){
                int temp=arr[i];
                arr[i]=arr[min];
                arr[min]=temp;
            }
        }
    }

3. 插入排序

3.1 算法步骤

• 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

3.2 动画演示

3.3 参考代码

public static int[] insertFun(int []arrSrc){
        //对原数组进行拷贝，使排序不改变原数组的内容
        int []arr= Arrays.copyOf(arrSrc,arrSrc.length);
        //从第二个数开始，因为第一个数已经是一个有序的序列了
        for (int i = 1; i <arr.length ; i++) {
            //保存将要插入的值
            int temp=arr[i];
            //将要插入元素的前一个元素，也就是有序列表的最右边的一个元素的索引
            int index=i-1;
            //如果有序列表中的最后一个比待排序的大，则为待排序的找位置，否则不用动
            while(index>=0 && temp<arr[index]){
                //如果降到插入的元素小于有序表的最右边的元素
                //有序表最右边的元素后移，
                arr[index+1]=arr[index];
                // 然后更新index的值为，有序表的倒数第二个元素...
                index--;
            }           
            // 找到待插入的数的位置后插入，如果待插入的位置没有变化，说明待插入的值比有序列表最后一个
            //元素大，这时候不用管，直接比较下一个数就行了
           if(index+1!=i){
                arr[index+1]=temp;
            }
        }
        return arr;
    }

4. 希尔排序

4.1 算法步骤

• 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.

  选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

• 按增量序列个数 k，对序列进行 k 趟排序；

• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动画演示

4.3 参考代码

//交换方式的希尔排序
    public static int[] shellFun(int []arrSrc){
        int []arr= Arrays.copyOf(arrSrc,arrSrc.length);
        int temp=0;
        //第一个循环用于分组（确定步长）,每几个数一组步长就是几,这里采用的是每次÷2取整
        for (int gap = arr.length/2; gap >0 ; gap/=2) {
            //里面的两个循环用于处理每组内的数据交换，从gap开始表示的是第一个待比较数据
            //因为i-gap是有序序列的最后一个元素。
            for(int i=gap; i<arr.length;i++){
                //这里的j-=5单纯的是为了退出循环
                for(int j=i-gap;j>=0;j-=gap){
                    //这里是按照从小到大的顺序排列
                    if(arr[j]>arr[j+gap]){
                        temp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=temp;
                    }
                }
            }
        }
        return arr;
    }

//优化之后的希尔排序：使用移位和knuth序列(h从1开始，每次变为3h+1)
    public static int[] shellFun2(int []arrSrc){
        int[] arr=Arrays.copyOf(arrSrc,arrSrc.length);
        //使用knuth方式获取步长
        int gap=1;
        while(gap<arr.length){
            gap=gap*3+1;
        }
        while (gap>0){
            //找到待插入元素，因为每组的第一个元素为有序序列(i-gap),所以待插入元素从gap开始
            for(int i=gap;i<arr.length;i++){
                int temp=arr[i];
                int j=i-gap;
                //把待插入的元素插入到有序序列中
                while(j>=0&&temp<arr[j]){
                    arr[j+gap]=arr[j];
                    j-=gap;
                }
                if(j+gap!=i){
                    arr[j+gap]=temp;
                }
            }
            gap=(int)Math.floor(gap/3);
        }
        return arr;
    }

5. 归并排序

5.1 算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

• 重复步骤 3 直到某一指针达到序列尾；

• 将另一序列剩下的所有元素直接复制到合并序列尾。

  5.2 动画演示

  
  

  5.3 参考代码

public class MergeSort {
    public static int[]arrTemp;//辅助数组
    public static void main(String[] args) {
        int []arr={-1,2,-3,2,4,-5,8,7};
        System.out.println("归并排序后的序列"+Arrays.toString(sort(arr)));
    }
    public static int[] sort(int[] arrSrc){
        int[] arr= Arrays.copyOf(arrSrc,arrSrc.length);
        //定义辅助数组的长度
        arrTemp=new int[arr.length];
        int left=0;
        int right=arr.length-1;
        sort(arr,left,right);
        return arr;
    }
    //对数据进行分开
    public static void sort(int[] arr,int left,int right){
        //安全性校验，这里如果做了，后面的merge函数里面就不用再进行判定了
        if(right<=left){
            return ;
        }
        int mid=left+(right-left)/2;
        //对左边的进行递归分割
        sort(arr,left,mid);
        //对右边的进行递归分割
        sort(arr,mid+1,right);
       //对分割之后的数据进行合并（合并的时候进行比较排序）
        merge(arr,left,mid,right);
    }
    public static void merge(int[]arr,int left,int mid,int right){
        //左边的索引
        int p1=left;
        //右边的索引
        int p2=mid+1;
        //辅助数组的索引
        int i=left;
        while(p1<=mid&&p2<=right){
            if(arr[p1]<arr[p2]){
                arrTemp[i++]=arr[p1++];
            }else{
                arrTemp[i++]=arr[p2++];
            }
        }
        //如果其中一个数组已经遍历完了，直接把另一个数组剩下元素加入到辅助数组
        while(p1<=mid){
            arrTemp[i++]=arr[p1++];
        }
        while(p2<=right){
            arrTemp[i++]=arr[p2++];
        }
        //用辅助数组覆盖原数组
        for (int j = left; j <= right; j++) {
            arr[j]=arrTemp[j];
        }
    }
}

• 6. 快速排序

  6.1 算法步骤

• 从数列中挑出一个元素，称为 “基准”（pivot）;

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

6.2 动画演示

6.3 参考代码

public static int[] MySort (int[] arr) {
        // write code here
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    //快速排序
    public static void quickSort(int[]arr,int left,int right){
        if(left<right){
            int l=left,r=right,part=arr[left];
            while(l!=r){
                while(l<r&&arr[r]>=part){
                    r--;
                }
                if(l<r){
                    arr[l]=arr[r];  // 替换到左边,左边向前移动一下，避免重复比较了
                    l++;
                }
                while(l<r&&arr[l]<=part){
                    l++;
                }
                if(l<r){
                    arr[r]=arr[l];
                    r--;
                }
            }
            arr[l]=part; //基准元素找到自己的位置，基准元素的位置就是l
            quickSort(arr,left,l-1); //递归处理左边
            quickSort(arr,l+1,right); //递归处理右边
        }

    }

7. 堆排序

7.1 算法步骤

• 创建一个堆 H[0……n-1]；

• 把堆首（最大值）和堆尾互换；

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

• 重复步骤 2，直到堆的尺寸为 1。

7.2 动画演示

7.3 参考代码

public static void heapSort(int[]arr){
        //把数组构建成一个大顶堆，默认数组按照二叉树的层序遍历
        //从第一个非叶子节点开始构造,构造第一个大顶堆
        for (int i =(arr.length-2)/2 ; i >=0 ; i--) {
            maxHeap(arr,i,arr.length);
        }
        //使用堆进行排序
        for (int i = 1; i < arr.length; i++) {
            //首先交换已经排序好的第一个堆,把堆顶部元素交换到最后(其实每次都是把堆顶元素交换到最后)
            swap(arr,0,arr.length-i);
            //对交换之后的数组重新构造新的堆,长度每排序一次都会减少一次，其实第一次循环是对长度-1之后的数组进行构造大顶堆
            maxHeap(arr,0,arr.length-1-i);
        }
    }
    public static void swap(int[]arr,int i ,int j){
        arr[i]^=arr[j];
        arr[j]^=arr[i];
        arr[i]^=arr[j];
    }
    //index表示默认的最大值的位置
    public static void maxHeap(int[]arr,int index,int size){
        //index默认为最大值的位置，也就是跟节点,其左右孩子的位置为2*index+1,2*index+2
        int left=2*index+1;
        int right=left+1;
        int temp=index;//临时节点，为了方便判断index有没有改变
        //如果范围没问题的化，直接比较当前最大值和左右节点的大小，判断是否需要交换
        if(left<size&&arr[left]>arr[temp]){
            temp=left;// 令左节点为最大值的节点
        }
        if(right<size&&arr[right]>arr[temp]){
            temp=right; //令右节点为最大值节点
        }
        if(index!=temp){
            //如果改变，则需要交换最大值和当前模型最大值的位置，并且重新构造大顶推
            swap(arr,temp,index);
            maxHeap(arr,temp,size);
        }
    }

8. 计数排序

8.1 算法步骤

• 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max

• 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)

• 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

• 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

8.2 动画演示

8.3 参考代码

public static int[] getLeastNumbersCountNumSort(int[] arr, int k){
        //计算数据的最大值和最小值（可以解决负数的问题，同时节约空间）
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min=Math.min(min,arr[i]);
            max=Math.max(max,arr[i]);
        }
        int count=max-min;
        int[] temp =new int[count+1]; //定义数组的长度,用来存储下标对应元素的个数，如果没有该下标对应的数，那就是0
        //计数
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i]-min]+=1; //如果是负数，则减去最小值，移动到正数
        }
        //回填
        int j=0;
        //这里已经不需要原数组了，因为这里从0到temp.length已经包含了原数组的所有元素了
        for (int i = 0; i < temp.length; i++) {
            while (temp[i]!=0){
                temp[i]--;
                arr[j++]=i+min; //把之前减去的再加上
            }
        }
        return arr;
    }

9. 桶排序

9.1 算法步骤

• 设置固定数量的空桶。

• 把数据放到对应的桶中。

• 对每个不为空的桶中数据进行排序。

• 拼接不为空的桶中数据，得到结果

9.2 动画演示

9.3 参考代码

 1//Java 代码实现
 2public class BucketSort implements IArraySort {
 3
 4    private static final InsertSort insertSort = new InsertSort();
 5
 6    @Override
 7    public int[] sort(int[] sourceArray) throws Exception {
 8        // 对 arr 进行拷贝，不改变参数内容
 9        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
10
11        return bucketSort(arr, 5);
12    }
13
14    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
15        if (arr.length == 0) {
16            return arr;
17        }
18
19        int minValue = arr[0];
20        int maxValue = arr[0];
21        for (int value : arr) {
22            if (value < minValue) {
23                minValue = value;
24            } else if (value > maxValue) {
25                maxValue = value;
26            }
27        }
28
29        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
30        int[][] buckets = new int[bucketCount][0];
31
32        // 利用映射函数将数据分配到各个桶中
33        for (int i = 0; i < arr.length; i++) {
34            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
35            buckets[index] = arrAppend(buckets[index], arr[i]);
36        }
37
38        int arrIndex = 0;
39        for (int[] bucket : buckets) {
40            if (bucket.length <= 0) {
41                continue;
42            }
43            // 对每个桶进行排序，这里使用了插入排序
44            bucket = insertSort.sort(bucket);
45            for (int value : bucket) {
46                arr[arrIndex++] = value;
47            }
48        }
49
50        return arr;
51    }
52
         //自动扩容，并保存数据
55   
59    private int[] arrAppend(int[] arr, int value) {
60        arr = Arrays.copyOf(arr, arr.length + 1);
61        arr[arr.length - 1] = value;
62        return arr;
63    }
64
65}

10. 基数排序

10.1 算法步骤

• 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零

• 从最低位开始，依次进行一次排序

• 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

10.2 动画演示

10.3 参考代码

 1//Java 代码实现
 2public class RadixSort implements IArraySort {
 3
 4    @Override
 5    public int[] sort(int[] sourceArray) throws Exception {
 6        // 对 arr 进行拷贝，不改变参数内容
 7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 8
 9        int maxDigit = getMaxDigit(arr);
10        return radixSort(arr, maxDigit);
11    }
12
13    
14      //获取最高位数
15     
16    private int getMaxDigit(int[] arr) {
17        int maxValue = getMaxValue(arr);
18        return getNumLenght(maxValue);
19    }
20
21    private int getMaxValue(int[] arr) {
22        int maxValue = arr[0];
23        for (int value : arr) {
24            if (maxValue < value) {
25                maxValue = value;
26            }
27        }
28        return maxValue;
29    }
30
31    protected int getNumLenght(long num) {
32        if (num == 0) {
33            return 1;
34        }
35        int lenght = 0;
36        for (long temp = num; temp != 0; temp /= 10) {
37            lenght++;
38        }
39        return lenght;
40    }
41
42    private int[] radixSort(int[] arr, int maxDigit) {
43        int mod = 10;
44        int dev = 1;
45
46        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
47            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
48            int[][] counter = new int[mod * 2][0];
49
50            for (int j = 0; j < arr.length; j++) {
51                int bucket = ((arr[j] % mod) / dev) + mod;
52                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
53            }
54
55            int pos = 0;
56            for (int[] bucket : counter) {
57                for (int value : bucket) {
58                    arr[pos++] = value;
59                }
60            }
61        }
62
63        return arr;
64    }
65    private int[] arrayAppend(int[] arr, int value) {
66        arr = Arrays.copyOf(arr, arr.length + 1);
67        arr[arr.length - 1] = value;
68        return arr;
69    }
70}