【Java数据结构与算法】排序算法

排序算法介绍和分类

排序算法的介绍

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

排序分类：

内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

插件的排序算法分类

算法的时间复杂度

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

事后统计的方法

这种方法可行，但是有两个问题：一是要想对设计的算法运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机硬件、软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快；
事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优；

时间频度介绍和特点

时间频度介绍

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

举例说明

基本案例

比如：计算1-100所有数字之和，设计两种算法；

int total = 0;
int end = 100;
// 使用for循环计算
for(int i=1;i<=end;i++){
    total+=i;
}

T(n)=n+1;

1 2	// 直接计算 total = (1+end)*end/2;

T(n)=1;

忽略常数项

	T(2n+20)	T(2n)	T(3n+10)	T(3n)
1	22	2	13	3
2	24	4	16	6
5	30	10	25	15
8	36	16	34	24
15	50	30	55	45
30	80	60	100	90
100	220	200	310	300
300	620	600	910	900

结论：

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

忽略低次项

	T(2n^2+3n+10)	T(2n^2)	T(n^2+5n+20)	T(n^2)
1	15	2	26	1
2	24	8	34	4
5	75	50	70	25
8	162	128	124	64
15	505	450	320	225
30	1900	1800	1070	900
100	20310	20000	10520	10000

结论：

2n^2+3n+10和``2n^2随着n变大，执行曲线无线接近，可以忽略3n+10`；
n^2+5n+20和``n^2随着n变大，执行曲线无线接近，可以忽略5n+20`；

忽略系数

	T(3n^2+2)	T(5n^2+7n)	T(n^3+5n)	T(6n^3+4n)
1	5	12	6	10
2	16	34	18	56
5	85	160	150	770
8	208	376	552	3104
15	705	1230	3450	20310
30	2760	4710	27150	162120
100	30200	50700	1000500	6000400

结论：

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

时间复杂度计算和举例

时间复杂度

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

常见的时间复杂度

常数阶O(1);
对数阶O( $log_2n$ );
线性阶O(n);
线性对数阶O( $nlogN$ );
平方阶O(n^2);
立方阶O(n^3);
k次方阶O(n^k);
指数阶O(2^n);

说明：

常见的算法时间复杂度由小到大依次为：O(1)<O( $log_2n$ )<O(n)<O( $nlog_2n$ )<O(n^2)<O(n^3)<O(n^k)<O(2^n)，随着问题规模n的不断增大，上述时间复杂度不断增加，算法的执行效率越低；
从上图可以看出，我们应该尽可能避免使用指数阶的算法；

举例说明

常数阶O(1)

无论代码执行多少行，只要没有循环等复杂结构，那这个代码的时间复杂度就是O(1);
1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i+j;
说明：上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使上万行，都可以用O(1)来表示它的时间复杂度。
对数阶O( $log_2n$ )
1
2
3
4
int i = 1;
while(i<n){
i = i * 2;
}
说明：在while循环里面，每次都将i乘以2，乘完之后，i距离n越来越近。假设循环x次后，i就大于2了，此时这个循环就退出了，也就是说2的x次方等于n，那么x= $log_2n$ 也就是说当循环 $log_2n$ 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O( $log_2n$ )。O( $log_2n$ )这个2时间上是根据diamagnetic变化的，例如i=i*3时，则是O( $log_3n$ )；
线性阶O(n)
1
2
3
4
for(i=1;i<=n;++i){
j = i;
j++;
}
说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度；
线性对数阶O( $nlogN$ )
1
2
3
4
5
6
for(m=1;m<n;m++){
i = 1;
while(i<n){
i = i * 2;
}
}
说明：线性对数阶O( $nlogN$ )其实非常容易理解，将时间复杂度为O( $logN$ )的代码循环n遍的话，那么它的时间复杂度就是n*O(logN)，也就是O( $nlogN$ )；
平方阶O(n^2)
1
2
3
4
5
6
for(x=1;x<=n;x++){
for(i=1;i<=n;i++){
j = i;
j++;
}
}
说明：如果把O(n)的代码在嵌套一遍循环，它的时间复杂度就是O(n^2)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(n*n)，即O(n^2)；如果其中一层循环改为m，那它的时间复杂度就编程O(n*m);
立方阶O(n^3)和k次方阶O(n^k)类似平方阶；

平均和最坏时间复杂度介绍

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

平均时间复杂度和最坏时间复杂度如下如表；

