算法

算法

查找算法

基本查找

也叫顺序查找

​ 说明：顺序查找适合存储结构为数组或者链表

基本思想：

顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。

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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 15:34
 * @Version 1.0   顺序查找（基本查找）
 */
public class BasicSearchDemo {

    public static void main(String[] args) {
        /**
         * 顺序查找：属于无序查找算法，从数据的一端开始到另一端结束，
         * 依次比较,如果比较的值相等则表示查找成功，
         * 如果遍历结束没有找到相同的，表示查找失败
         *
         * 核心：从0索引挨个往后查找
         */
        int arr[] = {1,6,2,8,45,123};
        int number = 123;
        boolean b = basicSearch(arr, number);
        System.out.println(b);
    }

    private static boolean basicSearch(int[] arr, int number) {
        //利用基本查找来查找number在数组是否存在
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]==number){
                return true;
            }
        }
        return false;
    }
}

二分查找

也叫折半查找

​ 说明：元素必须是有序的，从小到大或者从大到小都是可以的

​ 如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

基本思想：

​ 也称为是折半查找，属于有序查找算法。给定值先与中间节点比较。比较完之后有三种情况

  • 相等：说明找到了
  • 要查找的数据比中间节点小：说明要查找的数字在中间节点的左边
  • 要查找的数据比中间节点大：说明要查找的数字在中间节点的右边
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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 15:44
 * @Version 1.0 二分查找
 */
public class BinarySearchDemo {
    public static void main(String[] args) {
        /**
         * 二分查找/折半查找
         *  核心：每次排除一半的查找范围
         *  要求：数据必须有序，从小到大或者从大到小都行
         */
        int arr[] = {1,2,3,4,5,6,78,123,156,198,234};
        int number=234;
        System.out.println(binarySearch(arr, number));

    }

    private static int binarySearch(int[] arr, int number) {
        int start=0;
        int end = arr.length-1;
        while (true){

            if (start>end){
                //当start大于end表示查找完了，跳出循环,如果是等于的话，处于最边缘的数，就找不到
                return -1;
            }

            int mid =  (start+end)/2;
            if (number>arr[mid]){
                //如果要查找的值大于中间值，就要调整start的下标
                start=mid+1;
                mid=(start+end)/2;
            }else if (number<arr[mid]){
                //如果要查找的值小于中间值，就要调整end的下标
                end=mid-1;
                mid=(start+end)/2;
            }else{
                //要查找的值等于中间值
                return mid;
            }
        }
    }
}

插值查找

在介绍插值查找之前，先考虑一个问题：

​ 为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？

其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？

二分查找中查找点计算如下：

　　mid=(low+high)/2, 即mid=low+1/2*(high-low);

我们可以将查找的点改进为如下：

　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

这样，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。

细节：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

代码跟二分查找类似，只要修改一下mid的计算方式即可。

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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 16:13
 * @Version 1.0 插值查找
 */
public class InterpolationSearchDemo {
    public static void main(String[] args) {
        /**
         * 主要是为了让mid尽可能的靠近想要查找的元素，这样就能提高效率
         * 可以将二分查找的计算公式(因为min或者max是会变，这样取的是实时的下标)
         *  mid=(min+max)/2  即mid=min+1/2*(max-min)
         * 我们可以将查找的点改进为：
         *  mid = min+(key-a[min])/(a[max]-a[min])*(max-min)
         *  主要是(将key与最小值)/(最小值与最大值的比例)*(最小值与最大值的下标差)
         */
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int number=7;
        int index = interpolationSearch(arr,number);
        System.out.println(index);
    }

    private static int interpolationSearch(int[] arr, int number) {
        int min=0;
        int max = arr.length-1;
        while (true){
            if (min>max){
                //当start大于end表示查找完了，跳出循环,如果是等于的话，处于最边缘的数，就找不到
                return -1;
            }
            if (number>arr[max]||number<arr[min]){
                //当传入的值大于最右边的最大值或者小于最左边的最小值，则不需要找了
                return -1;
            }
            int mid = min+((number-arr[min])/(arr[max]-arr[min])*(max-min));

            if (number>arr[mid]){
                //如果要查找的值大于中间值，就要调整start的下标
                min=mid+1;
                mid=min+((number-arr[min])/(arr[max]-arr[min])*(max-min));
            }else if (number<arr[mid]){
                //如果要查找的值小于中间值，就要调整end的下标
                max=mid-1;
                mid=min+((number-arr[min])/(arr[max]-arr[min])*(max-min));
            }else{
                //要查找的值等于中间值
                return mid;
            }
        }
    }
}

