友情提示，篇幅较长，建议收藏后查看。

排序算法介绍

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

假设含有n个记录的序列为{r₁，r₂，·······，r_n},，其相应的关键字分别为{k₁，k₂，·······，k_n}。
需要确定1,2·····，n的一种排列 p₁，p₂，·······，p_n ，使其相应的关键字满足k_p1 ≤ k_p2···· ≤k_pn 非递增（非递减）关系，即使得序列成为一个按关键字有序的序列{r₁，r₂，·······，r_n}，这样的操作称为排序。

相关术语

• 稳定: 如果a原本在b前面，而a=b，排序之后a仍然在b的前面;
• 不稳定: 如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面;3)内排序:所有排序操作都在内存中完成;
• 外排序:由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行;
• 时间复杂度:一个算法执行所耗费的时间。
• 空间复杂度:运行完一个程序所需内存的大小。
• n:数据规模
• k:“桶”的个数
• In-place:不占用额外内存
• Out-place:占用额外内存

排序的稳定性

假设 k_i = k_j （1 ≤ i ≤ n ，1 ≤ j ≤ n，i ≠ j），且在排序之前在序列中r_i领先于r_j （i < j）。如果排序完成后，序列中r_i仍然领先于r_j （i < j），那么我们就说排序方法是稳定的，反之，则该排序算法就不睡稳定的。简单点说就说班级排名，现在张三和李四分数一样，没有排序前李四在张三的前面，排序完成后，李四还是在在张三的前面，那么该排序算法就说稳定的。

排序分类

内排序与外排序

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

算法时间复杂度

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

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

• 事前估算的方法
  通过分析某个算法的时间复杂度来判断哪个算法更优。

时间频度

• 基本介绍
  时间频度:一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
• 举例说明-基本案例
  比如计算1-100所有数字之和，我们设计两种算法:

public class test1 {
    public static void main(String[] args) {
        add1();
        add2();
    }

    public static void add1(){
        int total = 0;
        int end = 100;
        //使用for循环计算 T(n) = n + 1 , +1是执行最后一次的判断
        for (int i = 1; i <= end; i++) {
            total = total + i;
        }
        System.out.println("total = " + total);
    }

    public static void add2(){
        int total = 0;
        int end = 100;

        //直接计算 T(n) = 1 等差数列和=(首项+末项)×项数÷2 
        total = (1 + end) * end / 2;
        System.out.println("total = " + total);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

忽略常数项

忽略常数项 结论:

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

忽略低次项

忽略低次项 结论:

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

忽略系数

结论:

• 随着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’+7n+6 与T(n)=3n’+2n+2它们的T(n)不同，但时间复杂度相同，都为O(2)。
• 计算时间复杂度的方法:
  1、用常数1代替运行时间中的所有加法常数T(n)=n2+7n+6 =>T(n)=n2+7n+1
  2、修改后的运行次数函数中，只保留最高阶项T(n)=n2+7n+1 => T(n)=n2
  3、去除最高阶项的系数T(n)= n²=> T(n)= n²=>O(n²)

常见的时间复杂度。

• 常数阶O(1)
• 对数阶O(log2n)
• 线性阶O(n)
• 线性对数阶O(nlog₂N)
• 平方阶O(n²)
• 立方阶O(n³)
• k次方阶O(n^k)
• 指数阶O(2ⁿ)
  
  说明:
• 常见的算法时间复杂度由小到大依次为:0(1) < 0(log₂n) < 0(n) < 0(nlog₂n) < O(nⁿ) < 0(n³) < 0(n^k) < o(2²)，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
• 从图中可见，我们应该尽可能避免使用指数阶的算法。

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是o(1)

    public static void fun1(){
        int i = 1;
        int j = 2;
        ++i;
        ++j;
        int m = i + j ;
        System.out.println(m);
    }
1
2
3
4
5
6
7
8

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类码有多长，即使有几万几十万行，都可以用o(1)来表示它的时间复杂度。

对数阶O(log2n)

    /**
     * 对数阶O(log2n)
     */
    public static void fun2(int n){
        int i = 1;
        while (i < n){
            i = i *  2;
        }
    }
1
2
3
4
5
6
7
8
9
10

说明:
在while循环里面，每次都将i乘以2，乘完之后，i距离n就越来越近了。

假设循环x次之后，i就大于2了，此时这个循环就退出了，也就是说2的x次方等于n，那么x=log₂n也就是说当循环log₂n次以后，这个代码就结束了。因此这个代码的时间复杂度为:O(log₂n)。O(log₂n)的这个2时间上是根据代码变化的，i=i*3，则是O(log₃n)。

如果N= a^x(a>0,a≠1),即a的x次方等于N(a>0，且a≠1)，那么数x叫做以a为底N的对数（ logarithm),记作x = lo_a,N。其中，a叫做对数的底数，N叫做真数，x叫做以a为底N的对数。

线性阶O(n)