排序法	平均时间	最差情行	稳定度	额外空间	备注
冒泡	O(n^2)	O(n^2)	稳定	O(1)	n小时较好
交换	O(n^2)	O(n^2)	不稳定	O(1)	n小时较好
选择	O(n^2)	O(n^2)	不稳定	O(1)	n小时较好
插入	O(n^2)	O(n^2)	稳定	O(1)	大部分已排序时较好
基数	O( $log_RB$ )	O( $log_RB$ )	稳定	O(n)	B是真数(0~9)，R是基数(个十百)
shell	O(nlogB)	O(n^s) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogB)	O(n^2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogB)	O(nlogB)	稳定	O(1)	n大时较好
堆	O(nlogB)	O(nlogB)	不稳定	O(1)	n大时较好

算法空间复杂度基本介绍

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

冒泡排序算法思路分析

基本介绍

冒泡排序(Bubble Sorting)的基本思想是：通过对待排序序列从前向后(从下标小的地方开始)，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移动到后部，就像水底的气泡一样向上冒；

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，说明序列有序，因此要在排序过程中设置一个标志判断元素是否进行过交换。从而减少不必要的比较。

思路分析

列举五个无序数：3，9，-1，10，-2使用冒泡排序将其排成一个从小到大的有序数列。

第一趟排序：

3，9，-1，10，-2

3，-1，9，10，-2

3，-1，9，-2，10

第二趟排序：

-1，3，9，-2，10

-1，3，-2，9，10

第三趟排序：

-1，3，-2，9，10

-1，-2，3，9，10

第四趟排序：

-2，-1，3，9，10

冒泡排序规则：

一共进行数组大小减1次循环；
每一趟排序次数在逐渐减少；
如果我们发现某次排序中没有交换，可以提前结束排序(优化)；

冒泡排序算法代码实现

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/12 - 12:21
 **/
// 冒泡排序
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,-2};
        int temp = 0; // 临时变量

        // 为了容易理解，我们把冒泡排序的过程展示出来
        // 第一趟排序，就是最大的数拍到最后
//        for(int j = 0;j<arr.length-1;j++){
//            // 如果前面的数比后面的数大，就交换
//            if(arr[j]>arr[j+1]){
//                temp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = temp;
//            }
//        }
//        System.out.println("第一趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
//
//        // 第二趟排序，就是将第二大的数排在倒数第二位
//        for(int j = 0;j<arr.length-1-1;j++){
//            // 如果前面的数比后面的数大，就交换
//            if(arr[j]>arr[j+1]){
//                temp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = temp;
//            }
//        }
//        System.out.println("第二趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
//
//        // 第三趟排序，就是将第三大的数排在倒数第三位
//        for(int j = 0;j<arr.length-1-2;j++){
//            // 如果前面的数比后面的数大，就交换
//            if(arr[j]>arr[j+1]){
//                temp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = temp;
//            }
//        }
//        System.out.println("第三趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
//
//        // 第四趟排序，就是将第四大的数排在倒数第四位
//        for(int j = 0;j<arr.length-1-3;j++){
//            // 如果前面的数比后面的数大，就交换
//            if(arr[j]>arr[j+1]){
//                temp = arr[j];
//                arr[j] = arr[j+1];
//                arr[j+1] = temp;
//            }
//        }
//        System.out.println("第四趟排序后的数组");
//        System.out.println(Arrays.toString(arr));

        // 完整冒泡排序过程
        // 冒泡排序时间复杂度O(n^2)
        for (int i = 0; i < arr.length-1; i++) {
            for(int j = 0;j<arr.length-1-i;j++){
                // 如果前面的数比后i面的数大，就交换
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后的数组");
            System.out.println(Arrays.toString(arr));
        }
    }
}

运行结果

第1趟排序后的数组
[3, -1, 9, -2, 10]
第2趟排序后的数组
[-1, 3, -2, 9, 10]
第3趟排序后的数组
[-1, -2, 3, 9, 10]
第4趟排序后的数组
[-2, -1, 3, 9, 10]

Process finished with exit code 0

冒泡排序算法优化

冒泡排序优化

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，说明序列有序，因此要在排序过程中设置一个标志判断元素是否进行过交换。从而减少不必要的比较。

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/12 - 12:21
 **/
// 冒泡排序
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,-2};
        int temp = 0; // 临时变量
        boolean flag = false; // 标识符
        // 冒泡排序优化
        // 冒泡排序时间复杂度O(n^2)
        for (int i = 0; i < arr.length-1; i++) {
            for(int j = 0;j<arr.length-1-i;j++){
                // 如果前面的数比后i面的数大，就交换
                if(arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后的数组");
            System.out.println(Arrays.toString(arr));
            if(!flag){
                // 说明在一趟排序中，没发生过一次交换
                break;
            }else{
                flag = false; // 重置flag，进行下一次判断记录
            }
        }
    }
}

运行结果

