1、排序（Sort Algorithm）

1、排序（Sort Algorithm）

1、概念

排序也称排序算法（Sort Algorithm）排序是将一组数据，依指定的顺序进行排列的过程

2、排序的分类

1、内部排序

把需要排序的数据加载到内存中进行排序

2、外部排序

借助外部存储（文件等）进行排序

3、常见的排序算法分类

3、算法的时间复杂度

1、度量一个程序执行时间的两种方法

1、事后统计的方法

可行但是存在两个问题

需要实际运行该程序
需要在同一台计算器的相同状态下运行，才能比较
2、事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优
4、时间频度
1、介绍
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。[举例说明]

2、举例说明-基本案例

1、忽略常数项

结论：

1) 2n+20 和 2n 随着 n 变大，执行曲线无限接近,20可以忽略
2) 3n+10 和 3n 随着 n 变大，执行曲线无限接近,10可以忽略

2、忽略低次项

结论：
1) 2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近，可以忽略 3n+10
2) n^2+5n+20 和 n<2 随着 n 变大,执行曲线无限接近,可以忽略 5n+20

3、忽略系数

结论：
1) 随着 n值变大，5n^2+7n和3n^2+2n，执行曲线重合，说明这种情况下,5和3可以忽略。
2）而n^3+5n 和 6n^3+4n，执行曲线分离，说明多少次方式关键

3、时间复杂度
1)一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n的某个函数，用 T(n)表示，若有某个辅助函数 f（n），使得当 n 趋近于无穷大时，T(n)/ f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=O（f(n))，称O（f(n)）为算法的渐进时间复杂度，简称时间复杂度。
2) T(n)不同，但时间复杂度可能相同。如：T(n)=m2+7n+6 与 T(n)=3m2+2n+2 它们的 T(n)不同，但时间复杂度相同，都为O(n2)。
3)计算时间复杂度的方法：
- 用常数1 代替运行时间中的所有加法常数 T(n)=n2+7n+6 => T(n)=n2+7n+1
- 修改后的运行次数函数中，只保留最高阶项 T(n)=n2+7n+1=>T(n)=n2
- 去除最高阶项的系数 T(n)= n2=> T(n)= n2=> O(n2)
  4、常见的时间复杂度
1)常数阶 O(1)
2)对数阶 0(log2n)
3)线性阶 O(n)
4)线性对数阶O(nlog2n)
5)平方阶 O(n^2)
6)立方阶 O(n^3)
7)k 次方阶 O(n^k)
8)指数阶 O(2^n)
5、常见的时间复杂度对应的图

说明：

1)常见的算法时间复杂度由小到大依次为：O(1)< O(log2n)< O(n)< O(nlog2n)< O(n2)< O(n3)< O(nk)<O(2n)，随着问题规模N的不断增大，上述时间复杂度不断增大，算法的执行效率越低
2) 从图中可见，我们应该尽可能避免使用指数阶的算法

1、常数阶O（1）

2、对数阶O(log2n)

3、线性阶O(n)

4、线性对数阶O(nlog2n)

5、平方阶O(n2)

6、立方阶O(n3)、K次方阶O(nk)
说明：参考上面的O(n2)去理解就好了，O(n3)相当于三层n循环，其他的类似

6、平均时间复杂度和最坏时间复杂度
1) 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2) 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
3) 平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:)。

5、算法的空间复杂度简介

1、基本介绍

1) 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n的函数。
2) 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n有关，它随着n的增大而增大，当n 较大时，将占用较多的存储单元，例如快速排序和归并排序算法,基数排序就属于这种情况
3)在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

6、冒泡排序(Bubble Sorting)

1、思想

1、逻辑
通过对待排序序列从前向后（从下标较小的元素开始），
依次比较相邻元素的值，若发现逆序则交换。
较大的元素逐渐从前移向后部，就像水底下的气泡一样逐件向上冒

2、优化
如果一辆比较下来没有进行过交换，就说明顺序有序，就不需进行更多的排序了。

2、演示

小结上面的图解过程;
(1) 一共进行数组的大小-1 次大的循环
(2)每一趟排序的次数在逐渐的减少
(3)如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化
3、代码实现
1、创建Sort接口
```java package com.daijunyi.structure.sort;

/**

@author djy
@createTime 2022/1/6 上午11:43
@description */

public interface Sort {

<T extends Comparable<T>> void sort(T[] source);

}

<a name="LPUak"></a>
#### 2、添加工具类
```java
package com.daijunyi.structure.sort;

import java.util.Arrays;

/**
 * @author djy
 * @createTime 2022/1/6 下午1:37
 * @description 排序工具类
 */
public class SortUtil {