    /**
     * O(n)线性阶
     */
    public static void fun3(int n){
        int j = 0;
        for (int i = 0; i < n; i++) {
            j  = i;
            j++;
        }
    }
1
2
3
4
5
6
7
8
9
10

说明:
这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用o(n)来表示它的时间复杂度。

线性对数阶O(nlog₂N)

    /**
     * 线性对数阶O(nlog~2~n)
     */
    public static void fun4(int n){
        int j = 1;
        for (int i = 0; i < n; i++) {
            j = i;
            while (i < n){
                i = i * 2;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

说明:
线性对数阶o(nlogN)其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的活，那么它的时间复杂度就是n* O(logN)，也就是了O(nlogN)

平方阶O(n²)

    /**
     *  平方阶O(n2)
     */
    public static void fun5(int n){
        int j = 1;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < i; k++) {
                j = i;
                j++;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

说明:
平方阶o(n²)就更容易理解了，如果把o(n)的代码再嵌套循环一遍，它的时间复杂度就是o(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(n*n)。

即o(n2)如果将其中一层循环的n改成m，那它的时间复杂度就变成了O(m*n)

立方阶O(n³)、K次方阶O(n^k)

说明:参考上面的O(n²)去理解就好了，O(n³)相当于三层n循环，其它的类似。

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

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

空间复杂度

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

冒泡排序

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

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

小结上面的图解过程:

• 一共进行数组的大小 -1 次大的循环
• 每一趟排序的次数在逐渐的减少
• 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化。

代码实现

package sort.bubbleSort;

import java.util.Arrays;

public class bubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,22,18};
        bubbleSort(arr);
    }

    /**
     * 冒泡排序（稳定）
     * 每一趟排序找到序列中最大的一个值，将最大的数，交换到序列最后的位置。
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                //如果前面的数比后面的数大，进行位置交换。
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    isSwaped = true;
                }
            }
            System.out.println("第"+ i + " 趟："+ Arrays.toString(arr));
            if (!isSwaped) {
                // 内层没有元素交换，此时整个数组已经有序
                break;
            }
        }
    }



    static void swap(int[] arr,int i,int min){
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

输出结果

选择排序（不稳定）

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

思想

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

代码实现

package sort.selectionSort;


import java.util.Arrays;

/**
 * 直接选择排序（不稳定）
 *
 * 每次从无序区间选择一个最大或最小值的一个元素放在无序区间的最后或者最前，直到待排序的所有元素排序完毕。
 *
 * 最开始时，待排序数组(无序区间)，取值：[i..n)。
 * 已排序的数组(有序区间)，取值：[]，区间中没有任何元素。
 * 进行第一次排序：选择无序区间的最小值，放在无序区间的最开始位置。
 *
 * 选择排序在排序过程中无法保证相同元素的先后顺序，故不是一个稳定性的算法。
 */
public class selectionSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,22,18};
        selectionSort(arr);
     
        //System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;//假设第一个下标就是最小的
            boolean flag = false;
            //每次从arr[0] ~ arr[n-1]中找到最小元素的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                    flag = true;
                }
            }
            if (flag){//减少交换次数
                swap(arr,i,min);
                System.out.println("第" +(i+1) + "次：" + Arrays.toString(arr));
            }

        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

输出结果

优化

双向查找,每次从无序区间中选出最小值和最大值，存放在无序区间的最开始和最后面位置，重复上述过程。

package sort.selectionSort;

import java.util.Arrays;

/**
 * 直接选择排序（不稳定）
 *
 * 每次从无序区间选择一个最大或最小值的一个元素放在无序区间的最后或者最前，直到待排序的所有元素排序完毕。
 *
 * 最开始时，待排序数组(无序区间)，取值：[i..n)。
 * 已排序的数组(有序区间)，取值：[]，区间中没有任何元素。
 * 进行第一次排序：选择无序区间的最小值，放在无序区间的最开始位置。
 *
 * 选择排序在排序过程中无法保证相同元素的先后顺序，故不是一个稳定性的算法。
 */
public class selectionSort1 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,22,18};
        selectionSortOP(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 双向选择排序
     *
     * 每次从无序区间中选出最小值和最大值，存放在无序区间的最开始和最后面位置，重复上述过程
     */
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low == high => 无序区间只剩下最后一个元素，其实整个数组已经有序了。
        while (low < high) {
            int min = low; // 假设最小的是第一个元素下标
            int max = low; // 假设最大的是第一个元素下标

            /**
             * 遍历序列
             * 1, 0+1
             * 2：1+1
             */
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) { //找到最小值下标
                    min = i;
                }
                if (arr[i] > arr[max]) { //找到最大值下标
                    max = i;
                }
            }
            // 此时min对应了最小值索引，交换到无序区间的最前面
            swap(arr, min, low);
            // 边界条件 low == max
            if (max == low) {
            //此时max还在low这个位置，若交换high与max索引的元素会导致已排序的"2"被移到high处需要将min值赋给max
                max = min;
            }
            swap(arr, max, high);
            low++;
            high--;
        }
    }

    static void swap(int[] arr,int i,int min){
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

插入排序（稳定）

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

思想

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

• 类似打牌码牌的过程。
• 初始数据越接近有序，插入排序效率越高，经常作为高阶排序算法优化手段。
• 多次比较，注意是多次比较，直接插入，不是比较一次插入一次（与冒泡不同）。

代码实现

两个方法都可

package sort.insertionSort;

import java.util.Arrays;

/**
 * 直接插入排序 （稳定）
 *
 *     插入排序：类似打牌码牌的过程。
 *     直接插入排序：将待排序的集合看做两部分，已排序的区间[0..i)；待排序的区间[i...n)；
 *
 *     每次选择无序区间的第一个元素插入到有序区间的合适位置，直到整个数组有序。
 *
 *     初始数据越接近有序，插入排序效率越高，经常作为高阶排序算法优化手段。
 */
public class insertionSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,22,18};
        insertionSort1(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 直接插入排序
     * 已排序区间[0..i)  => 默认第一个元素就是已经排好序的区间
     * 待排序区间[i...n)
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 已排序区间[0...1)
            // 待排序区间[i ..n)
            // 选择无序区间的第一个元素，不断向前看
            // 注意看内层循环的终止条件 j >= 1而不是 j >= 0 ?
            // 因为此时arr[j] 不断向前看一个元素。  j - 1 要合法 j - 1 >= 0
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {
                //找到了合适的位置才交换
                swap(arr, j, j - 1);
            }
        }
    }

    public static void insertionSort1(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;

        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];  //待插入的数,暂存要插入的数
            insertIndex = i - 1;  //arr[i]的前面这个数的下标
            /**
             * 给insertVal找到合适的插入位置
             *
             * insertIndex >= 0 确保insertVal的插入位置，不越界。
             * insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置。
             *将arr[insertIndex]后移
             */
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){    // 12 < 88
                arr[insertIndex + 1] = arr[insertIndex]; // arr[2] = arr[1]
                insertIndex--;
            }
            /**
             * 退出循环，说明找到了插入位置，insertIndex + 1
             */
            if (insertIndex + 1 != i){
                arr[insertIndex + 1] = insertVal; //arr[1] = 12
            }
        }
    }
    static void swap(int[] arr,int i,int min){
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

二分插入排序

思考一下，直接插入的排序的主要耗时在哪个步骤？我觉得是给待插入的值找到合适的插入位置比较合适，所以采用二分查找，来优化前面在有序的序列中逐步查找插入位置的办法。

使用二分查找优化插入位置的查找次数。

package sort.insertionSort;

import java.util.Arrays;

public class insertionSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,22,18};
        //insertionSort1(arr);
        insertionSortBS(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    /**
     * 二分插入排序，*使用二分查找优化插入位置的查找次数。
     * @param arr
     */
    public static void insertionSortBS(int[] arr) {
        // 有序区间[0..i)
        // 无序区间[i..n)
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            // 有序区间[left...right)
            int left = 0;
            int right = i;
            while (left < right) {
                int mid = (left + right) / 2;
                if (val < arr[mid]) {
                    right = mid;
                }else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            // 搬移[left..i)的元素
            for (int j = i; j > left ; j--) {
                arr[j] = arr[j - 1];
            }
            // left就是待插入的位置
            arr[left] = val;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

希尔排序（不稳定）

问题

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

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

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

思想

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

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

可以把希尔排序理解成整体插入排序之前的预处理，就是为了咋插入排序之时，序列更加有序，然后插入排序效率就会更高。

稳定性：不稳定，再按照gap对子数组进行排序时，有可能值相等的两个元素被分到了两个不同的数组，他们的顺序可能交换。如下图，相等的5，在第一趟排序就交换了位置。

交换法

希尔排序时，对有序序列在插入时采用交换法，并测试排序速度.

推导

   public static void shellSorSwap(int[] arr) {
        /**
         * 第一轮排序，将10个数据分成10组  arr.length/2
         */
        for (int i = 5; i < arr.length; i++) {
            //遍历各组中所有的元素（共五组。每组两个元素），步长为5
            for (int j = i - 5; j >= 0; j -= 5) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 5]){
                    swap(arr,j,j + 5);
                }
            }
        }
        System.out.println("第一轮" + Arrays.toString(arr));

        //第二轮
        for (int i = 2; i < arr.length; i++) {
            //遍历各组中所有的元素（共2组。每组两个元素），步长为2
            for (int j = i - 2; j >= 0; j -= 2) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 2]){
                    swap(arr,j,j + 2);
                }
            }
        }
        System.out.println("第二轮" + Arrays.toString(arr));

        //第三轮
        for (int i = 1; i < arr.length; i++) {
            //遍历各组中所有的元素（共2组。每组两个元素），步长为2
            for (int j = i - 1; j >= 0; j -= 1) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }
        }
        System.out.println("第三轮" + Arrays.toString(arr));

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