第1趟排序后的数组
[3, -1, 9, -2, 10]
第2趟排序后的数组
[-1, 3, -2, 9, 10]
第3趟排序后的数组
[-1, -2, 3, 9, 10]
第4趟排序后的数组
[-2, -1, 3, 9, 10]

Process finished with exit code 0

冒泡排序封装

将冒泡排序封装为一个方法

// 将冒泡排序封装为一个方法
public int[] BubbleSort(int [] arr){
    int temp = 0; // 临时变量
    boolean flag = false; // 标识符
    // 冒泡排序优化
    // 冒泡排序时间复杂度O(n^2)
    for (int i = 0; i < arr.length-1; i++) {
        for(int j = 0;j<arr.length-1-i;j++){
            // 如果前面的数比后i面的数大，就交换
            if(arr[j]>arr[j+1]){
                flag = true;
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        if(!flag){
            // 说明在一趟排序中，没发生过一次交换
            break;
        }else{
            flag = false; // 重置flag，进行下一次判断记录
        }
    }
    return arr;
}

经过测试80000条随机数排序，冒泡排序耗费时间大约为20s左右；

选择排序算法思路图解

基本介绍

选择排序(select sorting)也属于内部排序法，是从需要排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

思路分析

选择排序也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]进行交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]进行交换，……，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]进行交换，……，第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]进行交换；总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

思路分析图解

说明：

选择排序一种由数组大小减1次排序；
每一轮排序，又是一个循环，循环的规则：
- 先假定当前这个数是最小数；
- 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标；
当遍历到数组的最后时，就得到本轮最小数和下标；

选择排序算法代码实现

应用实例

有一群牛，颜值分别是10分，34分，19分，100分，80分，请使用选择排序从低到高进行排序[19,34,100,10,80]；

代码实现

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/13 - 10:23
 **/
// 选择排序
public class SelectSort {
    public static void main(String[] args) {
        // 原始数组 [19,34,100,10,80]
        int[] arr = {19,34,100,10,80};
        selectSort(arr);
    }
    // 选择排序
    public static void selectSort(int[] arr){
        System.out.println("原始数组");
        System.out.println(Arrays.toString(arr));

        // 完整选择排序 时间复杂度O(n^2)
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i; // 假定初始值下标
            int min = arr[i]; // 假定初始值
            for(int j = i+1; j<arr.length;j++){
                if(min>arr[j]){
                    // 说明当前的值比我们假定的值大
                    min = arr[j]; // 重置min
                    minIndex = j; // 重置minIndex
                }
            }
            // 将最小值放在arr[i]，交换位置
            // 如果minIndex没有变化过，那我们也就不需要交换
            if(minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            System.out.println("第"+(i+1)+"轮交换后");
            System.out.println(Arrays.toString(arr));
        }
        // 使用逐步推导的方式，来理解选择排序
        /*
        // 第一轮比较交换后
        int minIndex = 0; // 假定初始值下标
        int min = arr[0]; // 假定初始值
        for(int j = 0+1; j<arr.length;j++){
            if(min>arr[j]){
                // 说明当前的值比我们假定的值大
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 将最小值放在arr[0]，交换位置
        // 如果minIndex没有变化过，那我们也就不需要交换
        if(minIndex!=0){
            arr[minIndex] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一轮交换后");
        System.out.println(Arrays.toString(arr));

        // 第二轮比较交换后
        minIndex = 1; // 假定初始值下标
        min = arr[1]; // 假定初始值
        for(int j = 1+1; j<arr.length;j++){
            if(min>arr[j]){
                // 说明当前的值比我们假定的值大
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 将最小值放在arr[1]，交换位置
        // 如果minIndex没有变化过，那我们也就不需要交换
        if(minIndex!=1){
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮交换后");
        System.out.println(Arrays.toString(arr));

        // 第三轮比较交换后
        minIndex = 2; // 假定初始值下标
        min = arr[2]; // 假定初始值
        for(int j = 2+1; j<arr.length;j++){
            if(min>arr[j]){
                // 说明当前的值比我们假定的值大
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 将最小值放在arr[2]，交换位置
        // 如果minIndex没有变化过，那我们也就不需要交换
        if(minIndex!=2){
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮交换后");
        System.out.println(Arrays.toString(arr));

        // 第四轮比较交换后
        minIndex = 3; // 假定初始值下标
        min = arr[3]; // 假定初始值
        for(int j = 3+1; j<arr.length;j++){
            if(min>arr[j]){
                // 说明当前的值比我们假定的值大
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }
        // 将最小值放在arr[3]，交换位置
        // 如果minIndex没有变化过，那我们也就不需要交换
        if(minIndex!=3){
            arr[minIndex] = arr[3];
            arr[3] = min;
        }
        System.out.println("第四轮交换后");
        System.out.println(Arrays.toString(arr));
         */
    }
}

