数据结构与算法 八种基本算法

发表于 阅读次数：
本文字数： 8.9k 阅读时长 ≈ 8 分钟

昌图

数据结构与算法基础

八种常用排序方法

交换排序

  • 冒泡排序

原理就是与后一个进行比较、然后根据大小决定是否进行交换位置、将得到结果放在后面最后形成排序结果

代码示例

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
public class BubbleSort {

    public static void main(String[] args) {
        //声明一个数组
        int[] arr = new int[]{5,7,2,8,9,4,1,0,5,7};
        //显示原数组
        System.out.println(Arrays.toString(arr));
        //调用冒泡排序方法
        bubbleSort(arr);
        //显示排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        //比较次数、控制比较几轮
        for(int i = 0; i < arr.length - 1; i++){
            //控制与他后面的进行比较、最后一个不进行比较
            for(int j = 0; j < arr.length - 1 - i; j++){
                //定义一个中间量暂时存放数据
                int temp;
                //如果前一个比后一个大、数据交换
                if(arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = 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
public class QuickSort {

    public static void main(String[] args) {
        //声明一个数组
        int[] arr = new int[]{3,4,6,7,2,7,2,8,0,9,1};

        //显示原数组
        System.out.println(Arrays.toString(arr));

        //调用快速排序方法
        quickSort(arr,0,arr.length - 1);

        //显示排序后的数组
        System.out.println(Arrays.toString(arr));
    }


    public static void quickSort(int[] arr,int start, int end){

        //当开始位置小于结束位置时执行
        if(start < end){

            //将第一个作为目标标准数
            int stard = arr[start];
            //记录数据小的和数据大的下标
            int low = start;
            int hight = end;

            //循环找出比标准数大的和比标准数小的
            while (low < hight){
                //如果高的数据比目标数大则保持数据不变、并移动下标
                while (low < hight && stard <= arr[hight]){
                    hight--;
                }
                //这里经过上面条件处理后这里的高位置数据小于目标数所以放到低位置
                arr[low] = arr[hight];

                //如果低的数据比目标数小则保持数据不变、并移动下标
                while (low < hight && stard >= arr[low]){
                    low++;
                }
                //这里经过上面条件处理后这里的低位置数据大于目标数所以放到高位置
                arr[hight] = arr[low];
            }
            //将目标数给低位置上面
            arr[low] = stard;

            //递归处理所有小的数据、将起始位置设置为0、将结束位置设置为目标数下标
            quickSort(arr,start,low);

            //递归处理所有大的数据、将起始位置设置为目标数下标+1、将结束位置设置为数组最后元素
            quickSort(arr,low + 1,end);
        }
    }
}

插入排序

  • 直接插入排序

原理就是判断当前的这个数据值与他前一个数据的值的关系、从小到大就是当前这个数据比前一个数据小、则将当前数据存放到中间变量中、然后将前一个赋值给当前变量、将中间变量一直与前一个数据判断、最后中间变量赋值给不符合题意的、从大到小反之即可、但是效率不怎么好

代码示例

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
public class InsertSort {

    public static void main(String[] args) {
        //声明一个数组
        int[] arr = new int[]{5,3,2,8,5,9,1,0};

        //显示原数组
        System.out.println(Arrays.toString(arr));
        //调用插入排序方法
        insertSort(arr);
        //显示排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){

        //遍历所有数据
        for(int i = 1; i < arr.length; i++){

            //判断后一个是否比前一个数据小
            if(arr[i] < arr[i - 1]){

                //定义一个中间变量来存放小的那个数据
                int temp = arr[i];
                //定义一个变量j
                int j;

                //遍历当前数字的所有前面的数字
                for(j = i - 1; j >= 0&&temp<arr[j]; j--){
                    //将前一个赋值给后一个
                    arr[j + 1] = arr[j];
                }
                //将中间变量temp赋值给不满足条件的那个值
                arr[j + 1] = 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
public class ShellSort {

    public static void main(String[] args) {

        //定义数组
        int[] arr = new int[] { 3, 5, 2, 7, 8, 1, 2, 0, 4, 7, 4, 3, 8 };

        //显示原数组
        System.out.println(Arrays.toString(arr));

        //调用希尔排序方法
        shellSort(arr);

        //显示排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){

        // 遍历所有的步长
        for(int d = arr.length / 2; d > 0; d /= 2){
            // 遍历所有有元素
            for(int i = d; i < arr.length; i++){
                // 遍历本组中所有的元素
                for(int j = i - d; j >= 0; j -= d){
                    // 如果当前元素大于加上步长后的那个元素
                    if(arr[j] > arr[j + d]){

                        //交换位置
                        int temp = arr[j];
                        arr[j] = arr[j + d];
                        arr[j + d] = 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
public class SelectSort {

    public static void main(String[] args) {

        //声明数组
        int[] arr = new int[]{2,7,5,8,1,6,9,0,4,3};

        //显示原数组
        System.out.println(Arrays.toString(arr));

        //调用选择排序方法
        selectSort(arr);

        //显示排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr){

        //遍历所有元素
        for(int i = 0; i < arr.length; i++){
            //定义最小值
            int min = i;
            //定义中间值
            int temp;
            //遍历最小值的其他值
            for(int j = i + 1; j < arr.length; j++){

                //判断最小值和其他值的关系、并进行排序交换
                if(arr[min] > arr[j]){
                    temp = arr[min];
                    arr[min] = arr[j];
                    arr[j] = 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
public class MergeSort {

    public static void main(String[] args) {

        //定义一个数组
        int[] arr = new int[] {1,3,5,2,4,6,8,10};
        //显示数组
        System.out.println(Arrays.toString(arr));
        //调用归并排序方法
        mergeSort(arr,0,arr.length - 1);
        //显示排序后的数组
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 归并排序
     * @param arr   数组
     * @param low   开始下标
     * @param hight 结束下标
     */
    public static void mergeSort(int[] arr,int low, int hight){
        //取出中间值
        int middle = (low + hight ) / 2;

        if(low < hight){

            //递归左边那个数组
            mergeSort(arr,low, middle);

            //递归右边那个数组
            mergeSort(arr,middle + 1,hight);

            //调用归并方法、进行归并
            merge(arr,low,middle,hight);

        }
    }

    /**
     * 归并
     * @param arr   数组
     * @param low   开始下标
     * @param middle    中间下标
     * @param hight 结束下标
     */
    public static void merge(int[] arr,int low, int middle,int hight){

        //定义一个临时数组
        int[] temp = new int[hight - low +1];
        //第一个数组的开始下标
        int i = low;
        //第二个数组的开始下标
        int j = middle + 1;
        //临时数组下标
        int index = 0;

        //遍历两个数组取出小的数字，放入临时数组中
        while (i <= middle && j <= hight){
            //判断两个数组中哪个数据更小
            if(arr[i] <= arr[j]){
                //将小的存储临时数组中
                temp[index++] = arr[i++];
            }else{
                //将小的存储临时数组中
                temp[index++] = arr[j++];
            }
        }

        //处理多余的数据
        while (i <= middle ){
            temp[index++] = arr[i++];
        }
        //处理多余的数据
        while (j <= hight){
            temp[index++] = arr[j++];
        }
        //把临时数组中的数据重新存入原数组
        for(int k=0;k<temp.length;k++) {
            arr[k+low]=temp[k];
        }
    }
}
  • 堆排序

基数排序

原理就是找到数组当中的最大数是几位数、然后就排几次、依次按个十百千万开始排、用几个临时数组依次存储个十百千万位为0~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
public class RadixSort {

    public static void main(String[] args) {

        //定义数组
        int[] arr = new int[] {23,6,189,45,9,287,56,1,798,34,65,652,5};
        //显示原数组
        System.out.println(Arrays.toString(arr));
        //调用基数排序方法
        radixSort(arr);
        //显示排序后的数组
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 基数排序
     * @param arr
     */
    public static void radixSort(int[] arr){

        //定义一个最大值变量
        int max = Integer.MAX_VALUE;

        //遍历数组找出最大值
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }
        //取出最大值的位数
        int maxLength = (max + "").length();

        //创建临时存放数据的二维数组
        int temp[][] = new int[10][arr.length];

        //创建存储临时数据数量的数组
        int counts[] = new int[10];

        //根据最大长度的数决定比较的次数
        for(int i = 0,n = 1; i < maxLength; i++,n *= 10){
            //把每一个数字分别计算余数
            for(int j = 0; j < arr.length; j++){
                //计算余数
                int ys = arr[j] / n % 10;
                //把当前遍历的数据放入指定的数组中
                temp[ys][counts[ys]] = arr[j];
                //记录数量
                counts[ys]++;
            }
            
            //记录原数组下标
            int index = 0;

            //遍历数量的数组
            for(int k = 0; k < counts.length; k++){
                //如果数组里面有数据则赋值
                if(counts[k] != 0){
                    //遍历数组里面的数据依次顺序赋值给原数组
                    for(int l = 0; l < counts[k]; l++){
                        arr[index++] = temp[k][l];
                    }
                    //赋值后将当前这个数组的数量清零
                    counts[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
public class RadixQueueSort {

    public static void main(String[] args) {

        //定义数组
        int[] arr = new int[] {23,6,189,45,9,287,56,1,798,34,65,652,5};
        //显示原数组
        System.out.println(Arrays.toString(arr));
        //调用基数排序方法
        radixSort(arr);
        //显示排序后的数组
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 基数排序
     * @param arr
     */
    public static void radixSort(int[] arr){

        //定义一个最大值变量
        int max = Integer.MAX_VALUE;

        //遍历数组找出最大值
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }
        //取出最大值的位数
        int maxLength = (max + "").length();

        //创建临时存放数据的对列
        MyQueue[] queue = new MyQueue[10];
        for(int i = 0; i < queue.length; i++){
            queue[i] = new MyQueue();
        }

        //根据最大长度的数决定比较的次数
        for(int i = 0,n = 1; i < maxLength; i++,n *= 10){
            //把每一个数字分别计算余数
            for(int j = 0; j < arr.length; j++){
                //计算余数
                int ys = arr[j] / n % 10;
                //把当前遍历的数据放入指定的数组中
                queue[ys].add(arr[j]);
            }

            //记录原数组下标
            int index = 0;

            //遍历数量的数组
            for(int k = 0; k < queue.length; k++){

                while (!queue[k].isEmpty()){
                    arr[index++] = queue[k].poll();
                }
            }
        }
    }
}

对列

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
public class MyQueue {

    //定义一个数组
    private int[] elements;

    //初始化
    public MyQueue(){
        this.elements = new int[0];
    }

    /**
     * 入队
     * @param element
     */
    public void add(int element){
        //创建一个新的数组、长度为原数组+1
        int[] newArr = new int[elements.length + 1];

        //添加数据
        for(int i = 0; i <elements.length; i++){
            newArr[i] = elements[i];
        }
        newArr[elements.length] = element;

        //更新原数组
        this.elements = newArr;
    }

    /**
     * 出队
     * @return
     */
    public int poll(){

//        出队
        int element = this.elements[0];

//        创建新数组
        int[] newArr = new int[elements.length - 1];

//        将数据赋值到新数组
        for(int i = 0; i < newArr.length; i++){
            newArr[i] = elements[i +1];
        }

//        数据更新
        this.elements = newArr;

//        返回出队数据
        return element;
    }

    /**
     * 队列是否为空
     * @return
     */
//    public String isEmpty(){
//
//        return this.elements.length == 0?"队列为空":"队列不为空";
//    }

    public Boolean isEmpty(){
        return this.elements.length == 0;
    }
}

正确的开始、微小的长进、然后持续、嘿、我是小博、带你一起看我目之所及的世界……

-------------本文结束 感谢您的阅读-------------

本文标题:数据结构与算法 八种基本算法

文章作者:小博

发布时间:2021年08月09日 - 12:57

最后更新:2021年08月09日 - 12:59

原始链接:https://codexiaobo.github.io/posts/1028172237/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。