冒泡排序、选择排序、直接插入排序

冒泡排序

import java.util.Arrays;

/**
 * @author dengqixing
 * @date 2021/4/17
 */
public class BubbleSort {
    public static void main(String[] args) {
        // 1、定义无序数组
        int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};
//        int[] arr = {12, 21, 23, 26, 44, 58, 59, 89, 94, 98};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
        // 外循环，至少比较数组长度减一，因为最后一个元素无需再进行比较
        for (int i = 0; i < arr.length - 1; i++) {
            // 默认序列是有序的
            boolean flag = true;
            // 内循环，由于每次比较都会有一个最大或最小的数被放在最边缘的位置，所以每次循环时都需要对应的减少比较的次数
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                    // 如果第一次小循环进行过交换，说明序列不是有序的,否则说明是有序的
                    flag = false;
                }
            }
            // 这么做如果数组已经是有序了，则无需继续进行比较，减少循环次数，增加效率
            if (flag) {
                break;
            }
        }

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

class SelectSort {
    public static void main(String[] args) {
        // 1、定义无序数组
        int[] arr = {89, 59, 44, 12, 58, 26, 94, 98, 21, 23};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
        // 外循环，需要 n - 1的循环次数
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            // 进行交换
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
}

选择排序与冒泡排序的注意事项

• 冒泡排序至多需要n-1趟循环，最少一趟循环；其中n为长度
• 选择排序一定需要n-1躺循环，一趟也不能少
• 冒泡排序中最多的操作就是比较和交换，一趟循环中可能发生多次交换；
• 选择排序中最多的操作就是比较，一趟比较结束后发现更小(或更大)的值才进行交换
• 所以更推荐使用冒泡。

小案例，使用选择排序完成对对象的排序

class SelectSort2 {
    public static void main(String[] args) {
        // 1、定义无序数组
        Comparable[] arr = {new Person(14,"李四"),new Person(18,"李四"),new Person(16,"李四")};

        // 2、输出无序数组
        System.out.println(Arrays.toString(arr));
        // 3、排序
       selectSort(arr);

        // 4、输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }

    private static void selectSort(Comparable[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex].compareTo(arr[j]) > 0) {
                    minIndex = j;
                }
            }
            // 进行交换
            if (minIndex != i) {
                Comparable temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}


class Person implements Comparable<Person> {
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }


    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public int compareTo(Person p) {
        return Integer.compare(this.getAge(), p.getAge());
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

直接插入排序(插入排序)

public static void insertSort(int[] arr) {
        // 默认第一个元素是有序序列，所以从1开始
        for (int i = 1; i < arr.length; i++) {
            // 临时变量存储当前需要插入的数据
            int temp = arr[i];
            // 存储有序序列的元素下标位置
            int j = i - 1;
            // 如果当前的元素小于需要比较的元素
            while (j >= 0 && temp < arr[j]) {
                // 将当前正在比较的元素放入其后面的位置
                arr[j + 1] = arr[j];
                // 继续往左进行数据比较
                j--;
            }
            // 循环结束后，将其比较的元素放在最后比较的一个元素的后面
            arr[j + 1] = temp;
        }
    }

快速排序（比较排序中效率最高的一种排序）

原理：

• 首先得到一个无序序列
• 随机选取其中一个数为基准数(一般默认为最左侧的第一个元素)
• 然后会有两个指针分别在当前需要比较的序列的最左侧和最右侧
• 先从最右侧开始往左移动比较，一旦碰到了大于或者相等于基准数的元素，则继续向左移动，直到指针所指向的元素小于基准数，就停下(还有一个条件，左边的索引必须小于右边的索引)
• 然后从最左侧开始向右移动比较，一旦碰到了小于或者相等于基准数的元素，则继续向右移动，直到指针所指向的元素大于基准数，就停下（左边的索引必须小于右边的索引）
• 如果左指针与右指针相等（也就是相遇了），则将其相遇位置的元素与基准数进行交换
• 最后再将基准数左边的序列再次进行快速排序
• 将基准数右边的序列再次进行快速排序

public static void main(String[] args) {
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            // 随机存入1到10万之间的数字
            arr[i] = (int)(Math.random() * 100000)+1;
        }

        // 排序
        long start = System.currentTimeMillis();
        quickSort(arr, 0 , arr.length -1);
        long end = System.currentTimeMillis();
	//19357毫秒，排序1亿个数字的序列竟只用了19秒，
	冒泡排序在10万数据时就已耗时15秒左右，快速排序在10万数据时耗时只有20-30毫秒
        System.out.println("运行时间为 :" + (end - start));
}

    public static void quickSort(int[] arr, int left, int right) {
        // 如果左边索引比右边索引还要大，是不合法的，直接return结束方法
        if (left > right) {
            return;
        }
        // 获得基准数(默认选择最左边的数)与左右2个下标索引数
        int base = arr[left];
        int i = left;
        int j = right;

        // 当i和j不相遇的时候，才进行循环检索
        while (i != j) {
            // 从右边开始检索，如果找到了小于基准数的数，就停下
            // 如果检索到比基准数大的或者相等的，就继续检索
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 从左开始检索，如果找到了大于基准数的数，就停下
            // 如果检索到比基准数小的或者相等的，就继续检索
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 到这说明i和j都停下了，交换它们两的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 到这说明 i 和 j相遇了，就将相遇位置的值与基准数交换
        arr[left] = arr[i];
        arr[i] = base;

        // 然后将排序后左边的序列再次进行排序
        quickSort(arr, left , i -1);
        // 将右边的序列再次进行排序
        quickSort(arr, i + 1, right);
    }
}

折半查找(使用时有限制，只能是排序好了的数组)

// 非递归二分查找
    public static int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 递归二分查找
    public static int binarySearch2(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int index = binarySearch(arr, key, low, high);
        return index;
    }

    private static int binarySearch(int[] arr, int key, int low, int high) {
        if (low > high) {
            return -1;
        }
        // 计算中间索引
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (key < arr[mid]) {
            return binarySearch(arr, key, low, mid - 1);
        } else {
            return binarySearch(arr, key, mid + 1, high);
        }
    }

补充一下递归的优点与缺点

• 优点：编码简单，适合处理相同业务逻辑的问题
• 缺点：占用内存空间多，每递归一次都会在栈空间中开辟新空间执行方法