运行结果

原始数组
[19, 34, 100, 10, 80]
第1轮交换后
[10, 34, 100, 19, 80]
第2轮交换后
[10, 19, 100, 34, 80]
第3轮交换后
[10, 19, 34, 100, 80]
第4轮交换后
[10, 19, 34, 80, 100]

Process finished with exit code 0

经过测试80000条随机数排序，选择排序耗费时间大约为2s左右；

插入排序算法思路分析

基本介绍

插入排序(Insertion Sorting)属于内部排序法，是对需要排序的数据以插入的方式找寻该元素的适当位置，以达到排序的目的；

思路分析

插入排序的基本思想是：把n个待排序的元素看为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表；

思路分析图解

插入排序算法代码实现

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/14 - 10:28
 **/
// 插入排序
public class InsertSort {
    public static void main(String[] args) {
        int [] arr = {17,3,25,9};
        insertSort(arr);
    }
    // 插入排序
    public static void insertSort(int[]arr){
        System.out.println("初始数据为");
        System.out.println(Arrays.toString(arr));
        // 完整插入排序
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            // 定义待插入数的索引，arr[1]前面的下标
            insertIndex = i-1;
            // 给insertVal找到要插入的位置
            // 保证找到待插入位置时不越界，且保证没找到待插入位置要一直循环
            while(insertIndex>=0 && insertVal < arr[insertIndex]){
                // 将arr[insertIndex]后移
                arr[insertIndex +1] = arr[insertIndex];
                insertIndex--;
            }
            // 当退出while循环时，说明插入的位置找到，insertIndex+1
            // 判断是否需要赋值，进行优化
            if(insertIndex+1 != i){
                arr[insertIndex+1] = insertVal;
            }

            System.out.println("第"+i+"轮插入后");
            System.out.println(Arrays.toString(arr));
        }

        // 使用逐步推导，便于理解
        // 第一轮{17,3,25,9}->{3,17,25,9}
        // 定义待插入的数
        /*
        int insertVal = arr[1];
        // 定义待插入数的索引，arr[1]前面的下标
        int insertIndex = 1-1;
        // 给insertVal找到要插入的位置
        // 保证找到待插入位置时不越界，且保证没找到待插入位置要一直循环
        while(insertIndex>=0 && insertVal < arr[insertIndex]){
            // 将arr[insertIndex]后移
            arr[insertIndex +1] = arr[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时，说明插入的位置找到，insertIndex+1
        arr[insertIndex+1] = insertVal;

        System.out.println("第一轮插入后");
        System.out.println(Arrays.toString(arr));

        // 第二轮{3,17,25,9}->{3,17,25,9}
        // 定义待插入的数
        insertVal = arr[2];
        // 定义待插入数的索引，arr[2]前面的下标
        insertIndex = 2-1;
        // 给insertVal找到要插入的位置
        // 保证找到待插入位置时不越界，且保证没找到待插入位置要一直循环
        while(insertIndex>=0 && insertVal < arr[insertIndex]){
            // 将arr[insertIndex]后移
            arr[insertIndex +1] = arr[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时，说明插入的位置找到，insertIndex+1
        arr[insertIndex+1] = insertVal;

        System.out.println("第二轮插入后");
        System.out.println(Arrays.toString(arr));

        // 第三轮{3,17,25,9}->{3,17,25,9}
        // 定义待插入的数
        insertVal = arr[3];
        // 定义待插入数的索引，arr[3]前面的下标
        insertIndex = 3-1;
        // 给insertVal找到要插入的位置
        // 保证找到待插入位置时不越界，且保证没找到待插入位置要一直循环
        while(insertIndex>=0 && insertVal < arr[insertIndex]){
            // 将arr[insertIndex]后移
            arr[insertIndex +1] = arr[insertIndex];
            insertIndex--;
        }
        // 当退出while循环时，说明插入的位置找到，insertIndex+1
        arr[insertIndex+1] = insertVal;

        System.out.println("第三轮插入后");
        System.out.println(Arrays.toString(arr));
         */
    }
}

运行结果

初始数据为
[17, 3, 25, 9]
第1轮插入后
[3, 17, 25, 9]
第2轮插入后
[3, 17, 25, 9]
第3轮插入后
[3, 9, 17, 25]

Process finished with exit code 0

经过测试80000条随机数排序，插入排序耗费时间大约为5s左右；

希尔排序算法思路分析

插入排序存在的问题

我们看简单的插入排序可能存在的问题

数组arr={2,3,4,5,6,1}，这时需要插入的数1，这样的过程是；