输出结果

可以看到第三轮排序完成后，数组已经基本有序了，在最后进行一次插入排序即可。但是测试后你会发现效率并没有直接插入的效率高，因为采用的是交换法，交换的次数太多了，解决的办法就是使用移动法。

代码实现

package sort.shellSort;

import com.sun.prism.shader.Solid_RadialGradient_REFLECT_AlphaTest_Loader;

import java.awt.geom.GeneralPath;
import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,18};

        shellSorSwap(arr);
    }


    /**
     * 希尔排序 - 缩小增量排序，交换法
     * 按照gap将原数组分为gap个子数组，子数组内部先排序，不断缩小gap值，直到gap = 1
     * 当gap = 1时，整个数组已经近乎有序，只需要最后来一次插入排序即可。
     *
     * 回顾一下冒泡和插入，冒泡排序是每次循环把最大和最小的数字移动到最边上，然后对剩下的接着冒泡。
     * 插入排序是把数组分成两组，每次从无序组中拿出一个数插入有序数组。
     * 这里i为分界线，i左边是有序数组，从i右边拿出一个数插入到有序数组合适位置，然后i+1
     * i有两个作用，i+1既可以改变分组，也可以在下次i+gap后从无序数组中拿元素插入本组。
     */
    public static void shellSorSwap(int[] arr) {
        int count = 0;
        for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有的元素（共gap组。每组个元素），步长为gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果当前元素大于加上步长后的那个元素，则交换元素位置
                    if (arr[j] > arr[j + gap]){
                        swap(arr,j,j + gap);
                    }
                }
            }
            System.out.println("第"+(++count)+"轮"+Arrays.toString(arr));
        }


 /*
        *//**
         * 第一轮排序，将10个数据分成10组  arr.length/2
         *//*
        for (int i = 5; i < arr.length; i++) {
            //遍历各组中所有的元素（共五组。每组两个元素），步长为5
            for (int j = i - 5; j >= 0; j -= 5) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 5]){
                    swap(arr,j,j + 5);
                }
            }
        }
        System.out.println("第一轮" + Arrays.toString(arr));

        //第二轮
        for (int i = 2; i < arr.length; i++) {
            //遍历各组中所有的元素（共2组。每组两个元素），步长为2
            for (int j = i - 2; j >= 0; j -= 2) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 2]){
                    swap(arr,j,j + 2);
                }
            }
        }
        System.out.println("第二轮" + Arrays.toString(arr));

        //第三轮
        for (int i = 1; i < arr.length; i++) {
            //遍历各组中所有的元素（共2组。每组两个元素），步长为2
            for (int j = i - 1; j >= 0; j -= 1) {
                //如果当前元素大于加上步长后的那个元素，则交换元素位置
                if (arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }
        }
        System.out.println("第三轮" + Arrays.toString(arr));*/

    }

    static void swap(int[] arr,int i,int min){
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

移动法

希尔排序时，对有序序列在插入时采用移动法。

代码实现

package sort.shellSort;

import com.sun.prism.shader.Solid_RadialGradient_REFLECT_AlphaTest_Loader;
import java.awt.geom.GeneralPath;
import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,18};

        //shellSorSwap(arr);
        shellSorMove(arr);
    }

    /**
     * 希尔排序 移动法
     */
    private static void shellSorMove(int[] arr) {
        int count = 0;
        for (int gap = arr.length / 2; gap > 0 ; gap /= 2) { //分组
            for (int i = gap; i < arr.length; i++) { //逐步对gap开始的所有元素进行插入排序
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){ //从前往后，所以每一次前面都是有序的，这样如果temp>最后一个元素就不排了
                    while (j - gap >= 0 && temp < arr[j - gap]){ //处理当前分组当前元素下的选择插入排序
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //退出循环说明找打位置
                    arr[j] = temp;
                }
            }
            System.out.println("第"+(++count)+"轮"+Arrays.toString(arr));
        }
    }

    static void swap(int[] arr,int i,int min){
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

快速排序

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

核心思路：分区
分区值：默认选择最左侧元素 pivot
从无序区间选择一个值作为分界点 pivot ，开始扫描原集合，将数组中所有 < 该pivot的元素放在分界点左侧；>= 该元素的值放在分区点的右则。

经过本轮交换，pivot放在了最终位置，pivot的左侧都是小于该值的元素，pivot的右侧都是大于该值的元素，在这两个子区间重复上述过程，直到整个集合有序。

代码实现

import java.util.Arrays;

/**
 * 快速排序
 * **快速排序(Quicksort)是对冒泡排序的一种改进。**
 * **基本思想**:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 *
 * **核心思路**：分区
 * **分区值**：默认选择最左侧元素 pivot
 * 从无序区间选择一个值作为分界点 pivot ，开始扫描原集合，将数组中所有 < 该pivot的元素放在分界点左侧；>= 该元素的值放在分区点的右则。
 *
 * 经过本轮交换，pivot放在了最终位置，pivot的左侧都是小于该值的元素，pivot的右侧都是大于该值的元素，在这两个子区间重复上述过程，直到整个集合有序。
 */
public class quickSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{1,88,12,34,11,22,35,36,39,100,55,18};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        // 左下标
        int l = left;
        // 右下标
        int r = right;

        int temp = 0;
        // 我这里取中轴数为基准数，基准数可随机。
        int pivot = arr[(left + right) / 2];
        // 比pivot小的值放在左边，比pivot大的值放在右边
        while (l < r){
            //在pivot左边一直找到大于等于pivot的值
            while (arr[l] < pivot){
                l += 1;
            }
            //在pivot左边一直找到小于于等于pivot的值
            while (arr[r] > pivot){
                r -= 1;
            }
            //在pivot左右两边的值，已经按照左边全部是小于等于pivot的值，
            // 右边是大于等于pivot的值
            if (l >= r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //交换完成后，发现arr[left] = pivot 相等，前移 r--
            if (arr[l] == pivot){
                r -= 1;
            }
            //交换完成后，发现arr[right] = pivot 相等，l后移 l--
            if (arr[r] == pivot){
                l += 1;
            }

        }

        //如果l == r,必须l++，r--，否则出现栈溢出
        if (l == r){
            l += 1;
            r -= 1;
        }
        //左递归
        if (left < r){
            quickSort(arr,left,r);
        }
        //右递归
        if (right > l){
            quickSort(arr,l,right);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

输出结果

归并排序

基本思想

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起即分而治之)。
对上图说明：
可以看到结构很像一颗二叉树，本文的归并排序采用递归去实现，（也可以采用迭代的方式去实现）分阶段可以理解为就是递归拆分子序列的过程。

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

代码实现

package sort.merge;

import java.util.Arrays;

/**
 * @BelongsProject: data-structure-java
 * @BelongsPackage: sort.merge
 * @Author: xj
 * @CreateTime: 2022-08-04  15:18
 * @Description: 归并排序
 * 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法，
 * 该算法采用经典的分治(divide-and-conquer)策略（分治法将问题分(divide)成一些小的问题然后递归求解，
 * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起即分而治之)。
 * @Version: 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int arr[] ={8,4,5,7,1,3,6,2};
        System.out.println("归并排序前：" + Arrays.toString(arr));
        int[] temp = new int[arr.length];
        sort(arr,0,arr.length - 1, temp);
        System.out.println("归并排序前：" + Arrays.toString(arr));
    }


    public static void sort(int[] arr,int left,int right,int temp[]){
        if (left < right){
            // 中间索引
            int mid = (left + right) / 2;
            //左递归
            sort(arr,left,mid,temp);
            // 右递归
            sort(arr,mid + 1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     *
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    static void merge(int[] arr,int left,int mid,int right,int temp[]){
        // 初始化i，左边有序序列的初始索引
        int i = left;
        // 初始化j，右边有序序列的初始化索引
        int j = mid + 1;
        // 指向temp数组的临时索引
        int t  = 0;

        /*
        第一步
        先把左右两边的有序数据按照规则填充到temp数组
        直到两边的有序序列，有一边处理完成。
         */
        while (i <= mid && j <= right){
            /*
            若左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            将左边的单前元素，赋值给temp数组
            然后t++ ，i++
             */
            if (arr[i] < arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        /*
        第二步
        把有剩余数据的一边的数据依次全部填充到temp
         */
        while (i <= mid){
            temp[t] = arr[i];
            i++;
            t++;
        }
        while (j <= right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        /*
        第三步
        将temp数组的元素拷贝到arr
         */
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

输出结果

基数（桶）排序

基本思想

• 基数排序（radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
• 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
• 基数排序(Radix Sort)是桶排序的扩展。
• 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较。

图文说明

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

• 基数排序是对传统桶排序的扩展，速度很快.
• 基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError 。
• 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=rli]，且r[i]在ri]之前，而在排序后的序列中，rti]仍在rüi]之前，则称这种排序算法是稳定的;否则称为不稳定的]
• 有负数的数组,我们不用基数排序来进行排序，如果要支持负数，请查阅其他资料。

