以下是10多种常见排序算法的时间复杂度表格及稳定性分析 ：

各排序算法简介

• 直接插入排序：对于已经有序的数据，只需比较$n-1$次，时间复杂度为$O(n)$；最坏情况是待排序数组逆序，时间复杂度为$O(n^2)$。
• 希尔排序：是插入排序的改进版，通过分组插入排序提高效率，时间复杂度与增量序列的选取有关。
• 计数排序：要求输入数据是有确定范围的整数，通过统计小于每个数的个数来确定其位置，时间复杂度为$O(n + k)$。
• 桶排序：将待排序元素分配到不同的桶中，对每个桶中的元素进行排序后再合并，适用于元素分布均匀的情况。

1. 稳定性解释
   • 冒泡排序
     • 它在比较相邻元素时，如果两个元素相等，不会交换它们的位置，所以相同元素的相对顺序不会改变，是稳定的排序算法。
   • 插入排序
     • 在插入元素的过程中，如果遇到相同大小的元素，会将新元素插入到已有相同元素的后面，不会改变相同元素的相对顺序，因此是稳定的。
   • 选择排序
     • 它会选择最小（或最大）的元素与当前位置的元素交换，可能会改变相同元素的相对顺序。例如，序列中有两个相等的元素，后面的元素可能会被先选走并交换到前面，所以是不稳定的。
   • 快速排序
     • 在划分过程中，基准元素的位置会改变相同元素的相对顺序。例如，当以序列最左边元素为基准时，可能会把右边相同的元素划分到不同的子序列中，导致相同元素的相对顺序改变，是不稳定的。
   • 归并排序
     • 在合并两个有序子序列时，如果遇到相同的元素，会按照顺序将它们合并，不会改变相同元素的相对顺序，是稳定的排序算法。
   • 堆排序
     • 在堆的调整过程中，可能会改变相同元素的相对位置。例如，在最大堆调整时，可能会把堆顶的元素和最后一个元素交换，导致相同元素的相对顺序改变，所以是不稳定的。

1. 冒泡排序（Bubble Sort）

   • 基本原理：
     • 它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
   • 时间复杂度：
     • 最好情况：当输入的数列已经是有序的，只需要进行一次遍历，比较次数为$n - 1$次（$n$是数列元素个数），时间复杂度为$O(n)$。这是因为在这种情况下，内层循环每次比较相邻元素，发现都是有序的，不会进行交换操作。
     • 最坏情况：当数列是逆序排列时，需要进行$n - 1$轮比较，每轮比较的次数依次为$n - 1,n - 2,\cdots,1$，总的比较次数为$\frac{n(n - 1)}{2}$，时间复杂度为$O(n^{2})$。
     • 平均情况：平均时间复杂度也是$O(n^{2})$，因为在平均情况下，大约一半的元素需要交换位置，交换操作的时间复杂度也是$O(n^{2})$。

2. 插入排序（Insertion Sort）

   • 基本原理：
     • 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
   • 时间复杂度：
     • 最好情况：如果数列已经是有序的，每次插入操作只需要比较一次，总共需要$n - 1$次比较，时间复杂度为$O(n)$。
     • 最坏情况：当数列是逆序排列时，每次插入一个元素都需要移动已排序的所有元素，第$i$个元素需要移动$i - 1$次，总的移动次数为$\frac{n(n - 1)}{2}$，时间复杂度为$O(n^{2})$。
     • 平均情况：平均时间复杂度同样是$O(n^{2})$，因为平均每次插入操作需要移动一半已排序的元素。

3. 选择排序（Selection Sort）

   • 基本原理：
     • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
   • 时间复杂度：
     • 最好情况：无论数列是否有序，都需要进行$\frac{n(n - 1)}{2}$次比较，因为每次都要遍历未排序的部分来找到最小（大）元素，时间复杂度为$O(n^{2})$。
     • 最坏情况：和最好情况一样，时间复杂度为$O(n^{2})$。
     • 平均情况：时间复杂度也是$O(n^{2})$。

4. 快速排序（Quick Sort）

   • 基本原理：
     • 它采用了分治的策略。选择一个基准元素，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序。
   • 时间复杂度：
     • 最好情况：每次划分都能将数组分成两个大小差不多的子数组，时间复杂度为$O(nlogn)$。这是因为每次划分后，问题规模以对数的方式减小，总共需要划分$logn$层，每层的比较次数大约为$n$。
     • 最坏情况：当数组已经有序或者逆序时，每次划分只得到一个比上一轮少一个元素的子数组，时间复杂度为$O(n^{2})$。例如，选择的基准元素是最小或最大的元素，会导致这种情况。
     • 平均情况：在平均情况下，时间复杂度为$O(nlogn)$，这是快速排序的一个重要特性，使其在实际应用中非常高效。

5. 归并排序（Merge Sort）

   • 基本原理：
     • 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
   • 时间复杂度：
     • 最好情况：时间复杂度为$O(nlogn)$。因为归并排序的过程是先将数组不断地二分，直到子数组只有一个元素（这个过程需要$logn$步），然后再将这些子数组两两合并（每次合并的操作数与子数组的元素总数有关，大约为$n$）。
     • 最坏情况：和最好情况一样，时间复杂度为$O(nlogn)$。
     • 平均情况：时间复杂度为$O(nlogn)$。

6. 堆排序（Heap Sort）

   • 基本原理：
     • 堆排序是利用堆这种数据结构所设计的一种排序算法。它是选择排序的一种。先将数列构建成一个最大堆（或最小堆），然后每次取出堆顶元素（最大值或最小值），将剩余元素重新调整为堆，直到所有元素都被取出。
   • 时间复杂度：
     • 最好情况：时间复杂度为$O(nlogn)$。构建初始堆的时间复杂度为$O(n)$，每次调整堆的时间复杂度为$O(logn)$，总共需要进行$n - 1$次调整，所以总的时间复杂度为$O(nlogn)$。
     • 最坏情况：和最好情况一样，时间复杂度为$O(nlogn)$。
     • 平均情况：时间复杂度为$O(nlogn)$。