2022-06-27 数据结构与算法-递归、冒泡、插入、选择排序

• 递归
• 冒泡排序（Bubble Sort）
• 插入排序（Insert Sort）*常用
• 选择排序（Select Sort）

需要满足的三个条件：

1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

注意事项

• 递归代码要警惕堆栈溢出
• 递归代码要警惕重复计算

如何将递归代码改写为非递归代码：递归是倒着推出答案，利用例如f(n)=f(n-1) + f(n-2)与子问题的关系加上终止条件，得出的代码；因此只需要正从终止条件求出问题答案即可

每边都需要交换比较结果的元素

package com.zsl.datastructalgorithm.date20220627;

import java.util.Arrays;


public class BubbleSort {

    public static void main(String[] args) {
        int[] ints = {44, 54, 523, 5, 6, 1, 543, 66, 7};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public static void sort(int[] elements) {
        if (elements.length < 2) {
            return ;
        }

        for (int i = 1; i < elements.length; i++) {
            boolean swap = false;
            for (int j = 0; j < elements.length - i; j++) {
                if (elements[j + 1] < elements[j]) {
                    int tmp = elements[j + 1];
                    elements[j + 1] = elements[j];
                    elements[j] = tmp;
                    swap = true;
                }
            }
            if (!swap) break;
        }
    }
}

每次插入，选择合适的位置，即插入过程中排序，后面的元素向后移动

package com.zsl.datastructalgorithm.date20220627;

import java.util.Arrays;


public class InsertSort {

    public static void main(String[] args) {
        int[] ints = {44, 54, 523, 5, 6, 1, 543, 66, 7};

        sort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public static void sort(int[] elements) {
        if (elements.length < 2) {
            return ;
        }

        for (int i = 1; i < elements.length; i++) {
            for (int j = 0; j < i; j++) {
                // 找到位置，将index i,作为存储位置，进行移动
                if (elements[i] < elements[j]) {
                    int tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;
                }
            }
        }
    }
}

每次选择最大或最小元素进行交换，只交换一次，但不是稳定的排序

package com.zsl.datastructalgorithm.date20220627;

import java.util.Arrays;


public class SelectSort {
    public static void main(String[] args) {
        int[] ints = {44, 54, 523, 5, 6, 1, 543, 66, 7};
        sort(ints);
        System.out.println(Arrays.toString(ints));
    }

    public static void sort(int[] elements) {
        if (elements.length < 2) {
            return ;
        }

        for (int i = 0; i < elements.length; i++) {
            int minIndex = i;
            for (int j = i; j < elements.length; j++) {
                if (elements[j] < elements[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = elements[minIndex];
            elements[minIndex] = elements[i];
            elements[i] = tmp;
        }
    }
}