{2,3,4,5,6,1}

{1,2,3,4,5,6}

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

希尔排序介绍

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

基本思想

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

分析图解

原始数组，以下数据元素颜色相同为一组；

初始增量gap=length/2=5，意味着整个数组被分为5组，[8,3][9,5][1,4][7,6][2,0];

对这5组分别进行直接插入排序，结果如下，可以看到，像3，4，6这些小元素都被调到前面了，然后缩小增量gap=5/2=2，数组被分为2组[3,1,0,9,7][5,6,8,4,2];

对以上2组再分别进行直接插入排序，结果如下，可以看到，此时整个数组的有序程度更进一步啦，在缩小增量gap=2/2=1；此时，整个数组为1组[0,2,1,4,3,5,7,6,9,8]；

经过上方的调整，现在整个数组非常接近有序。此时，仅需要对上方数组进行简单微调即可得到整个数组的排序；

希尔排序算法实现

交换式

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/15 - 10:31
 **/
public class ShellSort {
    public static void main(String[] args) {
        // 原始数据
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("初始数组为");
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
    }
    // 使用逐步推导编写希尔排序，交换式
    public static void shellSort(int[] arr){
        int temp = 0; // 中间变量
        int x = 0; // 记录排序次数
        // 完整希尔排序
        for(int gap = arr.length/2; gap>0; gap/=2){
            for (int i = gap; i < arr.length; i++) {
                // 遍历各组中所有的元素(共5组，每组2个元素)
                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;
                    }
                }
            }
            System.out.println("希尔排序"+(++x)+"轮后");
            System.out.println(Arrays.toString(arr));
        }
        /*
        // 希尔排序第1轮排序
        // 因为第1轮排序，是将10个数组分成了5组
        for (int i = 5; i < arr.length; i++) {
            // 遍历各组中所有的元素(共5组，每组2个元素)
            for (int j = i-5; j >=0 ; j-=5) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if(arr[j] > arr[j+5]){
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("希尔排序1轮后");
        System.out.println(Arrays.toString(arr));

        // 希尔排序第2轮排序
        // 因为第2轮排序，是将10个数组分成了5/2=2组
        for (int i = 2; i < arr.length; i++) {
            // 遍历各组中所有的元素(共5组，每组2个元素)
            for (int j = i - 2; j >=0 ; j-=2) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if(arr[j] > arr[j+2]){
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("希尔排序2轮后");
        System.out.println(Arrays.toString(arr));

        // 希尔排序第3轮排序
        // 因为第3轮排序，是将10个数组分成了2/2=1组
        for (int i = 1; i < arr.length; i++) {
            // 遍历各组中所有的元素(共5组，每组2个元素)
            for (int j = i - 1; j >=0 ; j-=1) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("希尔排序3轮后");
        System.out.println(Arrays.toString(arr));
         */
    }
}

运行结果

