十大经典排序算法(以升序为目的)

• 内部排序：数据记录在内存中进行排序。
• 外部排序：因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

        

• n：数据规模
• k：“桶” 的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存，比如需要开辟一个新数组

• 稳定：相等的数据排序后相对顺序保持不变，如果 A 原本在 B 前面，而且 A=B，排序之后 A 仍然在 B 的前面。
• 不稳定：相等的数据排序后相对顺序可能改变，如果 A 原本在 B 的前面，而且 A=B，排序之后 A 可能会出现在 B 的后面。
  不稳定的有：选择、希尔、快速、堆排序。(投机取巧地记一下：选择希尔快速怼)
• 内排序：所有排序操作都在内存中完成。
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
• 最好：原序列有序。
• 最差：原序列逆序。

2.冒泡排序(Bubble Sort)

（1）算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤 1~3，直到排序完成。

• 未优化写法：
  
• 优化：可以在每次循环中加一个标志位判断，如果原序列有序，就不用比较了，可以将O(n²)降为O(n)。
  
  

• 稳定性：稳定
• 时间复杂度 ：最佳：O(n) ，最差：O(n2)， 平均：O(n2)
• 空间复杂度 ：O(1)
• 排序方式 ：In-place

• 每次都从未排序序列中寻找最小（大）元素，然后放到已排序序列的末尾，直到所有元素均排序完毕。
  相当于每次从未排序序列中选择最小的元素，放到排序序列的最后，所以叫选择排序。

• 稳定性：不稳定，比如[3，3，1]，选择排序后变成了[1，3，3]，两个"3"的相对顺序改变了。
• 时间复杂度 ：最佳：O(n2) ，最差：O(n2)， 平均：O(n2)
• 空间复杂度 ：O(1)
• 排序方式 ：In-place

4.插入排序 (Insertion Sort)

• 从第一个元素开始，该元素可以认为已经有序（手里的第一张牌本身就有序了）；
• 取出下一个元素（摸牌），从后向前扫描有序序列；
• 如果该元素（已排序）大于新元素，将该元素后移；
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤 2~5。

        

• 稳定性：稳定
• 时间复杂度 ：最佳：O(n) ，最差：O(n2)， 平均：O(n2)
• 空间复杂度 ：O(1)
• 排序方式 ：In-place

5.希尔排序 (Shell Sort)

• 稳定性：不稳定
• 时间复杂度 ：最佳：O(nlogn)， 最差：O(n2) ，平均：O(nlogn)
• 空间复杂度 ：O(1)

6.★归并排序 (Merge Sort) 

• 如果输入内只有一个元素，则直接返回，否则将长度为n的输入序列分成两个长度为n/2的子序列；
• 分别对这两个子序列进行归并排序，使子序列变为有序状态；
• 设定两个指针，分别指向两个已经排序子序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
• 重复步骤 3 ~4 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

（2）2路-归并排序代码实现

• 稳定性：稳定
• 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
• 空间复杂度 ：O(n)，额外创建了一个辅助数组sortedArr。

7.快速排序 (Quick Sort)

• 首先设定一个分界点(pivot)，通过分界点将数组分成左右两部分；
• 将小于分界点的数据都放在到数组左边，将大于分界点的数据都放在数组的右边，与分界点相同的数据放哪边都可以；
• 然后，分界点左边的子数组和右边的子数组分别重复1~2步(递归)；
• 当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

• 稳定性 ：不稳定
• 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)，平均：O(nlogn)
  最好：最好的情况就是分割点始终是中间元素。
  最差：当分界点是最大或最小的元素时最差，这种情况导致中心元素位于已排序数组的最末端，一个子数组始终为空，而另一个子数组包含元素。
  
• 空间复杂度 ：尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归，因此是O(logn)。

8.堆排序 (Heap Sort)

• 下标为 i 的节点的父节点的下标：(i - 1) / 2；
• 下标为 i 的节点的左孩子的下标：i * 2 + 1；
• 下标为 i 的节点的右孩子的下标：i * 2 + 2。

• 将原序列转换成大顶堆(建堆)；
• 进行堆排序，每次将堆顶元素与最后一个元素交换，然后断开最后一个元素(因为已排好序)，再对剩下的元素维护大顶堆；
• 重复上一步。

• 稳定性 ：不稳定
• 时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
• 空间复杂度 ：O(1)

9.计数排序 (Counting Sort)

• 找出数组中的最大值max、最小值min；
• 创建一个新数组C，其长度是max-min+1，其元素默认值都为 0；
• 遍历原数组A中的元素A[i]，以A[i]-min作为C数组的索引，以A[i]的值在A中元素出现次数作为C[A[i]-min]的值；
• 对C数组变形，新元素的值是该元素与前一个元素值的和，即当i>1时C[i] = C[i] + C[i-1]；
• 创建结果数组R，长度和原始数组一样。
• 从后向前遍历原始数组A中的元素A[i]，使用A[i]减去最小值min作为索引，在计数数组C中找到对应的值C[A[i]-min]，C[A[i]-min]-1就是A[i]在结果数组R中的位置，做完上述这些操作，将count[A[i]-min]减小 1。

        

（2）代码实现

//获取最大值和最小值
private static int[] getMinAndMax(int[] arr) {
    int maxValue = arr[0];
    int minValue = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
        } else if (arr[i] < minValue) {
            minValue = arr[i];
        }
    }
    return new int[] { minValue, maxValue };
}
//排序
public static int[] countingSort(int[] arr) {
    if (arr.length < 2) {
        return arr;
    }
    int[] extremum = getMinAndMax(arr);
    int minValue = extremum[0];
    int maxValue = extremum[1];
    int[] countArr = new int[maxValue - minValue + 1];
    int[] result = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - minValue] += 1;
    }
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = countArr[arr[i] - minValue] - 1;
        result[idx] = arr[i];
        countArr[arr[i] - minValue] -= 1;
    }
    return result;
}

（3）算法分析