    /**
     * 获取随机数
     * @param size
     * @return
     */
    public static Integer[] getRandomInteger(int size){
        Integer[] integers = new Integer[size];
        for (int i=0;i<size;i++){
            integers[i] = (int)(Math.random()*size);
        }
        return integers;
    }

    /**
     * 排序测试
     * @param sort
     */
    public static void smallTest(Sort sort){
        Integer[] array = {3,9,-1,10,20};
        System.out.println("排序前："+ Arrays.toString(array));
        sort.sort(array);
        System.out.println("排序后："+Arrays.toString(array));
    }

    /**
     * 8万个数据测试 时间
     * @param sort
     */
    public static void bigTest(Sort sort){
        int size = 80000;
        Integer[] arrayMax = SortUtil.getRandomInteger(size);
        System.out.println("开始排序"+size+"万个数据");
        long start = System.currentTimeMillis();
        sort.sort(arrayMax);
        long m = (System.currentTimeMillis()-start)/1000;
        System.out.println("排序时间:"+m+"秒");
    }

}

3、冒泡排序主程序

/**
 * @author djy
 * @createTime 2022/1/6 上午11:41
 * @description 冒泡排序 从低位依次对比大的往后移动
 */
public class BubbleSort implements Sort{

    @Override
    public <T extends Comparable<T>> void sort(T[] source) {
        T tmp = null;
        boolean flag = false;
        for (int i=0;i<source.length-1;i++){
            for (int j=0;j<source.length-1-i;j++){
                Comparable front = source[j];
                Comparable rear = source[j + 1];
                if(front.compareTo(rear) > 0){
                    tmp = (T)front;
                    source[j] = (T)rear;
                    source[j+1] = tmp;
                    flag = true;
                }
            }
            if (flag == false){
                break;
            }
            flag = false;
        }
    }
}

4、测试

class BubbleSortMain{
    public static void main(String[] args) {
        SortUtil.smallTest(new BubbleSort());
        SortUtil.bigTest(new BubbleSort());
    }
}

5、结果

排序前：[3, 9, -1, 10, 20]
排序后：[-1, 3, 9, 10, 20]
开始排序80000万个数据
排序时间:30秒

7、选择排序（Selection Sort）

1、思想

第一次从arr[0]-arr[n-1]中选择最小数与arr[0]交换
第二次从arr[1]-arr[n-1]中选取最小数与arr[1]交换
。。。。
第n-1次从arr[n-2]-array[n-1]中选取最小值，与array[n-2]交换
总共通过n-1次
2、思路分析图

3、代码实现
1、创建SelectionSort
```java

/**

@author djy
@createTime 2022/1/6 下午5:08

@description */ public class SelectionSort implements Sort{ @Override public > void sort(T[] source) {

 if (source == null || source.length <= 1){
     return;
 }
 int index;
 T tmp;
 for (int i=0;i<source.length-1;i++){
     tmp = source[i];
     index = i;
     for (int j=i;j<source.length;j++){
         if (tmp.compareTo(source[j]) > 0){
             tmp = source[j];
             index = j;
         }
     }
     if (index != i){
         source[index] = source[i];
         source[i] = tmp;
     }
 }

} }

<a name="BtIEm"></a>
#### 2、测试
```shell
排序前：[3, 9, -1, 10, 20, 1, 2, 3, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 10, 20]
开始排序80000万个数据
排序时间:7秒

8、插入排序（Insertion Sort）

1、思想

把待排序的数组看成一个有序的表，也看成是一个无序表
开始时有序表中只包含一个元素，无序表中包含有n-1个元素，
排序过程每次从无序表中取一个元素插入到有序表的合适位置，
进行n-1次插入
2、思路图

3、代码实现
1、代码实现
```java package com.daijunyi.structure.sort;

class InsertionSortMain { public static void main(String[] args) { SortUtil.smallTest(new InsertionSort()); SortUtil.bigTest(new InsertionSort()); } }

/**

@author djy
@createTime 2022/1/7 上午11:47
@description 插入排序法 */ public class InsertionSort implements Sort {

/**
- ● 把待排序的数组看成一个有序的表，也看成是一个无序表
- ● 开始时有序表中只包含一个元素，无序表中包含有n-1个元素，
- ● 排序过程每次从无序表中取一个元素插入到有序表的合适位置，
- ● 进行n-1次插入
- @param source
- @param */ @Override public > void sort(T[] source) {
  
  for (int i = 1; i < source.length; i++) {
```
 //从前头开始先找到插入位置，然后再从后面右移
```
  // for (int j = 0;jj;k—){ // source[k] = source[k-1]; // } // source[j] = tmp; // break; // } // }
```
 //后头开始移动，并且直接找到位置之后，就插入
 T insertValue = source[i];
 int insertIndex = i-1;
 while (insertIndex >= 0 && insertValue.compareTo(source[insertIndex]) < 0){
     source[insertIndex+1] = source[insertIndex];
     insertIndex--;
 }
 if (insertIndex+1 != i){
     source[insertIndex+1] = insertValue;
 }