初始数组为
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
希尔排序1轮后
[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
希尔排序2轮后
[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
希尔排序3轮后
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Process finished with exit code 0

经过测试80000条随机数排序，希尔排序(交换式)耗费时间大约为17s左右；(甚至比插入排序还慢，需要进行优化)

移位式

优化交换式排序速度

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/15 - 10:31
 **/
public class ShellSort {
    public static void main(String[] args) {
        // 原始数据
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("初始数组为");
        System.out.println(Arrays.toString(arr));
        // shellSort(arr);
        shellSort1(arr);
    }
    // 使用逐步推导编写希尔排序，交换式
    public static void shellSort(int[] arr){
        int temp = 0; // 中间变量
        int x = 0; // 记录排序次数
        // 完整希尔排序
        for(int gap = arr.length/2; gap>0; gap/=2){
            for (int i = gap; i < arr.length; i++) {
                // 遍历各组中所有的元素(共5组，每组2个元素)
                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;
                    }
                }
            }
            System.out.println("希尔排序"+(++x)+"轮后");
            System.out.println(Arrays.toString(arr));
        }
    }
    
    // 希尔排序 移位式(优化交换式速度)
    public static void shellSort1(int[] arr) {
        int temp = 0; // 中间变量
        int x = 0; // 记录排序次数
        // 完整希尔排序
        // 增量gap，并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                temp = arr[i];
                if(arr[j]<arr[j-gap]){
                    while(j-gap >= 0 && temp<arr[j-gap]){
                        // 移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    // 当退出while循环后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
            System.out.println("希尔排序" + (++x) + "轮后");
            System.out.println(Arrays.toString(arr));
        }
    }
}

运行结果

初始数组为
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
希尔排序1轮后
[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
希尔排序2轮后
[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
希尔排序3轮后
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Process finished with exit code 0

经过测试80000条随机数排序，希尔排序(移位式)耗费时间大约为1s左右；

快速排序算法思路分析

基本介绍

快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此有序排列数据；

分析图解

快速排序算法代码实现

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/17 - 12:09
 **/
public class QuickSort {
    public static void main(String[] args) {
        int arr[] = {-9,78,0,23,-567,70};
        System.out.println("初始数组");
        System.out.println(Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("快速排序后数组");
        System.out.println(Arrays.toString(arr));
    }
    // 快速排序
    public static void quickSort(int[]arr,int left,int right){
        int lt = left;  // 左下标
        int rt = right; // 右下标
        int pivot = arr[(left+right)/2]; // pivot 中轴值
        int temp = 0; // 临时变量，用来交换
        // while循环的目的是让比pivot值小的放到左边，比pivot大的放到右边
        while(lt < rt){
            // 在pivot左边找到一个大于等于pivot的值
            while(arr[lt] < pivot){
                lt +=1;
            }
            // 在pivot右边找到一个小于等于pivot的值
            while(arr[rt] > pivot){
                rt -=1;
            }
            // 左边>=右边，说明左边的值都小于右边了
            if(lt >= rt){
                break;
            }
            // 交换
            temp = arr[lt];
            arr[lt] = arr[rt];
            arr[rt] = temp;

            // 如果交换完后，发现arr[lt] == pivot，就让右边前移
            if(arr[lt] == pivot){
                rt-=1;// 前移
            }
            // 如果交换完后，发现arr[rt] == pivot，就让左边后移
            if(arr[rt] == pivot){
                lt+=1;// 后移
            }
        }
        // 如果lt == rt，必须lt++，r--,否则会栈溢出
        if(lt==rt){
            lt+=1;
            rt-=1;
        }
        // 向左递归
        if(left < rt){
            quickSort(arr,left,rt);
        }
        // 向右递归
        if(right > lt){
            quickSort(arr,lt,right);
        }
    }
}

运行结果

初始数组
[-9, 78, 0, 23, -567, 70]
快速排序后数组
[-567, -9, 0, 23, 70, 78]

Process finished with exit code 0

经过测试80000条随机数排序，快速排序耗费时间大约为20ms左右；

归并排序算法思路分析

基本介绍

归并排序(Mergesort)是利用归并的思路实现排序方法，该算法采用经典的分治(divide and conquer)策略(分支法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段所得到的各个答案合并在一起，即分而治之)。

分析图解

可以看到这种结构很像一颗完全二叉树，归并排序我们采用递归实现(也可以采用迭代的方式实现)；

分的阶段

分的阶段可以理解为递归差分子序列的过程。

治的阶段

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

归并排序算法代码实现

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/18 - 9:39
 **/
public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {8,4,5,7,1,3,6,2};
        int temp[] = new int[arr.length]; // 归并排序需要一个额外空间
        System.out.println("初始数组");
        System.out.println(Arrays.toString(arr));
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("归并排序后数组");
        System.out.println(Arrays.toString(arr));
    }

    // 归并(分解+合并)
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2; //中间索引
            // 向左递归进行分解
            mergeSort(arr,left,mid,temp);
            // 向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            // 合并
            merge(arr,left,mid,right,temp);
        }
    }
    // 合并
    /**
     *
     * @param arr  原始数组
     * @param left 左边有序序列初始索引
     * @param mid 中间索引
     * @param right 最后的索引
     * @param temp 中转数组
     */
    public static void merge(int[] arr,int left,int mid,int right,int[]temp){
        int i = left; // 初始化i，左边有序序列初始索引
        int j = mid+1; // 初始化j，右边有序序列初始索引
        int t = 0; // 指向temp数组的当前索引
        // 先把左右两边的数据按照规则填充到temp数组，直到左右两边有序序列其中一边处理完毕为止
        while(i<=mid && j<=right){
            // 继续
            // 左边序列当前元素小于或者等于右边序列当前元素
            if(arr[i]<=arr[j]){
                temp[t] = arr[i]; // 把左边序列当前值放到temp中
                t += 1; // temp当前索引后移
                i += 1; // 左边序列索引后移
            }else{
                temp[t] = arr[j]; // 把右边序列当前值放到temp中
                t += 1; // temp当前索引后移
                j += 1; // 右边序列索引后移
            }
        }
        // 把有剩余数据的一边依次填充到temp
        while(i<=mid){ // 左边有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while(j<=right){ // 右边有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        // 将temp数组重新拷贝到arr
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t]; // 从temp拷贝到arr
            t += 1; // temp索引后移
            tempLeft +=1; // arr索引后移
        }
    }
}

运行结果

