基本概念：

排序的稳定性：

若序列中关键字值相等的值，排序前后的相对顺序保持不变，则称这种排序算法是稳定的，否则即为不稳定。
例如对于：
待排序列：34 12 34‘ 08 96
稳定：08 12 34 34‘ 96
不稳定：08 12 34’ 34 96

排序的基本方法：

插入排序：

基本思想：
默认已完成元素已排好序，依次从未完成序列中提取新元素，将其与前面的元素进行比较，若前面的元素比他大，就将元素向前移动，直至前面的元素小于等于该元素。
算法实现：

void insertSort(int a[], int l, int r)
{
   int i, j;
   int t;
   for(i = l + 1; i <= r; ++i){
      t = a[i];  //保存当前要插入的值
      //从后往前，依次将较大的元素后移一位
      for(j = i - 1; j >= 0 && t < a[j]; j--){
          a[j+1] = a[j];
      }
      a[j+1] = t;
   }
}

性能分析：
时间复杂度：O()
空间开销：O(1)
稳定性：稳定
适用于节点数较少的场景。

冒泡排序：

基本思想：
依次比较两个相邻的元素，若顺序不对，则两者交换。重复操作直至全部被排好序。
算法实现：

void bubbleSort(int a[], int l, int r)
{
   for(int i = l ; i < r; ++i){
     for(int j = l ; j < r - i + 1; ++j){
        if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
     }
   }
}

性能分析：
时间复杂度：O()
空间开销：O(1)
稳定性：稳定。

选择排序：

基本思想：
首先选出键值最小的项，将其与第一个项交换位置。然后选出第二小的项，将其与第二个项交换位置，重复进行…
算法实现：

void SelectSort(int a[], int l, int r){
  int i, j, min;
  for(i = l; i < r; ++i){
     for(min = i, j =i + 1; j <= r; ++j){
        if(a[j] < a[min]) min = j;
     }
     swap(a[min], a[i]);
  }
}

性能分析：
时间复杂度：O()
稳定性：不稳定。

归并排序：

基本思想：
即利用分治思想。设出一个分界点mid。设出一个新数组temp临时存放结果。假设原数组mid的右半部分均大于左半部分。从左右两边向中间开始遍历，较小的先放入temp数组中。
归并排序主要包括自顶向下和自底向上两种解决方法。

自顶向下归并排序：

基本步骤：
先递归排序左半部分；
再递归排序右半部分；
最后将两个已排好序的子数组合并。
算法实现：

//merge原子操作
void merge(int a[], int l, int m, int r){
  int i, j;
  static int temp[N];
  //左半部分升序，右半部分降序
  for(i = m + 1; i > l; --i) temp[i-1] = a[i-1];
  for(j = m; j < r; ++j) temp[r + m - j] = a[j+1];
  //逐个比较，进行升序合并。
  for(int k = l; k <= r; ++k){
      if(temp[j] < temp[i]) a[k] = temp[j--];
      else a[k] = temp[i++];
  }
}
//Merge实现操作
void MergeSort(int a[], int l, int r){
   if(r <= l) return;
   int m = (l + r)/2;
   MergeSort(a, l, m);
   MergrSort(a, m+1, r);
   merge(a, l, m, r);
}

自底向上归并排序：


void merge(int a[], int left, int mid, int right){
   int n = right - left + 1;
   int* temp = new int[n];
   
   int i = left;
   int j = mid + 1;
   int k = 0;
   
   while(i <= mid && j <= right){
     if(a[i] <= a[j]){
         temp[k++] = a[i++];
     }
     else temp[k++] = a[j++];
   }
   while(i <= mid) temp[k++] = a[i++];
   while(j <= right) temp[k++] = a[j++];
   
   for(i = left, k = 0; i <= right; i++, k++){
      a[i] = temp[k];
   }
   delete[] temp;
}

void mergeSort(int a[], int l, int r){
   if(l >= r) return;
   for(int m = 1; m <= r - l; m = m + m){  //步长，逐渐倍增符合二分思想
     for(int i = l; i <= r - m; i += m + m){
        int mid = i + m - 1;  //第一个数组结束位置
        int right = min(i + m + m - 1, r);   //第二个数组右边界
        merge(a, i, mid, right);
     }
   }
}

时间复杂度：

平均：O(NlogN)
最坏：O(NlogN)
归并排序是稳定的

一轮循环操作结果求解：
对于内部已经分为若干个有序子序列的，即采用自底向上归并排序方法：
设一组初始记录关键字序列（【25，50】，【15，35】，【80，85】，【20，40】，【36，70】），其中含有5个长度为2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为？
——解：
mergeL1与L2：
25与15比较——选择15；25与35比较——选择25；35与50比较——选择35…
…
mergeL1与L2，L3与L4后，L5剩余：
得到：15，25，35，50，20，40，80，85，36，70。

快速排序：

