三大经典排序：冒泡排序（Bubble Sort）、快速排序（Quick Sort）、插入排序（Insertion Sort）_冒泡排序法,快速排序法还有啥

在计算机编程中，特别是在使用C语言这样的底层语言时，排序算法是非常基础且重要的。在众多排序算法中，有三种被广泛认为是经典的，它们各自在不同的场景下有着不同的应用和优势。

这三种经典的排序算法是：冒泡排序（Bubble Sort）、快速排序（Quick Sort）、插入排序（Insertion Sort）。

一、 冒泡排序（Bubble Sort）

        冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这意味着数列已经排序完成。冒泡排序的名字由来是因为较小的元素会经由交换慢慢“浮”到数列的顶端，就像水中的气泡一样上升到水面

1.基本思想：

        通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

2.特点：

        实现简单，性能在平均情况下是O(n^2)的时间复杂度，适合小规模数据的排序。

3.算法步骤：

1）比较相邻的元素。如果第一个比第二个大，就交换它们两个。

2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

4.图示：

5.示例代码： 

void bubbleSort(int arr[], int n) 
{
    int i, j, temp;
    for (i = 0; i < n-1; i++) 
    {
        for (j = 0; j < n-i-1; j++) 
        {
            if (arr[j] > arr[j+1]) 
            {
                // 交换两个元素
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

6.性能分析：

• 时间复杂度：
  • 最佳情况：O(n)，当输入的数据已经是正序时。
  • 平均情况：O(n^2)。
  • 最坏情况：O(n^2)，当输入的数据是反序时。
• 空间复杂度：O(1)，因为只需要用到少数几个变量，是一个原地排序算法。
• 稳定性：冒泡排序是稳定的排序算法，因为它保证了两个相等的值不会因为排序而改变顺序。

        尽管冒泡排序是最容易理解和实现的排序算法之一，但由于其平均和最坏情况的时间复杂度都是O(n^2)，所以它不适用于数据量大的排序应用。然而，在数据量小或几乎已经排序的情况下，冒泡排序仍然是一个不错的选择。

 

二、 快速排序（Quick Sort）

         快速排序是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它使用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的平均时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。尽管最坏的情况不常见，通过随机化选择或者“三数中值”分割策略可以大大减少这种情况的发生。

1.基本思想：

        选择一个基准元素，通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有记录比另一部分的所有记录都要小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2.特点：

        平均情况下，快速排序的时间复杂度为O(n log n)，是效率较高的排序算法之一，尤其是在大数据集上。但是最坏情况下时间复杂度退化为O(n^2)。

 3.算法步骤：

1）选择基准值（Pivot）：从数列中挑出一个元素，称为“基准”（pivot）。

2）分割（Partitioning）：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。

3）递归排序子序列：递归地（recursive）将小于基准值元素的子序列和大于基准值元素的子序列排序。 递归到最底部时，数列的大小是零或一，也就是自然有序的。然后，从递归调用中一层一层返回，直到整个数列都排序好。

4.图示：

5.示例代码：

int partition(int arr[], int low, int high) 
{
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) 
    {
        if (arr[j] < pivot) 
        {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换 arr[i+1] 和 arr[high] (或 pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}
 
void quickSort(int arr[], int low, int high) 
{
    if (low < high) 
    {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

6.性能分析：

• 时间复杂度：
  • 最佳情况：O(n log n)，当分区操作每次都能将序列等分时。
  • 平均情况：O(n log n)。
  • 最坏情况：O(n^2)，当分区操作每次选择的基准都是最大或最小的元素时。
• 空间复杂度：O(log n)，主要是递归造成的栈空间的使用。
• 稳定性：快速排序是不稳定的排序算法，因为分区过程中相等的元素可能会因为分区而改变相互的先后顺序。

        快速排序是最常用的排序算法之一，适用于大多数场景，尤其是在数据量大的情况下。通过合理选择基准值和优化递归操作，可以显著提高其排序效率。

三、插入排序（Insertion Sort）

        插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在小规模数据或几乎已经排序的数据集上表现良好。

1基本思想：

        将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录开始，逐个进行插入，直到整个序列有序。

2.特点：

        插入排序在最佳情况下的时间复杂度为O(n)，在平均和最坏情况下的时间复杂度为O(n^2)。适合于小规模数据的排序，以及部分已经排序的数据。

3.算法步骤：

1）从第一个元素开始，该元素可以认为已经被排序；

2）取出下一个元素，在已经排序的元素序列中从后向前扫描；

3）如果该元素（已排序）大于新元素，将该元素移到下一位置；

4）重复步骤3，直到找到已排序的元素小于或等于新元素的位置；

5）将新元素插入到该位置后；

6）重复步骤2~5。

4.图示：

5.示例代码：

void insertionSort(int arr[], int n) 
{
    int i, key, j;
    for (i = 1; i < n; i++) 
    {
        key = arr[i];
        j = i - 1;
 
        /* 将 arr[i] 移动到其正确位置 */
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

6.性能分析：

• 时间复杂度：
  • 最佳情况：O(n)，当输入数组已经是排好序的情况。
  • 平均情况：O(n^2)，适用于较小的数据集。
  • 最坏情况：O(n^2)，当输入数组是反序的情况。
• 空间复杂度：O(1)，它是一个原地排序算法。
• 稳定性：插入排序是稳定的排序算法，因为它保证了不会改变相等元素的相对顺序。

        插入排序虽然在最坏情况下的时间复杂度较高，但它是自适应的，能够在接近排序好的数据上运行得更快。因此，在处理小数据集或部分已排序的数据时，插入排序可以是一个不错的选择。此外，由于其简单性，它通常被用作更复杂排序算法如快速排序的递归基准案例。