初始数组
[8, 4, 5, 7, 1, 3, 6, 2]
归并排序后数组
[1, 2, 3, 4, 5, 6, 7, 8]

Process finished with exit code 0

经过测试80000条随机数排序，归并排序耗费时间大约为20ms左右；

基数排序算法思路分析

基本介绍

基数排序(Radix Sort)于1882年由赫尔曼发明，属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort 或 bin sort)，它是通过键值的各个位上的值，将要排序的元素分配至某些桶中，达到排序的作用。

基数排序属于高效且稳定的排序法，属于桶排序的扩展。

稳定性举例：

例如一组数：3，4，1，1，2

排序后为：1，1，2，3，4；

稳定性：排序前相同的数1，1在排序后的顺序要与排序前保持一致；

思路分析

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

使用基数排序将数组{53,3,542,748,14,214}进行升序排序。

第一轮排序：
1. 将每个元素的个位数取出，然后按照个位数放入对应的桶中；
2. 全部放好后，按照桶顺序的下标依次取出数据，放回原来数组；
3. 第一轮排序后数组为{542,53,3,14,214,748}；
第二轮排序：
1. 将每个元素的十位数取出，然后按照十位数放入对应的桶中，前面没有位数的值补零；
2. 全部放好后，按照桶顺序的下标依次取出数据，放回原来数组；
3. 第二轮排序后数组为{3,14,214,542,748,53}；
第三轮排序：
1. 将每个元素的百位数取出，然后按照百位数放入对应的桶中，前面没有位数的值补零；
2. 全部放好后，按照桶顺序的下标依次取出数据，放回原来数组；
3. 第三轮排序后数组为{3,14,53,214,542,748}；

基数排序算法代码实现

这里所写的基数排序不能处理负数；

代码

package com.jokerdig.sort;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/10/19 - 11:15
 **/
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        radixSort(arr);
    }

    // 基数排序方法
    public static void radixSort(int[] arr){

        // 完整基数排序
        // 得到数组中最大数的位数
        int max = arr[0]; // 假设第一个数就是最大数
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]>max){
                max = arr[i]; // 找到最大值
            }
        }
        // 得到最大数是几位数
        int maxLength = (max + "").length();
        // 定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        /*
            说明：
            1. 二维数组包含10个一位数组
            2. 为了防止放入数时数据溢出，则每个一维数组(桶)，大小定为arr.length
            3. 很明确，基数排序是使用空间换时间的经典算法，当海量数据排序时会出现OutOfMemoryError(内存不足)
         */
        int[][] bucket = new int[10][arr.length];
        // 为了记录每个桶中，实际存放了多少个数据；
        // 我们定义一个一维数组来记录各个桶每次放入的数据个数
        int[] bucketElementCounts = new int[10];
        for (int i = 0,n = 1; i < maxLength; i++,n*=10) {
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素的对应位的数
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照桶的顺序，将桶中的数据放回原来的数组中
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有数据，我们才放入到原数组中
                if(bucketElementCounts[k] !=0){
                    // 循环第k个桶
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素放入到arr中
                        arr[index] = bucket[k][l];
                        index++; // 下标后移
                    }
                }
                // 第i+1轮处理后需要将每个bucketElementCounts[k]=0
                bucketElementCounts[k]=0;
            }
            System.out.println("第"+(i+1)+"轮基数排序后数组");
            System.out.println(Arrays.toString(arr));
        }
        /*
        // 推导过程
        // 第一轮排序(针对每个数字个位)
        // 定义一个二维数组，表示十个桶，每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        // 为了记录每个桶中，实际存放了多少个数据；
        // 我们定义一个一维数组来记录各个桶每次放入的数据个数
        int[] bucketElementCounts = new int[10];
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的个位置数
            int digitOfElement = arr[j] % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        // 按照桶的顺序，将桶中的数据放回原来的数组中
        int index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            // 如果桶中有数据，我们才放入到原数组中
            if(bucketElementCounts[k] !=0){
                // 循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    // 取出元素放入到arr中
                    arr[index] = bucket[k][l];
                    index++; // 下标后移
                }
            }
            // 第一轮处理后需要将每个bucketElementCounts[k]=0
            bucketElementCounts[k]=0;
        }
        System.out.println("第一轮基数排序后数组");
        System.out.println(Arrays.toString(arr));

        // 第二轮排序(针对每个数字十位)
        bucket = new int[10][arr.length];
        // 为了记录每个桶中，实际存放了多少个数据；
        // 我们定义一个一维数组来记录各个桶每次放入的数据个数
        bucketElementCounts = new int[10];
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的十位置数
            int digitOfElement = arr[j] /10 % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        // 按照桶的顺序，将桶中的数据放回原来的数组中
        index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            // 如果桶中有数据，我们才放入到原数组中
            if(bucketElementCounts[k] !=0){
                // 循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    // 取出元素放入到arr中
                    arr[index] = bucket[k][l];
                    index++; // 下标后移
                }
            }
            // 第二轮处理后需要将每个bucketElementCounts[k]=0
            bucketElementCounts[k]=0;
        }
        System.out.println("第二轮基数排序后数组");
        System.out.println(Arrays.toString(arr));

        // 第三轮排序(针对每个数字百位)
        bucket = new int[10][arr.length];
        // 为了记录每个桶中，实际存放了多少个数据；
        // 我们定义一个一维数组来记录各个桶每次放入的数据个数
        bucketElementCounts = new int[10];
        for (int j = 0; j < arr.length; j++) {
            // 取出每个元素的百位置数
            int digitOfElement = arr[j] /100 % 10;
            // 放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        // 按照桶的顺序，将桶中的数据放回原来的数组中
        index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            // 如果桶中有数据，我们才放入到原数组中
            if(bucketElementCounts[k] !=0){
                // 循环第k个桶
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    // 取出元素放入到arr中
                    arr[index] = bucket[k][l];
                    index++; // 下标后移
                }
            }
        }
        System.out.println("第三轮基数排序后数组");
        System.out.println(Arrays.toString(arr));
        */
    }

}

