来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
一、题目
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
- 1 <= nums.length <= 5 * 104
- -5 * 104 <= nums[i] <= 5 * 104
二、题解
解题源码: 链接
排序算法是《数据结构与算法》中最基本的算法之一。
| \ | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | In-place | 不稳定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | In-place | 稳定 |
| 希尔排序 | O(n log n) | O(n log² n) | O(n log² n) | O(1) | In-place | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | In-place | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | Out-place | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | Out-place | 稳定 |
| 基数排序 | O(n x k) | O(n x k) | O(n x k) | O(n x k) | Out-place | 稳定 |
关于时间复杂度：
- 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
- 线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
- O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
- 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于排序方式：
- 内部排序：数据记录在内存中进行排序。
- 外部排序：因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
关于稳定性：
- 稳定的排序：排序前后两个相等的数相对位置不变，则算法稳定。
- 不稳定的排序：排序前后两个相等的数相对位置不变，则算法稳定。
以上是个人学习记录，如有不正确请多多包涵，也欢迎评论告诉我，谢谢~
评论区