排序（冒泡排序、选择排序、插入排序、希尔排序)--＞深度剖析(一)

前言

排序是一种基本的数据处理操作，它涉及将一系列项目重新排列，以便按照指定的标准（通常是数值大小）进行排序。在C语言中，排序算法是用来对元素进行排序的一系列步骤。

排序的概况

C语言中的排序算法是一系列用于将一组数据按照特定顺序进行排列的算法。这些算法通常根据元素之间的大小关系来确定它们在最终排序结果中的位置。

衡量排序的标准

• 时间复杂度（参考：时间空间复杂度介绍）
• 辅助空间：有些排序算法在排序过程中需要额外的空间来辅助排序，例如归并排序和快速排序。这些算法的辅助空间通常为O(n)，而有些算法如插入排序和冒泡排序的辅助空间为O(1)
• 稳定性：稳定性是指在排序过程中，相等键值的元素在原始序列中的相对位置是否保持不变。稳定排序算法会维持相等元素的相对次序，而不稳定排序算法则可能改变这些元素的相对次序。

• 特殊情况下性能：某些排序算法在特定情况下可能表现得更优，例如当数据已经部分有序时，插入排序和冒泡排序可能会更快。而快速排序在这种情况下可能会变慢。

冒泡排序（Bubble Sort）

冒泡排序概念

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。这个过程会重复进行，直到没有再需要交换的元素，这意味着数列已经排序完成。这个过程就像是气泡一样，较小（或较大）的元素会逐渐“冒泡”到列表的顶端

代码实现

冒泡排序算法的实现通常涉及两个嵌套的for循环。外层循环控制每一轮的比较次数，内层循环用于比较相邻元素并进行交换。

//冒泡排序
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n-i-1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
      }
    }
  }
}

优化冒泡排序

当冒泡排序遇见 {2，1，4，5，6，7，8，9，10} 这样的数据就会大大折扣性能。如遇见如此的数据进行排序，我们可以定义一个bool类型flag = false 当数据进行交换的时候我们改变flag；

代码如下：

//冒泡排序
void BubbleSort(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
        bool flag = false;
    for (int j = i; j < n-i-1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
                flag = true;
      }
            if (flaf == false)
            {
                break;
            }
    }
  }
}

冒泡排序复杂度分析

冒泡排序算法的时间复杂度为O(n^2）， 这是因为在最坏的情况下，即数组完全逆序时，冒泡排序需要进行n-1轮比较和交换，其中n是数组的长度。每一轮比较需要比较n-i次（i为当前轮数），因此总的比较次数为n*(n-1)/2。所以，冒泡排序的时间复杂度为O(n^2)

选择排序（Selection Sort）

选择排序的概念

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是在每一轮中从不排序的子序列中选取最小（或最大）的元素，将其与子序列的起始位置的元素交换，从而逐渐构建起有序序列。

代码实现

选择排序思想简单，排序大->小（小->大），就遍历数组记录即可。

//交换
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

//选择排序
void SelectSort(int* a, int n)
{
  int min = 0;
  int begin = 0;
  while (begin < n - 1)
  {
    for (int i = begin; i < n; i++)
    {
      if (a[i] < a[min])
      {
        min = i;
      }
    }
    Swap(&a[min], &a[begin]);
    ++begin;
  }
}

优化选择排序

选择排序可以通过一些优化手段进行提升，例如使用哨兵变量来减少内层循环的判断次数等。这些优化手段可以在一定程度上提高选择排序的执行效率。（在这里就不实现了）

选择排序的复杂度分析

选择排序的时间复杂度为 O(n^2)，其中n是数组的长度。这是因为算法需要进行两层循环，外层循环控制排序的轮数，内层循环则负责在每一轮中找到最小元素。

插入排序（Insertion Sort）

插入排序的概念

插入排序是一种简单直观的排序算法，它的基本思想是将未排序的元素插入到已排序元素形成的有序序列中。在每一轮排序中，都会将一个待排序的元素插入到它应该所在的位置，直到所有元素都被插入完毕。

代码实现

定义循环进行比较将大（小）的值相后面依次挪动，直至寻找到比自己小（大）的值位置进行插入。

//插入排序
void InsertionSort(int* a, int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = a[end + 1];

    while (end >= 0)
    {
      if (a[end] > tmp)
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;
  }
}

插入排序的优化

• 可以进行二分插入，它通过二分查找来确定待插入位置，从而减少了比较和移动的次数。
• 希尔排序是对直接插入排序的优化，它通过增加一个间隙因子来分组排序，使得每个组内部的元素可以先进行排序，然后逐渐减小间隙因子，直到间隙因子为1，此时整个数组已经接近有序，插入排序的效率会得到提高

插入排序复杂度分析

• 最佳情况：如果输入数组已经是完全有序的，插入排序只需要进行 n 次比较（每次比较后插入一个元素到已排序部分），而不需要进行任何交换。在这种情况下，时间复杂度是 O(n)。
• 平均情况：在平均情况下，插入排序的时间复杂度是 O(n^2)。这是因为每个元素都需要与已排序部分的多个元素进行比较，平均下来，每个元素需要比较 n/2 次。

• 最坏情况：如果输入数组是完全逆序的，插入排序需要进行 n(n-1)/2 次比较和 n(n-1)/2 次交换，时间复杂度是 O(n^2)

希尔排序（Shell Sort）

希尔排序的概念

希尔排序（Shell Sort）是一种基于插入排序的算法，它通过引入增量序列，采取分组排序策略：将大数组分为若干个子序列，对每个子序列进行插入排序。随着增量逐渐减小，子序列变得更小，最终达到增量为1，整个数组变成一个有序序列，完成排序。这种排序方式使得希尔排序在初始阶段，使用较大的步长让序列更快时间的接近有序，并且减少了不必要的比较与交换。

代码实现

//希尔排序
void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap >= 1)
  {
    gap /= 2;

    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}

希尔排序复杂度分析

希尔排序算法的平均时间复杂度通常被认为是介于 O(n log n) 和 O(n^2) 之间，具体取决于所选择的间隔序列。在最佳情况下，当间隔序列满足特定条件时，希尔排序可以达到接近 O(n) 的时间复杂

度。然而，在最坏情况下，希尔排序的时间复杂度为 O(n^2)。

break;
      }
    }
    a[end + gap] = tmp;
  }
}

}

## 希尔排序复杂度分析

希尔排序算法的平均时间复杂度通常被认为是介于 O(n log n) 和 O(n^2) 之间，具体取决于所选择的间隔序列。在最佳情况下，当间隔序列满足特定条件时，希尔排序可以达到接近 O(n) 的时间复杂度。然而，在最坏情况下，希尔排序的时间复杂度为 O(n^2)。