java：常见算法-排序算法

1. 冒泡排序

相邻的两两比较，小左大右

每一轮决定该轮最大值（第一轮决定最大值，第二轮决定次大值……

共n-1轮

    public static void bubble(int[] arr) {
        for (int k = 0; k < arr.length - 1; k++) {
            for (int i = 0; i < arr.length - 1 - k; i++) {
                if (arr[i] > arr[i + 1]) {
                    int tmp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = tmp;
                }
            }
        }
    }

2.选择排序

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

    public static void select(int[] arr) {
        for (int k = 0; k < arr.length - 1; k++) {
            for (int i = k + 1; i < arr.length; i++) {
                if (arr[k] > arr[i]) {
                    int tmp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = tmp;
                }
            }
        }
    }

3. 插入排序

将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。

遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

N的范围：0~最大索引

    public static void insert(int[] arr) {
        // 找到无序的数组
        int startIndex = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                startIndex = i + 1;
                break;
            }
        }
        for (int k = startIndex; k < arr.length; k++) {
            int i = k;
            while (i > 0 && arr[i] < arr[i - 1]) {
                int tmp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = tmp;
                i--;
            }
        }

    }

4. 快速排序

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

    public static void quick(int[] arr, int startIndex, int endIndex) {
        int min = startIndex;
        int max = endIndex;
        if (startIndex > endIndex)
            return;
        int baseNumber = arr[startIndex];
        while (min != max) {
            while (true) {
                if (min >= max || arr[max] < baseNumber) {
                    break;
                }
                max--;
            }
            while (true) {
                if (min >= max || arr[min] > baseNumber) {
                    break;
                }
                min++;
            }
            int tmp = arr[min];
            arr[min] = arr[max];
            arr[max] = tmp;
        }
        int temp = arr[startIndex];
        arr[startIndex] = arr[min];
        arr[min] = temp;
        // arr[startIndex] = arr[min];
        // arr[min] = baseNumber;
        quick(arr, startIndex, min - 1);
        q

这里需要注意：如果是从小到大排序，那么与基准值对调的数字需要小于基准值，也就是先找max索引再找min索引，因为如果两者相等时先找max索引会使max=min且指向的数字小于基准值