```
  } } }

<a name="L284L"></a>
#### 2、结果
```shell
排序前：[3, 9, -1, 10, 20]
排序后：[-1, 3, 9, 10, 20]
开始排序80000万个数据
排序时间:7秒

9、希尔排序（Donald Shell Sort）

1、简单插入排序存在的问题

我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数1(最小), 这样的过程是：

结论：当需要插入的数是较小的数时，后移的次数明显多，对效率有影响

2、介绍

希尔排序是希尔（Donald Shell）1959年提出的算法。希尔算法也是一种插入算法，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

3、思想

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

4、图解

5、代码实现

1、实现

package com.daijunyi.structure.sort;

class DonaldShellSortMain {
    public static void main(String[] args) {
        SortUtil.smallTest(new DonaldShellSort());
        SortUtil.middleTest(new DonaldShellSort());
        SortUtil.bigTest(new DonaldShellSort());
    }
}

/**
 * @author djy
 * @createTime 2022/1/7 下午3:35
 * @description 希尔排序  插入排序的一种高效版本
 */
public class DonaldShellSort implements Sort {

    /**
     * 希尔排序是把记录按下标的一定增量分组，
     * 对每组使用直接插入排序算法排序，随着增量渐渐减少，
     * 每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，最后排序一次，算法便终止。
     *
     * @param source
     * @param <T>
     */
    @Override
    public <T extends Comparable<T>> void sort(T[] source) {
        T tmp;
        //增量值
        for (int gap = source.length / 2; gap > 0; gap /= 2) {
            //分组的最后一排数据
            for (int i = gap; i < source.length; i++) {
//                //这里使用了交换 效率反而慢
//                for (int j = i - gap; j >= 0; j -= gap) {
//                    if (source[j].compareTo(source[j + gap]) > 0) {
//                        tmp = source[j];
//                        source[j] = source[j + gap];
//                        source[j + gap] = tmp;
//                    }
//                }
                //优化使用 改成插入
                int j = i;
                tmp = source[j];
                while (j-gap >= 0 && tmp.compareTo(source[j-gap]) < 0){
                    source[j] = source[j-gap];
                    j = j-gap;
                }
                source[j] = tmp;
            }
        }
    }
}

2、测试

排序前：[3, 9, -1, 10, 20, 1, 2, 3, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 10, 20]
开始排序100个数据
排序前：[21, 14, 85, 57, 28, 54, 19, 75, 22, 17, 19, 98, 80, 88, 37, 15, 15, 30, 20, 21, 82, 88, 42, 76, 29, 66, 85, 57, 1, 53, 26, 28, 6, 76, 2, 21, 72, 53, 30, 23, 38, 51, 55, 91, 12, 79, 52, 41, 33, 5, 29, 6, 40, 62, 88, 20, 25, 71, 1, 78, 14, 41, 63, 92, 70, 81, 52, 1, 54, 30, 31, 99, 99, 29, 42, 94, 16, 35, 70, 77, 11, 46, 25, 30, 47, 13, 96, 24, 41, 9, 8, 27, 12, 61, 65, 88, 26, 81, 62, 95]
排序后：[1, 1, 1, 2, 5, 6, 6, 8, 9, 11, 12, 12, 13, 14, 14, 15, 15, 16, 17, 19, 19, 20, 20, 21, 21, 21, 22, 23, 24, 25, 25, 26, 26, 27, 28, 28, 29, 29, 29, 30, 30, 30, 30, 31, 33, 35, 37, 38, 40, 41, 41, 41, 42, 42, 46, 47, 51, 52, 52, 53, 53, 54, 54, 55, 57, 57, 61, 62, 62, 63, 65, 66, 70, 70, 71, 72, 75, 76, 76, 77, 78, 79, 80, 81, 81, 82, 85, 85, 88, 88, 88, 88, 91, 92, 94, 95, 96, 98, 99, 99]
排序时间:0秒
开始排序800000个数据
排序时间:0秒

10、快速排序（Quick Sort）

1、介绍

快速排序（QuickSort）是对冒泡排序的一种改进。

2、基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

2、填坑法

1、思想与图解

2、代码实现

package com.daijunyi.structure.sort;

class QuickSortMain {
    public static void main(String[] args) {
        SortUtil.smallTest(new QuickPitSort());
        SortUtil.middleTest(new QuickPitSort());
        SortUtil.bigTest(new QuickPitSort());
    }
}

/**
 * @author djy
 * @createTime 2022/1/8 上午9:35
 * @description 快速排序之填坑
 */
public class QuickPitSort implements Sort {

    /**
     * 填坑法
     * @param source
     * @param <T>
     */
    @Override
    public <T extends Comparable<T>> void sort(T[] source) {
        sort(source, 0, source.length - 1);
    }