void QuickSort(int a[], int l, int r){
  if(l >= r) return;
  int mid = (a[l] + a[r]) / 2;
  int i = l - 1;
  int j = r + 1;
  while(i < j){
    do i++; while(a[i] < mid);
    do j--; while(a[j] > mid);
    if(i < j) swap(a[i], a[j]);
  } 
  QuickSort(a, l, j);
  QuickSort(a, j + 1, r);
}

时间复杂度：

平均：O(NlogN)
最坏：O( $N^{2}$ )
快速排序是稳定的
实际执行：采用挖坑填数法——解决首轮循环状态问题
设一组初始关键字记录为（20， 15， 14， 18， 21， 36， 40， 10），则以20为基准记录的一趟快速排序结束后的结果为：
解：
由于20为基准，故i = 0 的位置设置为坑。j从7位置开始，10小于20，故填充到坑中——
10，15，14，18，21，36，40，20【此时位置7为一处坑】
i从左开始，遍历到21大于20，，将21填到坑中——
10，15，14，18，20，36，40，21
再将j继续左移，直至与i相遇

希尔排序：

思路：

先选定一个步长，通过步长对于原数组进行分组，再对分成的每一小组进行插入排序。
逐步缩小步长的大小，直至步长为1时，视作原数组结束。

int gap = n;

while(gap > 1){
  gap /= 2;
  for(int i = 1; i < n - gap + 1; ++i){
    int ed = i;
    int temp = a[ed + gap];
    while(ed >= 1){
      if(temp < a[ed]){
        a[ed + gap] = a[ed];
        ed -= gap;
      }
      else break;
    }
    a[ed + gap] = temp;
  }
}

各排序方法的每趟特点比较

冒泡排序：
看数组末尾，每一趟中最大的元素会出现“沉底”现象，逐渐累积到后面；
插入排序：
第n趟排序后，前n个元素应该是有序的。
选择排序：
看数组开头，前k个元素是全局最小的且已就绪。
希尔排序：
以特定间隔分组的子序列各自有序。
快速排序：
基准中间元素就绪，左右分区区别形成，但内部无序。

计数排序：

计数排序能够实现 O(N+K)O(N+K) 时间复杂度的核心在于：它利用了待排序元素的取值范围（0 到 K-1）这一额外信息，通过”计数”而不是”比较”来确定每个元素的位置。

详细解释其工作原理和复杂度推导如下：

1. 算法核心思想

传统的比较排序（如快速排序、归并排序）的下界是 O(Nlog⁡N)O(NlogN)，因为它们需要通过比较来确定元素间的相对顺序。
而计数排序假设每个输入元素都是介于 0 到 K-1 之间的整数。它利用这一先验知识，通过统计每个值出现的次数，直接计算出每个元素在输出数组中的最终位置。

2. 实现步骤与复杂度分析

假设输入数组 A 长度为 N，所有元素范围在 (0, k-1)。

步骤 1：统计频率

创建一个长度为 K 的计数数组 C，初始化为 0。
遍历输入数组 A，对于每个元素的值 A[i]，执行 C[A[i]]++。
时间复杂度：遍历 N 个元素，执行 N 次操作。O(N)O(N)

步骤 2：计算累积计数

将计数数组 C 转换为累积计数（前缀和）。公式：C[i] = C[i] + C[i-1]。
这一步结束后，C[i] 表示”小于等于 i 的元素有多少个”。这意味着，对于值 i，它应该出现在输出数组的第 C[i] 个位置（如果考虑从 1 开始计数的话）。
时间复杂度：遍历 K 次。O(K)O(K)

步骤 3：构建输出数组

创建一个与输入等长的输出数组 B。
为了保证算法的稳定性（即相同元素的相对顺序不变），需要从后往前遍历输入数组 A。
对于当前元素 A[j] = v：
1. 查找 C[v] 的值，这个值减 1 就是 v 在输出数组 B 中的正确索引。
2. 将 A[j] 放入 B[C[v] - 1]。
3. 将 C[v] 减 1（这样下次再遇到相同的 v 时，就会放到前一个位置）。
时间复杂度：遍历 N 个元素，执行 N 次操作。O(N)O(N)

3. 为什么是 O(N+K)

总时间：步骤 1 (O(N)O(N)) + 步骤 2 (O(K)O(K)) + 步骤 3 (O(N)O(N)) = O(N+K)+O(N+K)=O(N+K)O(N+K)+O(N+K)=O(N+K)。

4. 为什么比其他排序快？

没有比较：整个过程没有进行任何元素之间的两两比较。它通过数值直接索引到计数数组，从而获得位置信息。
空间换时间：它使用了额外的 K 长度的数组来存储计数，从而避免了 O(Nlog⁡N)O(NlogN) 的比较开销。

5. 局限性

虽然 O(N+K)O(N+K) 看起来比 O(Nlog⁡N)O(NlogN) 好，但它只有在 K 不太大 的时候才实用。如果 K 非常大（例如 K=N2K=N2），那么 O(N+K)O(N+K) 会变成 O(N2)O(N2)，比快速排序还慢。