">
1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.归并排序
6.快速排序
- 基准元素选择
- 元素的交换
  - 双边循环法
  - 单边循环法
7.堆排序
8.计数排序
- 优化
9.桶排序
10.基数排序

1.冒泡排序

public static void bubbleSort(int array[]) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            int temp = 0;
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

优化 1

如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作。

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        // 有序标记，每一轮初始值都是 True
        boolean isSorted = true;
        for (int j = 0; j < array.length - i - 1; j++) {
            int temp = 0;
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                // 有元素交换，所以不是有序的
                isSorted = false;
            }
        }
        if (isSorted) break;
    }
}

优化 2

按照现有的逻辑，有序区的长度和排序的轮数是相等的。例如第 1 轮排序过后的有序区长度是 1，第 2 轮排序过后的有序区长度是 2……
实际上，数列真正的有序区可能会大于这个长度。因此后面的多次元素比较是没有意义的。那么，该如何避免这种情况呢？我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。

public static void bubbleSort(int[] array) {
    // 记录最后一次交换位置
    int lastExchangeIndex = 0;
    // 无序数列的边界，每次只比较到这里为止
    int sortBorder = array.length - 1;
    for (int i = 0; i < array.length - 1; i++) {
        // 有序标记，每一轮初始值都是 True
        boolean isSorted = true;
        for (int j = 0; j < sortBorder; j++) {
            int temp = 0;
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                // 有元素交换，所以不是有序的
                isSorted = false;
                // 更新为最后一次交换元素的位置
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (isSorted) break;
    }
}

优化 3：鸡尾酒排序

鸡尾酒排序的思路。排序过程就像钟摆一样，第 1 轮从左到右，第 2 轮从右到左，第 3 轮再从左到右……
对于数组 [2, 3, 4, 5, 6, 7, 8, 1]，
第一轮排序：[2, 3, 4, 5, 6, 7, 1, 8]
第二轮排序：[1, 2, 3, 4, 5, 6, 7, 8]
此时经过两轮排序，数组已经有序，但常规的冒泡排序还会继续比较，鸡尾酒排序则解决了这个问题。

public static void cocktailSort(int[] array) {
    int temp = 0;
    for (int i = 0; i < array.length / 2; i++) {
        // 有序标记，每一轮初始值都是 True
        boolean isSorted = true;
        // 奇数轮，从左向右比较和交换
        for (int j = i; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                // 有元素交换，所以不是有序的
                isSorted = false;
            }
        }
        if (isSorted) break;
        // 在偶数轮之前，将 isSorted 重新标记为 True
        isSorted = true;
        // 偶数轮，从右向左比较和交换
        for (int j = array.length - i - 1; j > i; j--) {
            if (array[j] < array[j - 1]) {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                // 有元素交换，所以不是有序的
                isSorted = false;
            }
        }
        if (isSorted) break;
    }
}

代码外层的大循环控制着所有排序回合，大循环内包含 2 个小循环，第 1 个小循环从左向右比较并交换元素，第 2 个小循环从右向左比较并交换元素。
鸡尾酒排序的优点是能够在特定条件下，减少排序的回合数；而缺点也很明显，就是代码量几乎增加了 1 倍。

2.选择排序

3.插入排序

4.希尔排序

5.归并排序

6.快速排序

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
这种思路就叫作分治法。

基准元素选择

基准元素，英文是 pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
通常我们会选择数组的第一个元素来作为基准元素，但这样会出现一个问题，就是当一个数组逆序的时候，我们选择第一个元素作为基准元素时，快速排序的时间复杂度就会从十大排序算法 - 图3 退化为十大排序算法 - 图4 。
为了避免这种情况发生，我们可以随机选择一个元素作为基准元素，并让基准元素和数列首元素交换位置。

元素的交换

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。
具体如何实现呢？有两种方法。

双边循环法。
单边循环法。
双边循环法
首先，选定基准元素**pivot**，并且设置两个指针**left**和**right**，指向数列的最左和最右两个元素。