    private <T extends Comparable> void sort(T[] source, int left, int right) {
        if (left < right) {
            int start = left,end = right;
            T pivot = source[left];
            while (start < end){
                //从后部开始找到比标兵值小的
                while (start < end && source[end].compareTo(pivot) >= 0){
                    end--;
                }
                //把找到的小于标兵的值，复制给坑位，然后小的值的位置变成新的坑位
                source[start] = source[end];
                //从前面找到比标兵大的，复制给坑位
                while (start < end && source[start].compareTo(pivot) <= 0){
                    start++;
                }
                source[end] = source[start];
            }
            //把标兵复制给最后一个坑位
            source[start] = pivot;
            //对标兵左边递归快速排序
            sort(source,left,start-1);
            //对标兵右边递归快速排序
            sort(source,start+1,right);
        }
    }

}

结果

排序前：[3, 9, -1, 30, 20, 1, 3, 2, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 20, 30]
开始排序100个数据
排序前：[70, 20, 27, 5, 17, 68, 5, 0, 96, 4, 81, 89, 20, 89, 25, 29, 2, 58, 6, 58, 27, 22, 34, 43, 9, 2, 68, 65, 83, 11, 13, 53, 61, 71, 54, 5, 80, 21, 57, 61, 34, 25, 18, 36, 5, 8, 9, 68, 59, 72, 57, 55, 36, 78, 36, 31, 55, 23, 62, 60, 18, 65, 24, 87, 98, 9, 23, 33, 40, 83, 79, 6, 70, 26, 3, 8, 75, 10, 40, 57, 68, 0, 87, 32, 71, 30, 65, 91, 50, 74, 84, 29, 2, 37, 40, 71, 74, 69, 44, 14]
排序后：[0, 0, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 6, 8, 8, 9, 9, 9, 10, 11, 13, 14, 17, 18, 18, 20, 20, 21, 22, 23, 23, 24, 25, 25, 26, 27, 27, 29, 29, 30, 31, 32, 33, 34, 34, 36, 36, 36, 37, 40, 40, 40, 43, 44, 50, 53, 54, 55, 55, 57, 57, 57, 58, 58, 59, 60, 61, 61, 62, 65, 65, 65, 68, 68, 68, 68, 69, 70, 70, 71, 71, 71, 72, 74, 74, 75, 78, 79, 80, 81, 83, 83, 84, 87, 87, 89, 89, 91, 96, 98]
排序时间:0秒
开始排序8000000个数据
排序时间:3秒

3、交换法

1、思想和图解

2、代码实现

```java package com.daijunyi.structure.sort.quick;

import com.daijunyi.structure.sort.Sort; import com.daijunyi.structure.sort.SortUtil;

class QuickSwapSortMain { public static void main(String[] args) { SortUtil.smallTest(new QuickSwapSort()); SortUtil.middleTest(new QuickSwapSort()); SortUtil.bigTest(new QuickSwapSort()); } }

/**

@author djy
@createTime 2022/1/8 下午2:51

@description 快速排序交换方式 */ public class QuickSwapSort implements Sort {

@Override public > void sort(T[] source) {

 sort(source, 0, source.length - 1);

}

public > void sort(T[] source, int left, int right) {

 if (left < right){
     T pivot = source[(left + right) / 2];
     int start = left;
     int end = right;
     while (start < end) {
         while (start < end && source[start].compareTo(pivot) <= 0) {
             start++;
         }
         while (start < end && source[end].compareTo(pivot) >= 0) {
             end--;
         }
         swap(source, start, end);
     }
     swap(source,start,(left + right) / 2);
     sort(source,left,start-1);
     sort(source,start+1,right);
 }

}

public > void swap(T[] source, int left, int right) {

 T tmp = source[left];
 source[left] = source[right];
 source[right] = tmp;

} }

<a name="xmJi1"></a>
#### 3、结果
```java
排序前：[3, 9, -1, 30, 20, 1, 3, 2, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 20, 30]
开始排序100个数据
排序前：[6, 53, 75, 23, 22, 69, 57, 95, 0, 62, 87, 6, 91, 61, 50, 28, 32, 47, 75, 13, 72, 73, 60, 59, 25, 53, 71, 59, 0, 91, 13, 57, 62, 47, 14, 92, 24, 38, 32, 98, 57, 59, 61, 10, 72, 37, 66, 81, 21, 9, 57, 71, 42, 82, 88, 39, 59, 61, 27, 23, 26, 76, 38, 96, 32, 96, 95, 93, 41, 44, 24, 99, 61, 19, 62, 91, 34, 38, 30, 28, 52, 27, 77, 37, 90, 85, 83, 65, 93, 2, 96, 17, 36, 49, 70, 65, 17, 13, 13, 4]
排序后：[0, 0, 2, 4, 6, 6, 9, 10, 13, 13, 13, 13, 14, 17, 17, 19, 21, 22, 23, 23, 24, 24, 25, 26, 27, 27, 28, 28, 30, 32, 32, 32, 34, 36, 37, 37, 38, 38, 38, 39, 41, 42, 44, 47, 47, 49, 50, 52, 53, 53, 57, 57, 57, 57, 59, 59, 59, 59, 60, 61, 61, 61, 61, 62, 62, 62, 65, 65, 66, 69, 70, 71, 71, 72, 72, 73, 75, 75, 76, 77, 81, 82, 83, 85, 87, 88, 90, 91, 91, 91, 92, 93, 93, 95, 95, 96, 96, 96, 98, 99]
排序时间:0秒
开始排序80000个数据
排序时间:0秒