运行结果

第1轮基数排序后数组
[542, 53, 3, 14, 214, 748]
第2轮基数排序后数组
[3, 14, 214, 542, 748, 53]
第3轮基数排序后数组
[3, 14, 53, 214, 542, 748]

Process finished with exit code 0

经过测试80000条随机数排序，基数排序耗费时间大约为10ms左右；

排序算法时间复杂度比较

排序算法比较

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O( $n^2$ )	O(n)	O( $n^2$ )	O(1)	In-place	稳定
选择排序	O( $n^2$ )	O( $n^2$ )	O( $n^2$ )	O(1)	In-place	不稳定
插入排序	O( $n^2$ )	O(n)	O( $n^2$ )	O(1)	In-place	稳定
希尔排序	O(nlogn)	O(n $log^2$ n)	O(n $log^2$ n)	O(1)	In-place	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	Out-plcace	稳定
快速排序	O(nlogn)	O(nlogn)	O( $n^2$ )	O(logn)	In-place	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	In-place	不稳定
基数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-plcace	稳定
桶排序	O(n+k)	O(n+k)	O( $n^2$ )	O(n+k)	Out-plcace	稳定
基数排序	O(n×k)	O(n×k)	O(n×k)	O(n+k)	Out-plcace	稳定

	T(2n+20)	T(2n)	T(3n+10)	T(3n)
1	22	2	13	3
2	24	4	16	6
5	30	10	25	15
8	36	16	34	24
15	50	30	55	45
30	80	60	100	90
100	220	200	310	300
300	620	600	910	900

	T(2n+20)	T(2n)	T(3n+10)	T(3n)
1	22	2	13	3
2	24	4	16	6
5	30	10	25	15
8	36	16	34	24
15	50	30	55	45
30	80	60	100	90
100	220	200	310	300
300	620	600	910	900

排序算法介绍和分类

排序算法的介绍

插件的排序算法分类

算法的时间复杂度

时间频度介绍和特点

时间频度介绍

举例说明

时间复杂度计算和举例

时间复杂度

常见的时间复杂度

举例说明

平均和最坏时间复杂度介绍

平均和最坏时间复杂度介绍

算法空间复杂度基本介绍

冒泡排序算法思路分析

基本介绍

思路分析

冒泡排序算法代码实现

冒泡排序算法优化

冒泡排序优化

冒泡排序封装

选择排序算法思路图解

基本介绍

思路分析

思路分析图解

选择排序算法代码实现

应用实例

代码实现

插入排序算法思路分析

基本介绍

思路分析

思路分析图解

插入排序算法代码实现

希尔排序算法思路分析

插入排序存在的问题

希尔排序介绍

基本思想

分析图解

希尔排序算法实现

交换式

移位式

快速排序算法思路分析

基本介绍

分析图解

快速排序算法代码实现

归并排序算法思路分析

基本介绍

分析图解

归并排序算法代码实现

基数排序算法思路分析

基本介绍

思路分析

基数排序算法代码实现

排序算法时间复杂度比较

排序算法比较

相关属于解释

	T(2n+20)	T(2n)	T(3n+10)	T(3n)
1	22	2	13	3
2	24	4	16	6
5	30	10	25	15
8	36	16	34	24
15	50	30	55	45
30	80	60	100	90
100	220	200	310	300
300	620	600	910	900