斐波那契查找

在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

　　黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

　　0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

　　在数学中有一个非常有名的数学规律：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

（从第三个数开始，后边每一个数都是前两个数的和）。

然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

img

基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

斐波那契查找也是在二分查找的基础上进行了优化，优化中间点mid的计算方式即可

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
public class FeiBoSearchDemo {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契数分割数的下标值
        int index = 0;
        int mid = 0;
        //调用斐波那契数列
        int[] f = getFeiBo();
        //获取斐波那契分割数值的下标
        while (high > (f[index] - 1)) {
            index++;
        }
        //因为f[k]值可能大于a的长度，因此需要使用Arrays工具类，构造一个新法数组，并指向temp[],不足的部分会使用0补齐
        int[] temp = Arrays.copyOf(arr, f[index]);
        //实际需要使用arr数组的最后一个数来填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循环处理，找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向数组的前面部分进行查找
                high = mid - 1;
                /*
                  对k--进行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面继续查找k--
                  即下次循环,mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向数组的后面的部分进行查找
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要确定返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

分块查找

当数据表中的数据元素很多时，可以采用分块查找。

汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找

分块查找的过程：

  1. 需要把数据分成N多小块，块与块之间不能有数据重复的交集。
  2. 给每一块创建对象单独存储到数组当中
  3. 查找数据的时候，先在数组查，当前数据属于哪一块
  4. 再到这一块中顺序查找
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 16:49
 * @Version 1.0 分块查找
 */
public class BlockSearchDemo {
    public static void main(String[] args) {
        /**
         * 核心思想：块内无序，块间有序
         * 实现步骤：
         *  1.创建数组blockArr存放每一块对象的信息
         *  2.先查找blockArr确定要查找的数据属于那一块
         *  3.在单独遍历这一块数据
         *
         *  注意：
         *      1.分块个数一般等于数组中的数量个数的开根号。比如16的开根号是4，则一般分成4块
         *      2.分块的个数中前一块的最大值要小于后一块的最小值（如果不满足这个条件，则需要使用无规律的方式去分块）
         */
        regularBlockSearch();
        noRegularBlockSearch();
    }

    /**
     * 有规律的分块查找（无规律查找，需要将分块的数据范围无数据交集）
     */
    private static void noRegularBlockSearch() {
        int[] arr ={27,22,30,40,36,
                    13,19,16,20,
                    7,10,
                    43,50,48
        };
        //创建4个块对象
        NoBlock no1 = new NoBlock(22,40,0,4);
        NoBlock no2 = new NoBlock(13,20,5,8);
        NoBlock no3 = new NoBlock(7,10,9,10);
        NoBlock no4 = new NoBlock(43,50,11,13);
        //定义数组用来管理三个块的对象（索引表）
        NoBlock[] noBlockArr = {no1,no2,no3,no4};
        //定义一个变量用来记录要查找的元素
        int number = 30;

        //判断属于那个块中
        int noBlockIndex=-1;
        for (int i = 0; i < noBlockArr.length; i++) {
            if (noBlockArr[i].getMin()<=number&&noBlockArr[i].getMax()>=number){
                noBlockIndex=i;
                break;
            }
        }

        if (noBlockIndex!=-1){
            //输入的数据，存在对应的块中
            NoBlock noBlock = noBlockArr[noBlockIndex];
            int startIndex = noBlock.getStartIndex();
            int endIndex = noBlock.getEndIndex();

            //3.遍历
            int result=-1;
            for (int i = startIndex; i <= endIndex; i++) {
                if(arr[i] == number){
                    result=i;
                    break;
                }
            }
            if (result!=-1){
                System.out.println("所属下标:"+result);
            }else{
                System.out.println("未找到数据");
            }

        }else{
            System.out.println("未找到数据");
        }
    }