4、单指针交换

1、思想

单指针交换是代码量最少的
这里的单指针意思是定了一个，而动另一个
较少的比较和交换
2、代码
```java package com.daijunyi.structure.sort.quick;

import com.daijunyi.structure.sort.Sort; import com.daijunyi.structure.sort.SortUtil;

class QuickSingleSwapSortMain{ public static void main(String[] args) { SortUtil.smallTest(new QuickSingleSwapSort()); SortUtil.middleTest(new QuickSingleSwapSort()); SortUtil.bigTest(new QuickSingleSwapSort()); } } /**

@author djy
@createTime 2022/1/8 下午4:08
@description 单指针交换方式
单指针交换是代码量最少的
这里的单指针意思是定了一个，而动另一个

较少的比较和交换 */ public class QuickSingleSwapSort implements Sort {

@Override public > void sort(T[] source) {

 sort(source,0,source.length-1);

}

public > void sort(T[] source,int l,int r) {

 if(l<r){
     T pivot = source[l];
     int index=l;
     for(int i=l+1;i<=r;i++){
         if(source[i].compareTo(pivot)<0) {
             ++index;
             swap(source, i, index);
         }
     }
     swap(source,l,index);
     sort(source,l,index-1);
     sort(source,index+1,r);
 }

}

public > void swap(T[] source, int left, int right) {

 T tmp = source[left];
 source[left] = source[right];
 source[right] = tmp;

} }

<a name="IEAgr"></a>
#### 4、结果
```shell
排序前：[3, 9, -1, 30, 20, 1, 3, 2, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 20, 30]
开始排序100个数据
排序前：[55, 18, 27, 74, 51, 68, 55, 2, 94, 99, 83, 33, 80, 51, 87, 65, 24, 80, 66, 82, 18, 10, 64, 78, 51, 14, 61, 9, 17, 54, 16, 21, 62, 51, 82, 37, 45, 12, 34, 84, 78, 1, 48, 60, 95, 89, 44, 68, 13, 78, 47, 64, 33, 66, 69, 98, 74, 82, 95, 48, 82, 80, 75, 99, 41, 74, 68, 28, 42, 57, 13, 29, 4, 23, 67, 22, 98, 10, 97, 64, 55, 53, 30, 17, 40, 20, 91, 70, 47, 21, 11, 89, 36, 43, 90, 21, 84, 84, 94, 16]
排序后：[1, 2, 4, 9, 10, 10, 11, 12, 13, 13, 14, 16, 16, 17, 17, 18, 18, 20, 21, 21, 21, 22, 23, 24, 27, 28, 29, 30, 33, 33, 34, 36, 37, 40, 41, 42, 43, 44, 45, 47, 47, 48, 48, 51, 51, 51, 51, 53, 54, 55, 55, 55, 57, 60, 61, 62, 64, 64, 64, 65, 66, 66, 67, 68, 68, 68, 69, 70, 74, 74, 74, 75, 78, 78, 78, 80, 80, 80, 82, 82, 82, 82, 83, 84, 84, 84, 87, 89, 89, 90, 91, 94, 94, 95, 95, 97, 98, 98, 99, 99]
排序时间:0秒
开始排序80000个数据
排序时间:0秒

5、填坑排序优化

1、思想

优化填坑相比于填坑，减少了比较次数指针移动更加快了没有交换，减少了比较

2、代码实现

package com.daijunyi.structure.sort.quick;

import com.daijunyi.structure.sort.Sort;
import com.daijunyi.structure.sort.SortUtil;

class QuickPitOptimizeSortMain {
    public static void main(String[] args) {
        SortUtil.smallTest(new QuickPitOptimizeSort());
        SortUtil.middleTest(new QuickPitOptimizeSort());
        SortUtil.bigTest(new QuickPitOptimizeSort());
    }
}

/**
 * @author djy
 * @createTime 2022/1/8 下午4:34
 * @description 填坑优化排序
 */
