------------------------------------------排序算法-------------------------------------------

源码地址：Sort

根据时间复杂度的不同，主流的排序算法可以分为 3 大类。

1. 时间复杂度为 O(n ²)的排序算法
2. 时间复杂度为 O(n㏒n)的排序算法
3. 时间复杂度为线性的排序算法

1. 冒泡排序

冒泡排序的**升序排列是将相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置。**冒泡排序的时间复杂度为 O(n ²)。

一般的冒泡排序

    /**
     * 简单的冒泡排序（升序）
     *
     * @param originalArray 原始数组
     */
    public static void simpleBubbleSort(int[] originalArray) {
        int[] array;
        array = Arrays.copyOf(originalArray, originalArray.length);
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

优化后的冒泡排序

    /**
     * 优化后的冒泡排序（升序）
     *
     * @param originalArray 原始数组
     */
    public static void optBubbleSort(int[] originalArray) {
        int[] array;
        array = Arrays.copyOf(originalArray, originalArray.length);

        // 最后一次交换的位置
        int lastExchangeIndex = 0;
        // 数组中的无序数列的边界
        int sortBorder = array.length - 1;
        for (int i = 0; i < array.length - 1; i++) {
            // 默认每一次循环需要排序的序列是有序的
            boolean isSorted = true;
            for (int j = 0; j < sortBorder; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;

                    // 发生了交换，说明不是有序序列
                    isSorted = false;
                    // 记录最后一次交换元素的下标
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }

优化后的冒泡排序对原数组中已经包含多数有序序列的数组排序效率更高，否则由于每一次循环中需要做额外的赋值操作，反而较简单的冒泡排序效率更低下。

2. 鸡尾酒排序

鸡尾酒排序的排序规则是**轮流从左至右和从右至左进行相邻元素两两比较进行排序。**鸡尾酒排序的时间复杂度为 O(n ²)。
一般的鸡尾酒排序

/**
 * 鸡尾酒排序
 */
public class CocktailSort {

    /**
     * 普通的鸡尾酒排序（升序）
     *
     * @param originalArray 序排序的原始数组
     */
    public static void simpleSort(int[] originalArray) {
        for (int i = 0; i < originalArray.length / 2; i++) {
            // 默认每一轮开始比较之前数组都是有序的
            boolean isSorted = true;
            for (int j = 0; j < originalArray.length - i - 1; j++) {
                if (originalArray[j] > originalArray[j + 1]) {
                    int temp = originalArray[j];
                    originalArray[j] = originalArray[j + 1];
                    originalArray[j + 1] = temp;

                    // 有发生元素位置交换，所以原数组不为有序数组
                    isSorted = false;
                }
            }
            if (isSorted) {
                // 数组已为有序数组，无需做后续比较
                break;
            }

            // 进行这一轮排序之前，默认认为数组有序
            isSorted = true;
            for (int j = originalArray.length - i - 1; j > i; j--) {
                if (originalArray[j] < originalArray[j - 1]) {
                    int temp = originalArray[j];
                    originalArray[j] = originalArray[j - 1];
                    originalArray[j - 1] = temp;

                    // 发生了位置交换，说明数组不为有序数组
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

优化后的鸡尾酒排序

   /**
    * 优化后的鸡尾酒排序
    *
    * @param originalArray 需排序的数组
    */
   public static void optSort(int[] originalArray) {
       // 数组无序右边界
       int rightBorder = originalArray.length - 1;
       // 数组无序左边界
       int leftBorder = 0;
       // 从左至右最后一次交换的位置
       int lastRightIndex = 0;
       // 从右至左最后一次交换的位置
       int lastLeftIndex = 0;
       for (int i = 0; i < originalArray.length / 2; i++) {
           // 默认每一轮开始比较之前数组都是有序的
           boolean isSorted = true;
           for (int j = leftBorder; j < rightBorder; j++) {
               if (originalArray[j] > originalArray[j + 1]) {
                   int temp = originalArray[j];
                   originalArray[j] = originalArray[j + 1];
                   originalArray[j + 1] = temp;

                   // 记录最后一次发生交换的右边界位置
                   lastRightIndex = j;
                   // 有发生元素位置交换，所以原数组不为有序数组
                   isSorted = false;
               }
           }
           rightBorder = lastRightIndex;
           if (isSorted) {
               // 数组已为有序数组，无需做后续比较
               break;
           }

           // 进行这一轮排序之前，默认认为数组有序
           isSorted = true;
           for (int j = rightBorder; j > leftBorder; j--) {
               if (originalArray[j] < originalArray[j - 1]) {
                   int temp = originalArray[j];
                   originalArray[j] = originalArray[j - 1];
                   originalArray[j - 1] = temp;

                   // 记录最后一次发生交换的左边界位置
                   lastLeftIndex = j;
                   // 发生了位置交换，说明数组不为有序数组
                   isSorted = false;
               }
           }
           leftBorder = lastLeftIndex;
           if (isSorted) {
               break;
           }
       }
   }

鸡尾酒排序适用于大部分元素已有序的情况。

3. 快速排序

快速排序是在每一轮挑选一个基准元素，并让其他比他大的元素移动到数列一边，比它小的元素移动到另一边，从而把数列拆解成两个部分。这种思路就叫作分治法。快速排序的时间复杂度为 O(n㏒n)。

快速排序中要实现分治，有两种方法：

• 双边循环法
• 单边循环法

代码如下：

    /**
     * 双边循环
     * 1. 首先选定基准元素pivot，并且设置两个指针left和right，
     *    指向数列的最左和最右两个元素。
     * 2. 从right指针开始，让right指针所指向的元素和pivot相比较，
     *    如果大于pivot，则right指针向左移一位，否则停止移动。
     * 3. 切换至left指针，让left指针所指向的元素和pivot相比较，
     *    如果小于或等于pivot，则left指针右移一位，否则停止移动。
     * 4. 此时将left指针的元素和right指针的元素互换位置。
     * 5. 如此循环执行 2 --> 3 --> 4 这三步操作，
     *    直至left指针与right指针重合，
     *    将指针位置的元素与pivot元素互换位置，
     *    此时pivot元素左侧均为小于或等于pivot的元素，
     *    右侧均为大于pivot的元素，达到分治要求
     *
     * @param array      需排序的数组
     * @param startIndex 数组片段的起始位置
     * @param endIndex   数组片段的结束位置
     * @return 分治数组后，基准元素pivot的下标
     */
    public static int duplexPartition(int[] array, int startIndex, int endIndex) {
        // 默认取第一个元素作为基准元素
        int pivot = array[startIndex];
        // 基准元素左指针指向的元素下标位置
        int left = startIndex;
        // 基准元素右指针指向的元素下标位置
        int right = endIndex;

        while (left < right) {
            while (array[right] > pivot) {
                // 依次从右至左与基准元素进行比较，直至元素的值小于或等于基准元素的值
                right--;
            }
            while (left < right && array[left] <= pivot) {
                // 依次从左至右与基准元素进行比较，直至元素的值大于基准元素的值
                left++;
            }

            if (left < right) {
                // 将基准元素的左指针停止的位置元素与右指针停止的元素位置进行交换
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }

        // 将基准元素与两指针重合位置的元素交换
        array[startIndex] = array[left];
        array[left] = pivot;
        return left;
    }

    /**
     * 单边循环
     * 1. 首先选定基准元素pivot，并制定标记位置mark，
     *    设置mark初始值为数组起始位置。
     * 2. 将数组中的元素从左至右依次与pivot进行比较，
     *    如果元素的值比pivot大，则继续进行比较，
     *    如果元素的值小于或等于pivot，则
     *    先将mark后移一位，
     *    然后再将该元素和mark位置所在的元素位置进行互换。
     * 3. 待将整个数组的元素与pivot比较完毕后，
     *    将mark位置所在的元素与pivot互换位置。
     *
     * @param array      需排序的数组
     * @param startIndex 数组片段的起始位置
     * @param endIndex   数组片段的结束位置
     * @return 基准元素pivot的下标
     */
    public static int simplexPartition(int[] array, int startIndex, int endIndex) {
        int pivot = array[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (pivot >= array[i]) {
                // 从左至右与基准元素进行比较，小于pivot则将标记后移一位，并将mark位置的元素和当前元素进行交换
                mark++;
                int temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }

        // 此时数组中mark位置（包括mark）之前的元素均小于pivot，将mark位置的元素与pivot进行交换
        array[startIndex] = array[mark];
        array[mark] = pivot;
        return mark;
    }

快速排序代码如下：

    /**
     * 快速排序（升序）
     * 1. 首先使用单边循环或者双边循环将数组分成两部分
     * 2. 基准元素左边均是小于或等于pivot的元素，
     *    基准元素右边均是大于pivot的元素。
     * 3. 分别递归左边和右边的数组，循环执行 1 --> 2 
     * @param array      需排序的数组
     * @param startIndex 数组片段的起始位置
     * @param endIndex   数组片段的结束位置
     */
    public static void sort(int[] array, int startIndex, int endIndex) {
        // 当startIndex 和 endIndex 在一个位置时跳出递归循环
        if (startIndex >= endIndex) {
            return;
        }
        // 获取基准元素pivot的下标
        // 使用单边循环
        int pivotIndex = simplexPartition(array, startIndex, endIndex);
        // 使用双边循环
//        int pivotIndex = duplexPartition(array, startIndex, endIndex);
        // 根据基准元素，分成两部分进行递归排序
        // 递归左边
        sort(array, startIndex, pivotIndex - 1);
        // 递归右边
        sort(array, pivotIndex + 1, endIndex); 
    }

4. 堆排序

使用二叉堆这种数据结构的特性可以完成对数组的排序。
升序排序可先将数组调整为最大二叉堆，然后循环删除堆顶元素，并移动至尾部。
降序排序可先将数组调整为最小二叉堆，然后循环删除堆顶元素，并移动至尾部。

    /**
     * 构建最小二叉堆
     *
     * @param array    待调整的堆
     * @param endIndex 待调整的堆中可供调整的最大边界位置
     */
    public static void buildMinHeap(int[] array, int endIndex) {
        // 从最后一位非叶子节点进行“下沉”调整
        for (int i = (endIndex - 1) / 2; i >= 0; i--) {
            downAdjust(array, i, endIndex + 1);
        }
    }

    /**
     * 二叉堆的“下沉”操作
     *
     * @param array       待调整的堆
     * @param parentIndex 父节点下标
     * @param length      堆的大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        // 左子节点的下标位置为 2 * parentIndex + 1
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 取左右子节点中的较大的节点
            if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            if (temp >= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 堆排序（升序）
     *
     * @param array 需排序的数组
     */
    public static void sort(int[] array) {
        int endIndex = array.length - 1;
        for (int i = 0; i < array.length - 1; i++) {
            // 每次取了堆顶元素后，都要对新堆做调整
            buildMinHeap(array, endIndex);
            // 将排序后的数组中的最后一个元素与堆顶元素互换位置
            int temp = array[endIndex];
            array[endIndex] = array[0];
            array[0] = temp;
            // 此时数组中最大的元素已排到队尾，此时将堆的调整最大边界前移一位，即最后一位不参与最大堆调整
            endIndex--;
        }
    }

5. 计数排序

计数排序只适用于都是整数的数组进行排序。
代码如下：

/**
 * 计数排序
 * ** 只适用于整数序列的排序
 * 1. 首先获取数组中元素的最大值max与最小值min。
 * 2. 创建一个长度为（max - min） + 1的数组array， 数组中各个元素的初始值均为0。
 * 3. 循环遍历目标数组，当目标数组中的元素（值 - min）与array下标的值相等时，
 *    array中该下标位置的值 + 1。
 * 4. 此时排序已完成，循环输出即可
 */
public class CountSort {

    public static class Extreme {
        int min;
        int max;
    }

    /**
     * 获取数组中的最小值 和 最大值
     *
     * @param array 数组
     * @return 极限值
     */
    public static Extreme getExtreme(int[] array) {
        Extreme extreme = new Extreme();
        for (int i = 0; i < array.length; i++) {
            if (array[i] < extreme.min) {
                extreme.min = array[i];
            }
            if (array[i] > extreme.max) {
                extreme.max = array[i];
            }
        }
        return extreme;
    }

    /**
     * 构建计数数组
     *
     * @param array 需排序的数组
     * @return 返回计数数组
     */
    public static int[] buildCountArray(int[] array) {
        Extreme extreme = getExtreme(array);
        int min = extreme.min;
        int max = extreme.max;

        // 构建计数数组
        int[] countArray = new int[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            countArray[array[i] - min]++;
        }

        return countArray;
    }

    /**
     * 一般的计数排序（升序）
     *
     * @param array 需排序的数组
     * @return 排序后的数组
     */
    public static int[] simpleSort(int[] array) {
        // 构建计数数组
        int[] countArray = buildCountArray(array);

        int index = 0;
        int min = getExtreme(array).min;
        int[] resultArray = new int[array.length];
        for (int i = 0; i < countArray.length; i++) {
            if (countArray[i] != 0) {
                // 当下标所在位置元素的值为0时，表示需排序数组中不含与该下标值相同的元素
                for (int j = 0; j < countArray[i]; j++) {
                    // 排序后的数组
                    resultArray[index++] = i + min;
                }
            }
        }
        return resultArray;
    }

    /**
     * 优化后的计数排序（升序）
     *
     * @param array 需排序的数组
     * @return 排序后的数组
     */
    public static int[] optSort(int[] array) {
        int[] countArray = buildCountArray(array);

        // 优化计数数组
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        int min = getExtreme(array).min;
        int[] resultArray = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            resultArray[countArray[array[i] - min] - 1] = array[i];
            countArray[array[i] - min]--;
        }
        return resultArray;
    }

    public static void main(String[] args) {
        int[] array = {4, 4, 6, 5, 3, 2, 8, 1};
        int[] sortArray = optSort(array);
        System.out.println(Arrays.toString(sortArray));
    }

}

6. 桶排序

桶排序类似于计数排序，只是将数组中的各个元素放入对应的桶中，然后循环遍历所有的桶，即得排序后的数组。
每个通都有一个区间跨度
区间跨度 = （最大值 - 最小值）/ （桶的数量 - 1）

/**
 * 桶排序
 * 1. 先设置桶的个数num，继而确认每个桶的取值区间。
 * 2. 遍历集合，放入对应的桶中。
 * 3. 对每个桶内部的元素进行排序
 * 4. 循环遍历所有的桶，即可得到排序后的集合
 */
public class BucketSort {

    /**
     * 极限值，包含最小值和最大值
     */
    public static class Extreme {
        int min;
        int max;
    }

    /**
     * 构建所有的桶
     *
     * @param source 需排序的集合
     * @return 所有的桶
     */
    public static ArrayList<LinkedList<Integer>> buildBuckets(List<Integer> source) {
        // 这里桶的个数设为排序序列长度的十分之一
        int bucketNums = source.size() / 10;
        while (bucketNums <= 1) {
            // 保证桶的个数最少为两个（最后一个始终只放一个最大值）
            bucketNums++;
        }
        ArrayList<LinkedList<Integer>> buckets = new ArrayList<>(bucketNums);
        for (int i = 0; i < bucketNums; i++) {
            buckets.add(new LinkedList<>());
        }
        return buckets;
    }

    /**
     * 获取序列中的极限值
     *
     * @param source 需排序的集合
     * @return 极限值
     */
    public static Extreme getExtreme(List<Integer> source) {
        Extreme extreme = new Extreme();
        extreme.min = Collections.min(source);
        extreme.max = Collections.max(source);
        return extreme;
    }

    /**
     * 桶排序（升序）
     *
     * @param source 需排序的集合
     * @return 排序后的集合
     */
    public static ArrayList<Integer> sort(List<Integer> source) {
        ArrayList<Integer> sortList = new ArrayList<>(source.size());
        Extreme extreme = getExtreme(source);
        int min = extreme.min;
        int max = extreme.max;
        ArrayList<LinkedList<Integer>> buckets = buildBuckets(source);
        // 遍历所有元素，将其放入对应的桶中
        for (int i = 0; i < source.size(); i++) {
            int element = source.get(i);
            // 桶的下标
            int bucketIndex = (element - min) * (buckets.size() - 1) / (max - min);
            // 将元素存入桶中
            buckets.get(bucketIndex).add(element);
        }
        // 对每个桶中的元素进行排序
        buckets.forEach(Collections::sort);

        // 循环遍历所有的桶添加至排序集合中
        buckets.forEach(sortList::addAll);

        return sortList;
    }
}

• 备注： 源码地址：Sort