代码实现

package sort.RadixSort;

import javax.xml.transform.Source;
import java.util.Arrays;

/**
 * @BelongsProject: data-structure-java
 * @BelongsPackage: sort.RadisSort
 * @Author: xj
 * @CreateTime: 2022-08-05  10:47
 * @Description: 基数排序
 * @Version: 1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{53,3,542,748,14,214};
        System.out.println("排序前："+ Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后："+ Arrays.toString(arr));

    }

    static void radixSort(int[] arr){
        //获取到数组中最大的数的位数
        int max =arr[0]; //假设第一个数就是最大数
        for (int ele : arr){
            if (ele > max){
                max = ele;
            }
        }
        int maxLength = (max + "").length();

        //第一次排序，针对每个元素的个位数进行排序处理。
        // 为了防止元素入桶的时候数据溢出，给我每个桶的大小设置为arr.length
        //定义二维数组，表示10个桶，每个桶就是一个一维数组。空间换时间的经典算法
        int[][] bucket =new int[10][arr.length];
        //记录每个桶中实际存放的元素个数，定义一个一维数组记录每个桶的元素个数
        //bucketElementCount[0] 记录bucket[0]的数据个数
        int[] bucketElementCount = 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][bucketElementCount[digitOfElement]] = arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //按照桶的顺序，根据一维数组的下标依次取出数据，放入到原数组
            int index = 0;
            //遍历每个bucket，并将桶中的元素放入到原数组。
            for (int k = 0; k < bucketElementCount.length; k++) {
                //如果桶中有数据，放入到原数组
                if (bucketElementCount[k] != 0){
                    //遍历该桶元素
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        //取出元素放入到arr
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketElementCount[k] = 0;
            }

        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

输出结果

总结

插播小广告，我的公众号,试运行哈哈哈，虽然还没有内容，但是爱学习你一定会给我点个关注吧