public class QuickPitOptimizeSort implements Sort {
    @Override
    public <T extends Comparable<T>> void sort(T[] source) {
        sort(source, 0, source.length - 1);
    }

    /**
     * 优势是减少一次比较
     * @param source
     * @param l
     * @param r
     * @param <T>
     */
    public <T extends Comparable<T>> void sort(T[] source, int l, int r) {
        if (l < r) {
            int i = l, j = r;
            T pivot = source[l];
            while (i < j) {
                while (i < j && source[j].compareTo(pivot) >= 0) {
                    j--;
                }
                if (i < j) {
                    source[i++] = source[j];
                }
                while (i < j && source[i].compareTo(pivot) <= 0) {
                    i++;
                }
                if (i < j) {
                    source[j--] = source[i];
                }
            }
            source[i] = pivot;
            sort(source, i + 1, r);
            sort(source, l, i - 1);
        }
    }
}

3、结果

排序前：[3, 9, -1, 30, 20, 1, 3, 2, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 20, 30]
开始排序100个数据
排序前：[55, 18, 27, 74, 51, 68, 55, 2, 94, 99, 83, 33, 80, 51, 87, 65, 24, 80, 66, 82, 18, 10, 64, 78, 51, 14, 61, 9, 17, 54, 16, 21, 62, 51, 82, 37, 45, 12, 34, 84, 78, 1, 48, 60, 95, 89, 44, 68, 13, 78, 47, 64, 33, 66, 69, 98, 74, 82, 95, 48, 82, 80, 75, 99, 41, 74, 68, 28, 42, 57, 13, 29, 4, 23, 67, 22, 98, 10, 97, 64, 55, 53, 30, 17, 40, 20, 91, 70, 47, 21, 11, 89, 36, 43, 90, 21, 84, 84, 94, 16]
排序后：[1, 2, 4, 9, 10, 10, 11, 12, 13, 13, 14, 16, 16, 17, 17, 18, 18, 20, 21, 21, 21, 22, 23, 24, 27, 28, 29, 30, 33, 33, 34, 36, 37, 40, 41, 42, 43, 44, 45, 47, 47, 48, 48, 51, 51, 51, 51, 53, 54, 55, 55, 55, 57, 60, 61, 62, 64, 64, 64, 65, 66, 66, 67, 68, 68, 68, 69, 70, 74, 74, 74, 75, 78, 78, 78, 80, 80, 80, 82, 82, 82, 82, 83, 84, 84, 84, 87, 89, 89, 90, 91, 94, 94, 95, 95, 97, 98, 98, 99, 99]
排序时间:0秒
开始排序80000个数据
排序时间:0秒

11、归并排序（Merge Sort）

1、介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

2、思想

1、分治

2、治阶段

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

3、代码实现

package com.daijunyi.structure.sort;

class MergeSortMain{
    public static void main(String[] args) {
        SortUtil.smallTest(new MergeSort());
        SortUtil.middleTest(new MergeSort());
        SortUtil.bigTest(new MergeSort());
    }
}

/**
 * @author djy
 * @createTime 2022/1/8 下午5:16
 * @description 归并算法
 */
public class MergeSort implements Sort{

    @Override
    public <T extends Comparable<T>> void sort(T[] source) {
        divideAndCombineSort(source,0,source.length-1,new Object[source.length]);
    }

    /**
     * 分和治
     * @param source 原始数组
     * @param left 左边
     * @param right 右边
     * @param tmp 零时对象
     * @param <T>
     */
    public <T extends Comparable<T>> void divideAndCombineSort(T[] source,int left,int right,Object[] tmp){
        if (left < right){
            int middle = (left+right)/2;
            divideAndCombineSort(source,left,middle,tmp);
            divideAndCombineSort(source,middle+1,right,tmp);
            combineSort(source,left,middle,right,tmp);
        }
    }

    /**
     * 合的方法
     * @param source 原始对象
     * @param left 左边
     * @param middle 中间
     * @param right 右边
     * @param tmp
     * @param <T>
     */
    public <T extends Comparable<T>> void combineSort(T[] source,int left,int middle,int right,Object[] tmp){
        int tmpIndex = 0;
        int i = left;
        int j = middle+1;
        while (i<=middle && j<=right){
            if (source[i].compareTo(source[j])<=0){
                tmp[tmpIndex] = source[i];
                tmpIndex++;
                i++;
            }else if(source[i].compareTo(source[j]) > 0){
                tmp[tmpIndex] = source[j];
                tmpIndex++;
                j++;
            }
        }

        //填充剩下的数据
        while (i<=middle){
            tmp[tmpIndex] = source[i];
            tmpIndex++;
            i++;
        }

        while (j <= right){
            tmp[tmpIndex] = source[j];
            tmpIndex++;
            j++;
        }

        int tmpLeft = left;
        tmpIndex = 0;
        while (tmpLeft <= right){
            source[tmpLeft] = (T)tmp[tmpIndex];
            tmpIndex++;
            tmpLeft++;
        }
    }


}

