「数据结构与算法」根底排序

替换排序：

• 疾速排序
• 冒泡排序

替换排序

疾速排序

思路：

在数组中找一个元素(节点)，比它小的放在节点的右边，比它大的放在节点左边。一趟下来，比节点小的在右边，比节点大的在左边。
一直执行这个操作…

实现：

    public static void quickSort(int[] array, int l, int r) {
        int leftPos = l;
        int rightPos = r;

        // 支点
        // 该值能够选任意值
        int pivot = array[(l + r) / 2];

        // 支点右边的值全副小于支点
        // 支点左边的值全副大于支点
        while (leftPos <= rightPos) {
            // 从左开始，寻找比支点大的地位
            while (array[leftPos] < pivot) {
                leftPos++;
            }

            // 从右开始，寻找比支点小的地位
            while (array[rightPos] > pivot) {
                rightPos--;
            }

            if (leftPos <= rightPos) {
                // 替换左右数值
                int temp = array[leftPos];
                array[leftPos] = array[rightPos];
                array[rightPos] = temp;
                leftPos++;
                rightPos--;
            }
        }

        if (rightPos > l) {
            quickSort(array, l, rightPos);
        }

        if (leftPos < r) {
            quickSort(array, leftPos, r);
        }
    }

冒泡排序

思路：

俩俩替换，大的放在前面，第一次排序后最大值已在数组开端
因为俩俩替换，须要 n-1 趟排序，比方10个数，须要9趟排序

实现：

    public static void popupSort(int[] array) {
        // 每一轮把最大的值像冒泡泡一样冒到最初一位
        for (int i = 0; i < array.length - 1; i++) {
            // 判断是否批改
            boolean isChange = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    isChange = true;
                }
            }

            // 若无批改代表数组曾经有序
            if (isChange == false) {
                break;
            }
        }
    }