    /**
     * 有规律的分块查找（满足分块的个数中前一块的最大值要小于后一块的最小值）
     */
    private static void regularBlockSearch() {
        int[] arr = {16, 5, 9, 12,21, 18,
                32, 23, 37, 26, 45, 34,
                50, 48, 61, 52, 73, 66};

        //创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定义数组用来管理三个块的对象（索引表）
        Block[] blockArr = {b1,b2,b3};

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr,arr,number);

        //打印一下
        System.out.println(index);
    }

    //利用分块查找的原理，查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
    }


    //定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block[] blockArr,int number){ //100

        //从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }

}

class NoBlock{
    //块中最小值
    private int min;
    //块中最大值
    private int max;
    //起始索引
    private int startIndex;
    //结束索引
    private int endIndex;
    private NoBlock(){}

    public NoBlock(int min, int max, int startIndex, int endIndex) {
        this.min = min;
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}


class Block{
    //最大值
    private int max;
    //起始索引
    private int startIndex;
    //结束索引
    private int endIndex;

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}

哈希查找

哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。

一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体

为了让大家方便理解，所以规定：

  • 数组的0索引处存储1~100
  • 数组的1索引处存储101~200
  • 数组的2索引处存储201~300
  • 以此类推

但是实际上，我们一般不会采取这种方式，因为这种方式容易导致一块区域添加的元素过多，导致效率偏低。

更多的是先计算出当前数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的位置，再挂在数组的后面形成链表，如果挂的元素太多而且数组长度过长，我们也会把链表转化为红黑树，进一步提高效率。

Snipaste_2022-09-05_21-36-50

数表查找

​ 基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

　　二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree），具有下列性质的二叉树：

　　1）若任意节点左子树上所有的数据，均小于本身；

　　2）若任意节点右子树上所有的数据，均大于本身；

　　二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

​ 不同形态的二叉查找树如下图所示：

20180226113852869

　　基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

​ 不管是二叉查找树，还是平衡二叉树，还是红黑树，查找的性能都比较高

排序算法

冒泡排序

​ 冒泡排序（Bubble Sort）也是一种简单直观的排序算法。

它重复的遍历过要排序的数列，一次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。

这个算法的名字由来是因为越大的元素会经由交换慢慢”浮”到最后面。当然，大家可以按照从大到小的方式进行排列。

算法步骤

  1. 相邻的元素两两比较，大的放右边，小的放左边
  2. 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推
  3. 如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以

冒泡

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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 17:31
 * @Version 1.0 冒泡排序
 */
public class BubbleDemo {
    public static void main(String[] args) {
        /**
         * 核心思想
         *  1.相邻的元素两两比较，大的放右边，小的放左边
         *  2.第一轮比较完毕，最大值已经确定，第二轮可以少循环一次，后面依此类推
         *  3.如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以
         *
         */
        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};
        //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5