4、运行结果

排序前：[3, 9, -1, 30, 20, 1, 3, 2, -10, -1]
排序后：[-10, -1, -1, 1, 2, 3, 3, 9, 20, 30]
开始排序100个数据
排序前：[53, 67, 25, 41, 54, 48, 17, 64, 16, 82, 23, 6, 89, 2, 51, 42, 89, 47, 5, 86, 94, 65, 73, 11, 10, 46, 79, 36, 61, 47, 43, 80, 8, 6, 79, 21, 70, 6, 77, 96, 50, 76, 49, 73, 13, 28, 36, 79, 8, 77, 0, 53, 96, 43, 84, 85, 14, 20, 78, 64, 56, 38, 36, 4, 73, 28, 29, 71, 43, 30, 34, 5, 80, 81, 45, 79, 47, 39, 7, 71, 65, 82, 38, 6, 79, 69, 4, 75, 41, 18, 58, 47, 37, 57, 12, 1, 46, 57, 70, 0]
排序后：[0, 0, 1, 2, 4, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8, 10, 11, 12, 13, 14, 16, 17, 18, 20, 21, 23, 25, 28, 28, 29, 30, 34, 36, 36, 36, 37, 38, 38, 39, 41, 41, 42, 43, 43, 43, 45, 46, 46, 47, 47, 47, 47, 48, 49, 50, 51, 53, 53, 54, 56, 57, 57, 58, 61, 64, 64, 65, 65, 67, 69, 70, 70, 71, 71, 73, 73, 73, 75, 76, 77, 77, 78, 79, 79, 79, 79, 79, 80, 80, 81, 82, 82, 84, 85, 86, 89, 89, 94, 96, 96]
排序时间:0秒
开始排序8000000个数据
排序时间:3秒

12、基数排序（Radix Sort）

1、介绍

1)基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或binsort，顾名思义，它是通过键值的各个位的值，将要排序元素分配至某些“桶”中，达到排序的作用
2) 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3)基数排序(Radix Sort)是桶排序的扩展

4) 基数排序是 1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

2、思想

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

3、图解

4、代码实现

1、代码实现

/**
* @author djy
* @createTime 2022/1/9 上午9:48
* @description 基数排序法
*/
public class RadixSort {

  public void sort(int[] source) {
      if (source == null || source.length < 2){
          return;
      }
      int[][] bucket= new int[10][source.length];
      //每个桶存储index
      int[] bucketElementCounts = new int[10];

      int max = source[0];
      for (int i=1;i<source.length;i++){
          if (source[i] > max){
              max = source[i];
          }
      }
      //最大值有多少位
      int count = (max+"").length();
      for (int i=0,n=1;i<count;i++,n*=10){
          for (int j=0;j<source.length;j++){
              int index = source[j]/n%10;
              bucket[index][bucketElementCounts[index]++] = source[j];
          }
          int index = 0;
          for (int j=0;j<bucket.length;j++){
              for (int k=0;k<bucketElementCounts[j];k++){
                  source[index] = bucket[j][k];
                  index++;
              }
              //赋值完一定要记住把桶中存储记录值置空
              bucketElementCounts[j] = 0;
          }
      }
  }
}

2、测试