接下来进行第1次循环，从 right 指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于 pivot，则指针向左移动；如果小于 pivot，则 right 指针停止移动，切换到 left 指针。
在当前数列中，1＜4，所以 right 直接停止移动，换到 left 指针，进行下一步行动。
轮到 left 指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于pivot，则指针向右移动；如果大于 pivot，则 left 指针停止移动。
由于 left 开始指向的是基准元素，判断肯定相等，所以 left 右移1位。

由于 7 ＞ 4，left 指针在元素 7 的位置停下。这时，让 left 和 right 指针所指向的元素进行交换。

接下来，进入第 2 次循环，重新切换到 right 指针，向左移动。right 指针先移动到 8，8＞4，继续左移。由于 2＜4，停止在 2 的位置。
按照这个思路，后续步骤如图所示。
```
private static int partition(int[] arr, int startIndex, int endIndex) {
 // 取第一个位置元素作为基准元素
 int pivot = arr[startIndex];
 int left = startIndex;
 int right = endIndex;
 while (left != right) {
     // 控制 right 指针比较并左移
     while (left < right && arr[right] > pivot) {
         right--;
     }
     // 控制 left 指针比较并右移
     while (left < right && arr[left] <= pivot) {
         left++;
     }
     // 交换 left 和 right 指针所指向的元素
     if (left < right) {
         int p = arr[left];
         arr[left] = arr[right];
         arr[right] = p;
     }
 }
 // pivot 和指针重合点交换
 arr[startIndex] = arr[left];
 arr[left] = pivot;
 return left;
}
```
单边循环法
开始和双边循环法相似，首先选定基准元素 pivot。同时，设置一个**mark**指针指向数列起始位置，这个 mark 指针代表小于基准元素的区域边界。

接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素大于基准元素，就继续往后遍历。
如果遍历到的元素小于基准元素，则需要做两件事：第一，把 mark 指针右移 1 位，因为小于 pivot 的区域边界增大了 1；第二，让最新遍历到的元素和 mark 指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot 的区域。首先遍历到元素 7，7＞4，所以继续遍历。

接下来遍历到的元素是 3，3＜4，所以 mark 指针右移1位。

随后，让元素 3 和 mark 指针所在位置的元素交换，因为元素 3 归属于小于 pivot 的区域。

按照这个思路，继续遍历，后续步骤如图所示。
```java private static int partition(int[] arr, int startIndex, int endIndex) { // 取第一个位置的元素作为基准元素 int pivot = arr[startIndex]; int mark = startIndex; for (int i = startIndex + 1; i <= endIndex; i++) {
```
 if (arr[i] < pivot) {
     mark++;
     int p = arr[mark];
     arr[mark] = arr[i];
     arr[i] = p;
 }
