八大排序算法【上】

冒泡排序

冒泡排序是一种 稳定 的排序算法。

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

假设我们想要从小到大进行排序：

• 第一次冒泡：将最大值放到了数组的最后一位；

• 第二次冒泡：将第二大值放在数组的倒数第二位；

• 以此类推。

void BubbleSort(int arr[], int num)
{
   
    // 需要 num-1 次冒泡
    for (int i = 0; i < num - 1; ++i)
    {
   
        for (int j = 0; j < num - i - 1; ++j)
        {
   
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
}

复杂度分析：

当序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 $ O(N)$;

在最坏情况下，冒泡排序要执行 $(n-1)\cdot n/2$次交换操作，时间复杂度为 $O(N^2)$；

冒泡排序的平均时间复杂度为 $O(N^2)$。

选择排序

每次选择一个最大/最小的数，与当前位置的数进行交换。

由于 swap（交换两个元素）操作的存在，可能打乱相等数的相对顺序，因此选择排序是一种 不稳定 的排序算法。

void SelectionSort(int arr[], int num)
{
   
    // 需要 num-1 次选择
    for (int i = 0; i < num - 1; ++i)
    {
   
        int mini = i;
        for (int j = i; j < num; ++j)
        {
   
            if (arr[j] < arr[mini]) mini = j;
        }
        swap(arr[i], arr[mini]);
    }
}

复杂度分析：

最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 $O(N^2)$。

插入排序

插入排序是一种 稳定 的排序算法。

插入排序的思想：将当前元素与已经排好序的子数组中的元素逐个比较，找到合适的位置插入当前元素。

void InsertionSort(int arr[], int num)
{
   
    // 从下标 1 开始
    for (int i = 1; i < num; ++i)
    {
   
        int cur = arr[i];
        int index = i;

        // 将大于 cur 的元素向右移动
        while (index - 1 >= 0 && arr[index - 1] > cur)
        {
   
            arr[index] = arr[index - 1];
            index--;
        }

        // 将 cur 插入到正确的位置
        arr[index] = cur;
    }
}

复杂度分析：

最优时间复杂度为 $ O(N)$，最坏时间复杂度和平均时间复杂度都为 $O(N^2)$。

希尔排序(**)

希尔排序是一种改进版的插入排序，其基本思路如下：

• 选择增量： 选择一个增量，来决定元素之间的间隔，通常增量选择数组总长度的一半；

• 分组排序： 根据选定的增量，将数组元素分成若干组；对于每一组，使用插入排序的方法进行排序；

• 逐步缩小增量： 逐步减小增量并重复上述分组和排序步骤，直至增量为 1。

当增量减小至 1 时，相当于进行一次普通的插入排序，此时数组已经被排好序了。

因为希尔排序进行了分组，可能打乱相等数的相对位置，希尔排序是一种 不稳定 的排序算法。

void ShellSort(int arr[], int num)
{
   
    // 选择增量
    int dist = num / 2;
    while (dist)
    {
   
        for (int i = dist; i < num; ++i)
        {
   
            int cur = arr[i];
            int index = i;
            while (index - dist >= 0 && arr[index - dist] > cur)
            {
   
                arr[index] = arr[index - dist];
                index -= dist;
            }
            arr[index] = cur;
        }
        dist /= 2;  
    }     
}

复杂度分析：

通常情况下，希尔排序的时间复杂度介于 $O(n{\log }^{2}n)$ 和 $O(n^2)$ 之间。