        //外循环：表示我要执行多少轮。 如果有n个数据，那么执行n - 1 轮
        for (int i=0;i<arr.length-1;i++){
            //内循环：表示我能做什么。每一轮中我如何比较数据并找到当前的最大值，拿着下标从0开始的相邻的两个数比较并交换
            //-1:是为了防止索引越界
            //-i:提高效率，每一轮执行的次数应该比上一轮少一次，因为每次执行完下面的循环就能确定一个值的位置
            for (int j=0;j<arr.length-1-i;j++){
                //比较数据，满足条件的交换
                if(arr[j]>arr[j+1]){
                    int temp =arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        printArr(arr);
    }

    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

选择排序

算法步骤

  1. 从0索引开始，跟后面的元素一一比较
  2. 小的放前面，大的放后面
  3. 第一次循环结束后，最小的数据已经确定
  4. 第二次循环从1索引开始以此类推
  5. 第三轮循环从2索引开始以此类推
  6. 第四轮循环从3索引开始以此类推。

选择排序

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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 17:46
 * @Version 1.0 选择排序
 */
public class SelectionDemo {

    public static void main(String[] args) {
        /**
         * 选择排序：
         *  1.从0索引开始，跟后面的元素一一比较
         *  2.小的放前面，大的放后面
         *  3.一次循环结束后，最小的数据已经确定
         *  4.第二次循环从1索引开始以此类推
         */
        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};


        //2.利用选择排序让数组变成 1 2 3 4 5
        //外循环：比较的轮数
        //i:表示这一轮中，我拿着那个索引上的数据区更后面的数据进行比较并交换
        for (int i = 0; i < arr.length-1; i++) {
            //内循环：每一轮我要干什么事情
            //拿着i和i后面的数据进行比较并交换
            for(int j=i+1;j<arr.length;j++){
                //比较并交换
                if (arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i]= arr[j];
                    arr[j]=temp;
                }
            }
        }
        printArr(arr);
    }
    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过创建有序序列和无序序列，然后再遍历无序序列得到里面每一个数字，把每一个数字插入到有序序列中正确的位置。

插入排序在插入的时候，有优化算法，在遍历有序序列找正确位置时，可以采取二分查找

插入排序

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
package com.zhuixun.demo;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 18:03
 * @Version 1.0 插入排序
 */
public class InsertDemo {

    public static void main(String[] args) {
        /**
         * 插入排序：
         *    1. 将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
         *    2. 遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
         *    3. N的范围：0~最大索引
         */

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到无序的哪一组数组是从哪个索引开始的。  2
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > arr[i + 1]){
                startIndex = i + 1;
                break;
            }
        }

        //2.遍历从startIndex开始到最后一个元素，依次得到无序的那一组数据中的每一个元素
        for (int i=startIndex;i<arr.length;i++){
            //记录当前要插入数据的索引
            int j=i;
            //将无序数组的数据依次和有序数组中数据从大往小比较
            while (j>0&&arr[j]<arr[j-1]){
                //交换位置
                int temp = arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
                //这边是为了继续往下比较有序数组中的数据
                j--;
            }
        }
        printArr(arr);
    }
    private static void printArr(int[] arr) {
        //3.遍历数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。

快速排序又是一种分而治之思想在排序算法上的典型应用。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！

它是处理大数据最快的排序算法之一了。

算法步骤

  1. 从数列中挑出一个元素，一般都是左边第一个数字，称为 “基准数”;
  2. 创建两个指针，一个从前往后走，一个从后往前走。
  3. 先执行后面的指针，找出第一个比基准数小的数字
  4. 再执行前面的指针，找出第一个比基准数大的数字
  5. 交换两个指针指向的数字
  6. 直到两个指针相遇
  7. 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。
  8. 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。
  9. 把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序

快速排序

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
package com.zhuixun.demo;

import java.util.Arrays;

/**
 * @Author： zhuixun
 * @Date: 2022/12/31 18:13
 * @Version 1.0
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        /**
         * 快速排序：
         *    第一轮：以0索引的数字为基准数，确定基准数在数组中正确的位置。
         *    比基准数小的全部在左边，比基准数大的全部在右边。
         *    后面以此类推。
         */
        int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};


        //int[] arr = new int[1000000];

       /* Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }*/
        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();

        System.out.println(end - start);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param arr  我们要排序的数组
     * @param i  要排序数组的起始索引
     * @param j  要排序数组的结束索引
     */
    public static void quickSort(int[] arr, int i, int j) {
        //定义两个变量记录要查找的范围
        int start = i;
        int end = j;

        if(start > end){
            //递归的出口
            return;
        }



        //记录基准数
        int baseNumber = arr[i];
        //利用循环找到要交换的数字
        while(start != end){
            //利用end，从后往前开始找，找比基准数小的数字，注意这边一定要先从后面开始找
            //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
            while(true){
                if(end <= start || arr[end] < baseNumber){
                    //找到小于基准数和左边大于基准数进行交换
                    break;
                }
                end--;
            }
            System.out.println(end);
            //利用start，从前往后找，找比基准数大的数字
            while(true){
                if(end <= start || arr[start] > baseNumber){
                    break;
                }
                start++;
            }



            //把end和start指向的元素进行交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        //当start和end指向了同一个元素的时候，那么上面的循环就会结束
        //表示已经找到了基准数在数组中应存入的位置
        //基准数归位
        //就是拿着这个范围中的第一个数字，跟start指向的元素进行交换
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        //确定6左边的范围，重复刚刚所做的事情 ，这边用end和start都可以，因此此时start==end，这边使用的是递归思想
        quickSort(arr,i,start - 1);
        //确定6右边的范围，重复刚刚所做的事情
        quickSort(arr,start + 1,j);

    }
}

JavaBase
#查找算法 #排序算法
算法
http://example.com/2023/01/29/Java基础/算法/algorithm/
作者
zhuixun
发布于
2023年1月29日
许可协议