```
} arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark; }

public static void quickSort(int[] arr, int startIndex, int endIndex) { // 递归结束条件：startIndex >= endIndex if (startIndex >= endIndex) { return; } // 得到基准元素位置 int pivotIndex = partition(arr, startIndex, endIndex); // 根据基准元素，分成两部分进行递归 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); }

<a name="IMf9B"></a>
## 代码实现
```java
public static void quickSort(int[] arr, int startIndex, int endIndex) {
    // 递归结束条件：startIndex >= endIndex
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素位置
    int pivotIndex = partition(arr, startIndex, endIndex);
    // 根据基准元素，分成两部分进行递归
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

public static void quickSort2(int[] arr, int startIndex, int endIndex) {
    // 用一个集合栈代替递归的函数栈
    Stack<Map<String, Integer>> quickSortStack = new Stack<>();
    // 整个数列的起止下标，以哈希的形式入栈
    Map<String, Integer> rootParam = new HashMap<>();
    rootParam.put("startIndex", startIndex);
    rootParam.put("endIndex", endIndex);
    quickSortStack.push(rootParam);
    // 循环结束条件，栈为空时
    while (!quickSortStack.isEmpty()) {
        // 栈顶元素出栈，得到起止下标
        Map<String, Integer> param = quickSortStack.pop();
        // 得到基准元素位置
        int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
        // 根据基准元素分成两部分，把每一部分的起止下标入栈
        if (param.get("startIndex") < pivotIndex - 1) {
            HashMap<String, Integer> leftParam = new HashMap<>();
            leftParam.put("startIndex", param.get("startIndex"));
            leftParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(leftParam);
        }
        if (pivotIndex + 1 < param.get("endIndex")) {
            HashMap<String, Integer> rightParam = new HashMap<>();
            rightParam.put("startIndex", pivotIndex + 1);
            rightParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(rightParam);
        }
    }
}

7.堆排序

堆排序算法的步骤。

把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
```
public static void downAdjust(int[] array, int parentIndex, int length) {
 // temp 保存父节点值，用于最后的赋值
 int temp = array[parentIndex];
 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 * childIndex + 1;
 }
 array[parentIndex] = temp;
}
```
```
public static void heapSort(int[] array) {
 // 把无序数组构建为最大堆
 for (int i = (array.length - 1) / 2; i >= 0; i--) {
     downAdjust(array, i, array.length);
 }
 System.out.println(Arrays.toString(array));
 // 循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
 for (int i = array.length - 1; i > 0; i--) {
     // 最后一个元素和第一个元素进行交换
     int temp = array[i];
     array[i] = array[0];
     array[0] = temp;
     // 下沉调整最大堆
     downAdjust(array, 0, i);
 }
}
```
8.计数排序
假设数组中有20个随机整数，取值范围为 0～10，要求用最快的速度把这 20 个整数从小到大进行排序。
如何给这些无序的随机整数进行排序呢？
考虑到这些整数只能够在 0、1、2、3、4、5、6、7、8、9、10 这 11 个数中取值，取值范围有限。所以，可以根据这有限的范围，建立一个长度为 11 的数组。数组下标从 0 到 10，元素初始值全为 0。

假设 20 个随机整数的值如下所示。
9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9
下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加 1 操作。
例如第 1 个整数是 9，那么数组下标为 9 的元素加 1。

第 2 个整数是 3，那么数组下标为 3 的元素加 1。

继续遍历数列并修改数组……
最终，当数列遍历完毕时，数组的状态如下。

该数组中每一个下标位置的值代表数列中对应整数出现的次数。
有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
显然，现在输出的数列已经是有序的了。这就是计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是很大的情况下，它的性能甚至快过那些时间复杂度为的排序。
```
public static int[] countSort(int[] array) {
 // 得到数列的最大值
 int max = array[0];
 for (int i = 1; i < array.length; i++) {
     if (array[i] > max) {
         max = array[i];
     }
 }
 // 根据数列最大值确定统计数组的长度
 int[] countArray = new int[max + 1];
 // 遍历数组，填充统计数组
 for (int i = 0; i < array.length; i++) {
     countArray[array[i]]++;
 }
 // 遍历统计数组，输出结果
 int index = 0;
 int[] sortedArray = new int[array.length];
 for (int i = 0; i < countArray.length; i++) {
     for (int j = 0; j < countArray[i]; j++) {
         sortedArray[index++] = i;
     }
 }
 return sortedArray;
}
```
优化
假设有成绩表 {小灰: 90，大黄: 99，小红: 95，小白: 94，小绿: 95}
要求按成绩从低到高进行排序，如果成绩相同，则遵循原表固有顺序。
那么，当我们填充统计数组以后，只知道有两个成绩并列为 95 分的同学，却不知道哪一个是小红，哪一个是小绿。
在这种情况下，需要稍微改变之前的逻辑，在填充完统计数组以后，对统计数组做一下变形。
仍然以刚才的学生成绩表为例，将之前的统计数组变形成下面的样子。

这是如何变形的呢？其实就是从统计数组的第2个元素开始，每一个元素都加上前面所有元素之和。
为什么要相加呢？初次接触的读者可能会觉得莫名其妙。
这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置的序号。例如下标是9的元素值为5，代表原始数列的整数9，最终的排序在第5位。
接下来，创建输出数组 sortedArray，长度和输入数列一致。然后从后向前遍历输入数列。
第 1 步，遍历成绩表最后一行的小绿同学的成绩。小绿的成绩是 95 分，找到 countArray 下标是 5 的元素，值是 4，代表小绿的成绩排名位置在第 4 位。
同时，给 countArray 下标是 5 的元素值减 1，从 4 变成 3，代表下次再遇到 95 分的成绩时，最终排名是第 3。

第 2 步，遍历成绩表倒数第 2 行的小白同学的成绩。
小白的成绩是 94 分，找到 countArray 下标是 4 的元素，值是 2，代表小白的成绩排名位置在第 2 位。同时，给 countArray 下标是 4 的元素值减 1，从 2 变成 1，代表下次再遇到 94 分的成绩时（实际上已经遇不到了），最终排名是第 1。

……
这样一来，同样是 95 分的小红和小绿就能够清楚地排出顺序了，也正因为此，优化版本的计数排序属于稳定排序。
```
public static int[] countSort(int[] array) {
 // 得到数列的最大值和最小值，并算出差值
 int max = array[0];
 int min = array[0];
 for (int i = 1; i < array.length; i++) {
     if (array[i] > max) max = array[i];
     if (array[i] < min) min = array[i];
 }
 int d = max - min;
 // 创建统计数组并统计对应元素个数
 int[] countArray = new int[d + 1];
 for (int i = 0; i < array.length; i++) {
     countArray[array[i] - min]++;
 }
 // 统计数组做变形，后面的元素等于前面的元素之和
 for (int i = 1; i < countArray.length; i++) {
     countArray[i] += countArray[i - 1];
 }
 // 倒序遍历原始数组，从统计数组中找到正确位置
 int[] sortedArray = new int[array.length];
 for (int i = array.length - 1; i >= 0; i--) {
     sortedArray[countArray[array[i] - min] - 1] = array[i];
     countArray[array[i] - min]--;
 }
 return sortedArray;
}
```
9.桶排序
桶排序同样是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。
那么，桶排序中所谓的“桶”，又是什么呢？
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。
假设有一个非整数数列如下：
4.5, 0.84, 3.25, 2.18, 0.5
让我们来看看桶排序的工作原理。
桶排序的第 1 步，就是创建这些桶，并确定每一个桶的区间范围。

具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。

第 2 步，遍历原始数列，把元素对号入座放入各个桶中。

第 3 步，对每个桶内部的元素分别进行排序（显然，只有第1个桶需要排序）。

第 4 步，遍历所有的桶，输出所有元素。
0.5, 0.84, 2.18, 3.25, 4.5
到此为止，排序结束。
```
public static double[] bucketSort(double[] array) {
 // 得到数列的最大值和最小值，并算出差值
 double max = array[0];
 double min = array[0];
 for (int i = 1; i < array.length; i++) {
     if (array[i] > max) max = array[i];
     if (array[i] < min) min = array[i];
 }
 double d = max - min;
 // 初始化桶
 int bucketNum = array.length;
 ArrayList<LinkedList<Double>> bucketList = new ArrayList<>();
 for (int i = 0; i < bucketNum; i++) {
     bucketList.add(new LinkedList<Double>());
 }
 // 遍历原始数组，将每个元素放入桶中
 for (int i = 0; i < array.length; i++) {
     int num = (int) ((array[i] - min) * (bucketNum - 1) / d);
     bucketList.get(num).add(array[i]);
 }
 // 对每个桶内部进行排序
 for (int i = 0; i < bucketList.size(); i++) {
     Collections.sort(bucketList.get(i));
 }
 // 输出全部元素
 double[] sortedArray = new double[array.length];
 int index = 0;
 for (LinkedList<Double> list : bucketList) {
     for (double element : list) {
         sortedArray[index] = element;
         index++;
     }
 }
 return sortedArray;
}
```
10.基数排序

十大排序算法