```java class RadixSortMain{ public static void main(String[] args) {

  RadixSort radixSort = new RadixSort();
  int[] array = {3,9,1,30,20,1,3,2,10,1};

// Integer[] array = {3,9,-1,10,20};

  System.out.println("排序前："+ Arrays.toString(array));
  radixSort.sort(array);
  System.out.println("排序后："+Arrays.toString(array));

  int size = 100;
  int[] arrayMax = SortUtil.getRandomInt(size);
  System.out.println("开始排序"+size+"个数据");
  System.out.println("排序前："+ Arrays.toString(arrayMax));
  long start = System.currentTimeMillis();
  radixSort.sort(arrayMax);
  long m = (System.currentTimeMillis()-start)/1000;
  System.out.println("排序后："+ Arrays.toString(arrayMax));
  System.out.println("排序时间:"+m+"秒");

    int size1 = 8000000;
    int[] arrayMax1 = SortUtil.getRandomInt(size1);
    System.out.println("开始排序"+size1+"个数据");
    long start1 = System.currentTimeMillis();
    radixSort.sort(arrayMax1);
    long m1 = (System.currentTimeMillis()-start1)/1000;
    System.out.println("排序时间:"+m1+"秒");
}

}

```shell
排序前：[3, 9, 1, 30, 20, 1, 3, 2, 10, 1]
排序后：[1, 1, 1, 2, 3, 3, 9, 10, 20, 30]
开始排序100个数据
排序前：[82, 79, 94, 76, 29, 8, 65, 3, 56, 44, 23, 67, 87, 62, 57, 73, 26, 18, 62, 72, 53, 27, 21, 5, 3, 71, 44, 53, 55, 73, 12, 5, 18, 0, 33, 93, 16, 43, 52, 32, 24, 12, 89, 71, 84, 21, 1, 44, 44, 87, 31, 99, 44, 53, 34, 45, 27, 68, 31, 7, 3, 75, 70, 51, 79, 56, 64, 23, 22, 48, 83, 10, 86, 3, 0, 85, 37, 86, 88, 53, 56, 15, 85, 71, 94, 31, 81, 61, 45, 39, 73, 52, 72, 31, 93, 55, 30, 76, 7, 90]
排序后：[0, 0, 1, 3, 3, 3, 3, 5, 5, 7, 7, 8, 10, 12, 12, 15, 16, 18, 18, 21, 21, 22, 23, 23, 24, 26, 27, 27, 29, 30, 31, 31, 31, 31, 32, 33, 34, 37, 39, 43, 44, 44, 44, 44, 44, 45, 45, 48, 51, 52, 52, 53, 53, 53, 53, 55, 55, 56, 56, 56, 57, 61, 62, 62, 64, 65, 67, 68, 70, 71, 71, 71, 72, 72, 73, 73, 73, 75, 76, 76, 79, 79, 81, 82, 83, 84, 85, 85, 86, 86, 87, 87, 88, 89, 90, 93, 93, 94, 94, 99]
排序时间:0秒
开始排序8000000个数据
排序时间:1秒

12、算法运行时间总结

1、排序对比

2、运行时间对比

单位 | 待排序个数 | 1000 | 5000 | 1万 | 10万 | 100万 | 1000万 | 5000万 | 1亿 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 冒泡排序 | 13m | 96m | 390m | 48s372m | - | - | - | - | | 选择排序 | 8m | 40m | 68m | 9s733m | - | - | - | - | | 插入排序 | 5m | 48m | 77m | 11s116m | - | - | - | - | | 希尔排序 | 1m | 4m | 6m | 46m | 879m | 19s585m | - | - | | 快排-填坑 | 1m | 2m | 3m | 80m | 359m | 4s388m | 30s394m | 67s346m | | 快排-交换 | 0m | 1m | 1m | 16m | 250m | 4s353m | 31s110m | 73s429m | | 快排-单指针 | 1m | 2m | 3m | 60m | 198m | 4s363m | 30s429m | 79s634m | | 快排-填坑优化 | 2m | 2m | 3m | 65m | 401m | 3s761m | 27s401m | 60s338m | | 归并排序 | 1m | 1m | 3m | 82m | 278m | 4s237m | 27s399 | 62s85m | | 基数排序 | 3m | 1m | 2m | 6m | 44m | 496m | 3s434m | 内存溢出 |

3、算法与数据结构（排序）

1、排序（Sort Algorithm）

1、概念

2、排序的分类

1、内部排序

2、外部排序

3、常见的排序算法分类

3、算法的时间复杂度

1、度量一个程序执行时间的两种方法

1、事后统计的方法

2、事前估算的方法

4、时间频度

1、介绍

2、举例说明-基本案例

1、忽略常数项

2、忽略低次项

3、忽略系数

3、时间复杂度

4、常见的时间复杂度

5、常见的时间复杂度对应的图

1、常数阶O（1）

2、对数阶O(log2n)

3、线性阶O(n)

4、线性对数阶O(nlog2n)

5、平方阶O(n2)

6、立方阶O(n3)、K次方阶O(nk)

6、平均时间复杂度和最坏时间复杂度

5、算法的空间复杂度简介

1、基本介绍

6、冒泡排序(Bubble Sorting)

1、思想

1、逻辑

2、优化

2、演示

3、代码实现

1、创建Sort接口

3、冒泡排序主程序

4、测试

5、结果

7、选择排序（Selection Sort）

1、思想

2、思路分析图

3、代码实现

1、创建SelectionSort

8、插入排序（Insertion Sort）

1、思想

2、思路图

3、代码实现

1、代码实现

9、希尔排序（Donald Shell Sort）

1、简单插入排序存在的问题

2、介绍

3、思想

4、图解

5、代码实现

1、实现

2、测试

10、快速排序（Quick Sort）

1、介绍

2、基本思想

2、填坑法

1、思想与图解

2、代码实现

3、交换法

1、思想和图解

2、代码实现

4、单指针交换

1、思想

2、代码

5、填坑排序优化

1、思想

2、代码实现

3、结果

11、归并排序（Merge Sort）

1、介绍

2、思想

1、分治

2、治阶段

3、代码实现

4、运行结果