常见排序算法可以分为两大类：
- 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。如：快速排序、归并排序、堆排序、冒泡排序等。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
- 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。如：计数排序、基数排序、桶排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
常见算法的复杂度分析
参考这里：所谓稳定性是指待排序的序列中有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2.（相同的记录在排序前后相对次序不发生改变，那么就是稳定的排序）
对于不稳定的 排序算法 ，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是， 排序算法是否为稳定的是由具体算法决定的 ，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a[j]>=a[j+1]，则两个相等的记录就会交换位置。
稳定性的意义：
1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）
3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。
- 稳定排序算法：冒泡排序、插入排序、归并排序、（计数排序、桶排序与基数排序）
- 不稳定排序算法：希尔排序、选择排序、堆排序与快速排序
复杂度分析：
- 数据结构和算法本身解决的是“快”和“省”的问题，衡量算法执行效率的指标就包括复杂度
- 复杂度分析包括时间复杂度和空间复杂度分析，时间复杂度是指算法执行的时间与数据规模的关系，空间复杂度是指算法占用的空间与数据规模的关系
为什么进行复杂度分析？如何分析？
- 为什么分析复杂度：通过测试、统计、监控，可以的得到算法执行的时间和占用的内存大小，但是测试结果非常依赖测试环境，测试结果受数据规模的影响很大；我们需要一个不依赖测试环境和数据规模就可以粗略估算算法执行效率的方法
大O时间复杂度表示法：表示代码执行时间随数据规模增长的变化趋势，又称渐进时间复杂度。
大O空间复杂度表示法：表示代码执行所占的内存空间随数据规模增长的变化趋势，又称渐进空间复杂度 ps：给出随着增长规模的下界，具体流程：
- 大O复杂度表示法
算法的执行效率，粗略地讲就是算法的执行时间。下面的代码是求1，2，3...n累加的和。
cal(int n) { int sum = 0; int i = 1; for (; i <= n; ++i) { sum += i; // 两步操作 } return sum; }
从CPU的角度，这段代码的操作是，读数据 -> 运算 -> 写数据，如果每一个操作都是unit_time，第二行和第三行是一个unit_time，而第四行和第五行的for循环是2n个unit_time，加上return操作。时间复杂度就是2n+3，一般计算的时候会把常量省略，所以这个程序的时间复杂度就是n。所以就可以推断出，所以代码的执行时间T(n)与每行代码的的执行次数成正比。
引出重要概念：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比，即T(n) = O(f(n))
- 复杂度分析法则
- 单段代码，看循环的次数。
- 多段代码，看代码循环量级。
- 嵌套代码求乘积，比如递归和多重循环。
- 多个规模求加法，方法中并行的两个循环。
- 常用的复杂度级别
- 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括，O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n2)(平方阶)、O(n3)(立方阶)。
- 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这列算法性能极差。包括，O(2^n)(指数阶)、O(n!)(阶乘阶)
- 复杂度分析的四个概念
- 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
- 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
- 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
- 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
ps：区分平均时间复杂度和均摊时间复杂度
- 平均时间复杂度：代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。
- 均摊时间复杂度：两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度，如hashmap查找元素时间复杂度 O(1)；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
1、冒泡排序
基本思想：每次此循环确定未排序的数组的最大值（每轮遍历固定一个元素），出现逆序交换元素，通过比较元素的大小，将较大的数依次交换到最后面。（或者每次寻找最小值，依次交换到最前边）。
复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。
代码实现：
public void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = arr.length - 1; i >= 0; i--) { // 优化：设置标志位 int flag = 1; for (int j = 1; j < i; j++) { // 是稳定排序，这里如果改成<=，那么就是不稳定了 if (arr[j] < arr[j - 1]) { // 出现逆序 swap(arr, j, j - 1); flag = 0; } } if (flag == 1) { // 已经有序，直接退出 return; } } } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }
优化思路：可以设置一个哨兵，如果一轮从前到后的比较没有出现交换，那么这个数组已经是有序数组了，那么后面再比较就没有意义了，可以直接退出。
2、选择排序
基本思想：在未排序序列中找到最小元素，存放到排序序列起始位置。再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。（或者每次在未排序的数组中找最大值，加入排序序列）
ps：类似双指针中minIndex维护排序数组的最后一个元素。
复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。
代码实现：
public void selectSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; // 初始化最小值索引 for (int j = i + 1; j < arr.length; i++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; // 更新最小值索引 } swap(arr, i, minIndex) } } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }
3、插入排序
基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以理解为玩扑克牌时的理牌；
ps：两层for循环都是正向遍历，插入时从已经有序末尾依次进行比较交换。
复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。
注意：如果数组基本有序，那么插入排序会更好。因为插入排序每次是选择一个位置插入到有序的新数组中，如果数据基本有序的情况下，每次寻找插入位置的时间复杂度就基本上是O(1)了，那么总体的时间复杂度就可以是o(n)。
代码实现：
public void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j > 0 && arr[j] > arr[j + 1]; j--) { // 从后向前遍历已经排序数组，寻找插入位置 swap(arr, j, j + 1); } } } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }
优化：进行二分插入，时间复杂度O(nlogn)。
4、希尔排序
基本思想：希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
问题：增量的序列取法？
关于取法，没有统一标准，但最后一步必须是1；因为不同的取法涉及时间复杂度不一样，具体了解可以参考《数据结构与算法分析》；一般以length/2为算法。（再此以gap=gap*3+1为公式）
复杂度分析：时间复杂度O(N^3/2 )，最坏时间复杂度O(N^2)，空间复杂度O(1)。
代码实现：
private static void sort(int[] array) { int n = array.length; int h = 1; while (h < n / 3) { //动态定义间隔序列 h = 3 * h + 1; } while (h >= 1) { for (int i = h; i < n; i++) { for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) { int temp = array[j]; array[j] = array[j - h]; array[j-h]= temp; } } h /= 3; } }
5、归并排序
基本思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想。简言之，先递归的分解数组，再合并有序数组。
复杂度分析：时间复杂度O(NlogN)，空间复杂度O(N)。
代码实现：
public static void mergeSort(int[] arr) { // 主函数 if (arr == null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } //1.递归分解数组 public static void mergeSort(int[] arr, int l, int r) { if (l == r) return; int m = l + ((r - l) >> 1); //注：算数运算符优先级大于移位！ mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } //2.合并成有序数组 public static void merge(int[] arr, int l, int m, int r) { int[] help = new int[r - l + 1]; int index = 0; int p1 = l, p2 = m + 1; while (p1 <= m && p2 <= r) { help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { //p2越界 help[index++] = arr[p1++]; } while (p2 <= r) { //p1越界 help[index++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[l + i] = help[i]; //遍历临时数组，拷贝到原数组（一定注意拷贝到原数组的下标！！！） } }
优化点：（1）已经有序，直接返回，不用合并（2）用同一个tmp数组（3）位运算（4）小区间进行插入排序
class Solution { // 列表大小大于或等于该值，将优先使用归并排序，否则使用插入排序 private static final int INSERTION_SORT_THRESHOLD = 7; public int[] sortArray(int[] nums) { int n = nums.length; int[] tmp = new int[n]; mergeSort(nums, 0, n - 1, tmp); return nums; } private void mergeSort(int[] nums, int left, int right, int[] tmp) { if (right - left <= INSERTION_SORT_THRESHOLD) { insertionSort(nums, left, right); return; } // int mid = left + (right - left) / 2; int mid = left + right >>> 1; mergeSort(nums, left, mid, tmp); mergeSort(nums, mid + 1, right, tmp); // 如果子区间本身有序，则无需合并 if (nums[mid] <= nums[mid + 1]) { return; } merge(nums, left, mid, right, tmp); } // 区间[left, right]进行插入排序 private void insertionSort(int[] nums, int left, int right) { for (int i = left + 1; i <= right; ++i) { // 待插入的元素 int tmp = nums[i]; int j = i; while (j > left && nums[j - 1] > tmp) { // 移动数组元素找到插入位置 nums[j] = nums[j - 1]; j--; } nums[j] = tmp; } } private void merge(int[] nums, int left, int mid, int right, int[] tmp) { System.arraycopy(nums, left, tmp, left, right - left + 1); int i = left; int j = mid + 1; for (int k = left; k <= right; k++) { if (i == mid + 1) { nums[k] = tmp[j]; j++; } else if (j == right + 1) { nums[k] = tmp[i]; i++; } else if (tmp[i] <= tmp[j]) { // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前） nums[k] = tmp[i]; i++; } else { // tmp[i] > tmp[j]:先放较小的元素 nums[k] = tmp[j]; j++; } } } }
6、随机快速排序
基本思想：首先，从数组中随机挑出一个元素，作为基准值（pivot）；然后，按照基准进行分区（partition）操作，最后，递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
复杂度分析：时间复杂度O(NlogN)，空间复杂度O(N)。
代码实现：分区划分的荷兰国旗问题。
// 区域划分：荷兰国旗（三明治结构） public static int[] partition(int[] arr, int l, int r, int num) { int less = l - 1; int more = r + 1; while (l < more) { //变量复用(l相当于index) if (arr[l] < num) { swap(arr, ++less, l++); }else if (arr[l] > num) { swap(arr, l, --more); }else { l++; } } //返回等于区域 return new int[] {less + 1, more - 1}; } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }
代码实现：快速排序
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { //优化：取随机数与最后一个数索引调换（做划分值） swap(arr, l + (int)(Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; // 复用变量l，当前遍历位置 while (l < more) { // 区间最右边的元素做划分值 if (arr[l] < arr[r]) { swap(arr, ++less, l++); } else if (arr[l] > arr[r]) { swap(arr, l, --more); } else { l++; } } // 用完元素，不要忘记归位（划分值） swap(arr, more, r); // 返回等于区域的边界 return new int[] {less + 1, more}; } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }
三数取中法优化代码：
/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/ int SelectPivotMedianOfThree(int arr[],int low,int high) { int mid = low + ((high - low) >> 1);//计算数组中间的元素的下标 //使用三数取中法选择枢轴 if (arr[mid] > arr[high]) { swap(arr[mid],arr[high]); } if (arr[low] > arr[high]) { swap(arr[low],arr[high]); } if (arr[mid] > arr[low]) { swap(arr[mid],arr[low]); } //此时，arr[mid] <= arr[low] <= arr[high] return arr[low]; //low的位置上保存这三个位置中间的值 //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了 }
快排的优化思路：
基准值选取：
- 随机选取划分基准值pivot ：
l + (int)(Math.random() * (r - l + 1)) - 三数取中法取划分基准值pivot，但处理不了重复数组
其他优化：
- 对于小区间切换到插入排序(对于存在很多重复序列的情况，分割成小区间)
- 在一次排序后，可以将与基准值相等的数放在一起，在下次分割时可以不考虑这些数。(聚集相等的元素)
7、堆排序
基本思想：堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
复杂度分析：时间复杂度O(NlogN)，空间复杂度O(1)。
代码实现：
public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); //0-i之间形成大根堆 } int size = arr.length; swap(arr, 0, --size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } //转换为大根堆,添加元素 public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } //使用异或当(即位运算交换两个数)i=j时可能会出错 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //当出现某个位置的数值改变怎么调整 public static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; while (left < heapSize) { //找最大值的下标 (算术运算符的优先级大于关系运算符) int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; //左右孩子的最大值和父节点比较 largest = arr[largest] > arr[index] ? largest : index; if (index == largest) { break; } swap(arr, index, largest); index = largest; left = index * 2 + 1; } }
8、计数排序
基本思想：将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
复杂度分析：时间复杂度O(N + K)，空间复杂度O(N + K)。
代码实现：
/** * 输入数组的元素都是介于0..k之间的 * @param data 待排序数组 * @param k 最大元素 * @return 排序结果 */ public static int[] countingSort(int[] data, int k) { // 存放临时数据的数组tmp，初始元素都是0；k为数组中最大元素 int[] tmp = new int[k + 1]; // 计算数组中每个元素i出现的次数，存入数组tmp中的第i项，即原数组中的元素值为tmp数组中的下标 for (int i = 0; i <= data.length - 1; i++) { tmp[data[i]]++; } // 计算数组中小于等于每个元素的个数,即从tmp中的第一个元素开始，每一项和前一项相加 for (int j = 1; j <= k; j++) { tmp[j] = tmp[j] + tmp[j - 1]; } // result数组用来来存放排序结果 int[] result = new int[data.length]; for (int i = data.length - 1; i >= 0; i--) { result[tmp[data[i]] - 1] = data[i]; tmp[data[i]]--; } return result; }
9、桶排序
基本思想：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
复杂度分析：时间复杂度O(N + K)，最坏时间复杂度O(N^2)，空间复杂度O(N + K)。
代码实现：
public static void bucketSort(double array[]) { int length = array.length; ArrayList arrList[] = new ArrayList[length]; for (int i = 0; i < length; i++) { //0.7到0.79放在第8个桶里,编号7；第一个桶放0到0.09 int temp = (int) Math.floor(10 * array[i]); if (null == arrList[temp]) arrList[temp] = new ArrayList(); arrList[temp].add(array[i]); } // 对每个桶中的数进行插入排序 for (int i = 0; i < length; i++) { if (null != arrList[i]) { Collections.sort(arrList[i]); } } int count = 0; for (int i = 0; i < length; i++) { if (null != arrList[i]) { Iterator iter = arrList[i].iterator(); while (iter.hasNext()) { Double d = (Double) iter.next(); array[count] = d; count++; } } } }
10、基数排序
基本思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
复杂度分析：时间复杂度O(N * K)，空间复杂度O(N + K)。
代码实现：
private static void radixSort(int[] array,int radix, int distance) { int length = array.length; int[] temp = new int[length]; int[] count = new int[radix]; int divide = 1; for (int i = 0; i < distance; i++) { System.arraycopy(array, 0,temp, 0, length); Arrays.fill(count, 0); for (int j = 0; j < length; j++) { int tempKey = (temp[j]/divide)%radix; count[tempKey]++; } for (int j = 1; j < radix; j++) { count [j] = count[j] + count[j-1]; } for (int j = length - 1; j >= 0; j--) { int tempKey = (temp[j]/divide)%radix; count[tempKey]--; array[count[tempKey]] = temp[j]; } divide = divide * radix; } }
应用场景分析：
（1）若数据规模较小（如n <= 50），可以使用简单的直接插入排序或者直接选择排序（不稳定）。
（2）若文件的初始状态基本有序，排序关键字移动次数较少，则应选用直接插入或冒泡排序为宜；
（3）若文件初始状态随机分布，则应选用快速排序为宜，平均时间复杂度O(nlogn)；
（4）若数据规模较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序；
- 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；虽然可能退化为O(N^2)，但这种概率很小。
ps：堆排序每次取一个最大值和堆底部的数据交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来，可以说堆排序做了许多无用功。堆排序过程里的交换跟快排过程里的交换虽然都是常量时间，但是常量时间差很多。 - 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。堆排序和快速排序都是不稳定的。
- 若要求排序稳定，则可选用归并排序（外部排序）。从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。推荐：先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
![[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解](https://ucc.alicdn.com/pic/developer-ecology/qy2cxr5w3tthc_33f1d390347b4adeb98b335ecc73ec77.jpeg?x-oss-process=image/resize,h_160,m_lfit)