排序算法：最慢到最快

2025年3月17日 | 阅读42分钟

在接下来的教程中，我们将讨论不同的排序算法，并根据它们的复杂度进行比较。

那么，让我们开始吧。

什么是排序算法？

排序算法是一组指令，它接受数组或列表作为输入，并将数据元素按特定顺序排列。

排序最常见的是按数字顺序或字母（或词典）顺序进行，排序顺序可以是升序（0-9，A-Z）或降序（9-0，Z-A）。

理解排序算法的重要性

排序算法在计算机科学中起着重要作用，因为它们通常可以降低问题的复杂度。这些算法直接应用于搜索算法、数据库管理算法、数据结构算法、分而治之方法等。

以下是一些排序算法在现实世界中实现的最佳示例：

气泡排序算法通常用于电视节目中，以根据观众观看时间对频道进行排序。
数据库使用外部归并排序算法来排序无法完全加载到内存中的大型数据集。
体育比赛得分使用快速排序算法实时快速地进行组织。
除了上述之外，还有许多其他排序算法的实际应用示例。

理解数据结构中的排序类型

数据结构中的排序技术分为几类：

基于比较的排序：在基于比较的排序技术中，定义一个比较器来比较数据样本的数据元素或项。此比较器规定了元素的顺序。基于比较的排序的一些示例如冒泡排序和归并排序。
基于计数的排序：在基于计数的排序技术中，数据样本的数据元素之间不进行比较；然而，它在执行期间基于计算出的假设。基于计数的排序的一些示例如计数排序和基数排序。
原地排序和非原地排序技术：原地排序技术用于在原始数组内修改数组元素的顺序。

同时，非原地排序技术利用辅助数据结构来排序原始数组。原地排序技术的一些示例如冒泡排序和选择排序。非原地排序算法的一些示例如归并排序和快速排序。

一些常见的排序算法

以下是一些常用排序算法的列表：

冒泡排序
选择排序
插入排序
快速排序
合并排序
计数排序
基数排序
桶排序
梳排序
希尔排序

让我们通过它们的时间和空间复杂度来检查上述排序算法，以确定最快的排序算法。

冒泡排序

冒泡排序是最简单的排序算法。冒泡排序的基本概念是，如果数据元素不处于期望的顺序，则反复交换相邻的数据元素。

假设给定一个包含五个不同数据元素的未排序数组。在这种情况下，冒泡排序将首先比较数组的第一个数据元素和第二个数据元素，如果第一个大于第二个，则立即交换它们，然后继续比较第二个和第三个数据元素，依此类推。

让我们通过一个例子来理解冒泡排序的直观方法：

示例

假设我们有一个包含五个不同数据元素的未排序数组。

给定数组：(5, 3, 4, 2, 1)

我们现在将使用冒泡排序以升序排列这些数组数据元素。

第一次迭代

(5, 3, 4, 2, 1) -> (3, 5, 4, 2, 1)

冒泡排序比较前两个数据元素，并进行交换，因为 5 大于 3 (5 > 3)。

(3, 5, 4, 2, 1) -> (3, 4, 5, 2, 1)，因为 5 大于 4 (5 > 4) 而交换。
(3, 4, 5, 2, 1) -> (3, 4, 2, 5, 1)，因为 5 大于 2 (5 > 2) 而交换。
(3, 5, 2, 5, 1) -> (3, 4, 2, 1, 5)，因为 5 大于 1 (5 > 1) 而交换。

第二次迭代

(3, 4, 2, 1, 5) -> (3, 2, 4, 1, 5)，因为 4 大于 2 (4 > 2) 而交换。
(3, 2, 4, 1, 5) -> (3, 2, 1, 4, 5)，因为 4 大于 1 (4 > 1) 而交换。

第三次迭代

(3, 2, 1, 4, 5) -> (2, 3, 1, 4, 5)，因为 3 大于 2 (3 > 2) 而交换。
(2, 3, 1, 4, 5) -> (2, 1, 3, 4, 5)，因为 3 大于 1 (3 > 1) 而交换。

第四次迭代

(2, 1, 3, 4, 5) -> (1, 2, 3, 4, 5)，因为 2 大于 1 (2 > 1) 而交换。
算法需要一次完整的无交换遍历来检查是否已排序。
(1, 2, 3, 4, 5) -> (1, 2, 3, 4, 5)
因此，我们已成功将数组按升序排序。

现在我们已经理解了冒泡排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的冒泡排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to perform Bubble Sort
void BubbleSort(int arr[], int size){
    
    // defining some iterables
    int i, j;

    // using a nested for-loop
    for (i = 0; i < size - 1; i++)
        for (j = 0; j < size - i - 1; j++)
            // comparing the values of adjacent elements and swaping them if the first one is greater than the other 
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

// main function
int main(){
    // defining and initializing an array
    int arr[] = {5, 3, 4, 2, 1};

    // calculating the size of array
    int size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the BubbleSort() function to sort the given array in ascending order
    BubbleSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
5 3 4 2 1 
Sorted Array : 
1 2 3 4 5

说明

在上面的代码片段中，我们包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 BubbleSort() 的 void 函数，它接受两个参数——数组名及其大小。在此函数内部，我们定义了两个可迭代对象 i 和 j。我们使用嵌套的 for 循环遍历数组中的每个元素，比较当前元素的值与下一个元素的值，如果当前元素较大，则交换它们的位置。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名 arr 及其大小来调用 BubbleSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (5, 3, 4, 2, 1)）被排序为升序（1, 2, 3, 4, 5）。

冒泡排序的性能分析

现在让我们观察冒泡排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察冒泡排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n²)
最佳情况：Ω(n)

辅助空间复杂度: O(1)

冒泡排序的一些应用

以下是冒泡排序的一些应用：

冒泡排序用于向计算机科学学生介绍排序算法的基本概念。
冒泡排序在计算机图形学中很受欢迎，用于检测几乎排序数组中的小错误（例如，仅交换两个数据元素）。

选择排序

选择排序是一种排序算法，其中给定的数组被分成两个子数组：

第一个子数组将包含列表的已排序部分。
第二个子数组将包含列表的未排序部分。

最初，已排序的段为空，而未排序的段包含整个列表。在每次迭代中，我们将从未排序的子数组中获取最小的数据元素，并将其推到已排序的子数组的末尾。因此，我们可以成功构建我们的已排序数组。

让我们通过一个例子来理解选择排序的直观方法：

示例

假设我们有一个包含五个不同数据元素的未排序数组。

给定数组：(26, 23, 28, 16, 18)

我们现在将使用选择排序以升序排列这些数组数据元素。

对于 i = 0，我们将选择数组中的最小元素，即 16，并将其移动到未排序数组的开头 i = 0，同时保持其余数据元素的相对顺序。

因此，我们将得到以下数组：

(16, 26, 23, 28, 18)

同样，对于 i = 1，我们将再次选择数组中的下一个最小元素，即 18，并将其移动到未排序数组的开头 i = 1，同时保持其余数据元素的相对顺序。

因此，我们现在将得到以下数组：

(16, 18, 26, 23, 28)

同样，对于 i = 2，我们将再次选择数组中的下一个最小元素，即 23，并将其移动到未排序数组的开头 i = 2，同时保持其余数据元素的相对顺序。

因此，我们现在将得到以下数组：

(16, 18, 23, 26, 28)

同样，对于 i = 3，我们将再次选择数组中的下一个最小元素，即 26，并将其移动到未排序数组的开头 i = 3，同时保持其余数据元素的相对顺序。

因此，我们现在将得到以下数组：

(16, 18, 23, 26, 28)

同样，对于 i = 4，我们将再次选择数组中的下一个最小元素，即 28，并将其移动到未排序数组的开头 i = 4。

因此，最终的已排序数组将是：

(16, 18, 23, 26, 28)

现在我们已经理解了选择排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的选择排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to perform Selection Sort
void SelectionSort(int arr[], int size){
    
    // defining iterables and variables
    int i, j, curr;
    
    // using the nested for-loop
    for (i = 0; i < size - 1; i++){
        // initializing the curr variable as i
        curr = i;
        for (j = i + 1; j < size; j++)
            // if array's element at index j is lower than element at the curr variable, then set the curr to j 
            if (arr[j] < arr[curr])
                curr = j;
        // calling the swap() function to swap the lowest value with the current index i curr
        swap(arr[curr], arr[i]);
    }
}

// main function
int main(){
    // defining and initializing an array
    int arr[] = {25, 23, 28, 16, 18};
    
    // calculating the size of array
    int size = sizeof(arr)/sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the SelectionSort() function to sort the given array in ascending order    
    SelectionSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
25 23 28 16 18
Sorted Array :
16 18 23 25 28

说明

在上面的代码片段中，我们包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 SelectionSort() 的 void 函数，它接受两个参数——数组名及其大小。在此函数内部，我们定义了两个可迭代对象 i 和 j 以及一个名为 curr 的变量。我们使用了嵌套的 for 循环来遍历数组中的每个元素。在第一个 for 循环内部，我们将 curr 变量初始化为索引 i 的当前值。在第二个 for 循环内部，我们将索引 j 处的元素值与 curr 位置处的元素进行比较，如果较大，则调用 swap() 函数交换它们的位置。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名 arr 及其大小来调用 SelectionSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (25, 23, 28, 16, 18)）被排序为升序（16, 18, 23, 25, 28）。

选择排序的性能分析

现在让我们观察选择排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察选择排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n²)
最佳情况：Ω(n²)

辅助空间复杂度: O(1)

选择排序的一些应用

以下是选择排序的一些应用：

选择排序用于小数据列表，因为此排序算法的时间复杂度为 O(n²)，因此对于大列表来说效率不高。
选择排序也用于内存空间有限的情况，因为它在整个排序过程中交换的次数最少。

插入排序

插入排序是一种排序算法，其中给定的数组被分成已排序和未排序的段。在每次迭代中，我们需要在已排序的子序列中找到要插入的数据元素的最佳位置，然后将其插入，同时将剩余的数据元素向右移动。

让我们通过一个例子来理解插入排序的直观方法：

示例

假设我们有一个包含五个不同数据元素的未排序数组。

给定数组：(26, 23, 28, 16, 18)

我们现在将使用插入排序以升序排列这些数组数据元素。

对于 i = 1，因为 23 比 26 小，我们将 25 移到右边，并将 23 这个数据元素插入到 25 之前。

因此，我们将得到以下数组：

(23, 26, 28, 16, 18)

对于 i = 2，因为 A[0, ..., i-1] 中的所有元素都小于 27，所以它将保持其位置不变。

因此，我们的数组将保持不变。

(23, 26, 28, 16, 18)

对于 i = 3，我们将值 16 的数据元素移动到开头，将从 23 到 28 的其余数据元素向右移动一个位置。

因此，我们将得到以下数组：

(16, 23, 26, 28, 18)

对于 i = 4，我们将值 18 的数据元素移动到 16 之后，并将从 23 到 28 的数据元素向右移动一个位置。

因此，最终的已排序数组将是：

(16, 18, 23, 26, 28)

现在我们已经理解了插入排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的插入排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to perform Insertion Sort
void InsertionSort(int arr[], int size){

    // defining some iterables and variables
    int i, temp, j;

    // using the for-loop
    for (i = 1; i < size; i++){
        // initializing the temp variable as value at index i from array
        temp = arr[i];
        // initializing another iterable value
        j = i - 1;
        // using the while loop for j >= 0 and arr[j] > temp
        while (j >= 0 && arr[j] > temp){
            // swapping the elements
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = temp;
    }
}

// main function
int main(){
    // defining and initializing an array
    int arr[] = {25, 23, 28, 16, 18};

    // calculating the size of array
    int size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the InsertionSort() function to sort the given array in ascending order    
    InsertionSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
25 23 28 16 18
Sorted Array :
16 18 23 25 28

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 InsertionSort() 的 void 函数，它接受两个参数——数组名及其大小。在此函数内部，我们定义了两个可迭代对象 i 和 j 以及一个名为 temp 的变量。我们使用 for 循环遍历数组中的每个元素。在此之内，我们将 temp 变量初始化为 arr[i] 的值，并将可迭代对象 j 初始化为 i 的前一个值。然后我们使用 while 循环来比较索引 j 处的元素值和 temp，如果较大则交换它们的位置。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名 arr 及其大小来调用 InsertionSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (25, 23, 28, 16, 18)）被排序为升序（16, 18, 23, 25, 28）。

插入排序的性能分析

现在让我们观察插入排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察插入排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n²)
最佳情况：Ω(n)

辅助空间复杂度: O(1)

插入排序的一些应用

以下是插入排序的一些应用：

插入排序是一种稳定的排序算法，当列表几乎排序时，它工作速度很快。
插入排序在对小数据列表（例如，35 个数据元素）进行排序时非常有效和高效。

快速排序

快速排序是一种基于分而治之方法的排序算法。此排序技术的直观概念是，它选择一个数据元素作为给定数据元素数组的枢轴，然后围绕该枢轴数据元素对数组进行分区。因此，它递归地调用自身，然后对两个子数组进行分区。

让我们通过一个例子来理解快速排序的直观方法：

示例

快速排序算法包含的逻辑步骤如下：

枢轴选择：我们首先选择一个数据元素作为枢轴（在本例中，我们选择了最后一个数据元素作为枢轴）。
分区：然后我们将数组分区，使得所有小于枢轴的数据元素都位于左子数组中，而严格大于枢轴元素的数据元素则存储在右子数组中。
递归调用 Quicksort：我们将再次为上面创建的两个子数组调用 Quicksort 函数，并重复该过程，直到获得最终的排序数组。

现在我们已经理解了快速排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的快速排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to partition_array the array around the pivot_element
int partition_array(int arr[], int start, int end){
    // defining and initializing the pivot element
    int pivot_element = arr[end];
    // defining and initializing an iterable
    int i = (start - 1);
    // using the for-loop to iterate through the array and swap the elements for sorting
    for (int j = start; j <= end - 1; j++){
        if (arr[j] < pivot_element){
            i++; swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[end]);
    return (i + 1);
}
 
/*
arr[] --> array to be sorted,
start --> Starting index,
end --> Ending index
*/

// defining a function to perform Quick Sort
void QuickSort(int arr[], int start, int end){
    if (start < end){
        // middle is partitioning index, arr[p] is now at right place
        int middle = partition_array(arr, start, end);
        // sorting data elements seperately before partition and after partition
        QuickSort(arr, start, middle - 1);
        QuickSort(arr, middle + 1, end);
    }
}

// main function
int main(){
    // defining and initializing an array
    int arr[] = {25, 23, 28, 16, 18};

    // calculating the size of array
    int size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the QuickSort() function to sort the given array in ascending order    
    QuickSort(arr, 0, size - 1);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
25 23 28 16 18
Sorted Array :
16 18 23 25 28

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 partition_array() 的函数来围绕枢轴元素对数组进行分区。此函数接受三个参数——数组名、起始点和终点。在此函数内部，我们初始化了枢轴元素的值并定义了一个可迭代对象进行迭代。然后我们使用 for 循环遍历元素并交换元素以对数组进行排序。然后我们定义了一个名为 QuickSort() 的 void 函数，它接受三个参数——数组名、起始点和终点。在此函数内部，我们比较起始点是否小于终点，并调用 partition_array() 函数。然后我们递归调用 QuickSort() 函数。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名以及起始点和终点来调用 QuickSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (25, 23, 28, 16, 18)）被排序为升序（16, 18, 23, 25, 28）。

快速排序的性能分析

现在让我们观察快速排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察快速排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n * log n)
最佳情况：Ω(n * log n)

辅助空间复杂度：O(log n)

快速排序的一些应用

以下是快速排序的一些应用：

快速排序对于适合内存的数据集可能更有效。
快速排序适用于数组，因为它是一种原地排序算法，不需要任何额外的存储空间。

合并排序

归并排序是另一种基于分而治之方法的排序算法。在每次迭代中，归并排序将输入数组分成两个相等的子数组，递归地为这两个子数组调用自身，最后合并两个已排序的半部分。

让我们通过一个例子来理解归并排序的直观方法：

现在我们已经理解了归并排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的归并排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to merge the sub-arrays
void merge_subarray(long arr[], long start, long middle, long end){
    // defining some variables
    long num1 = middle - start + 1;
    long num2 = end - middle;
    
    // defining some arrays
    long Left[num1], Right[num2];
    // inserting elements to the arrays using the for-loops
    for (long i = 0; i < num1; i++)
        Left[i] = arr[start + i];
    for (long j = 0; j < num2; j++)
        Right[j] = arr[middle + 1 + j];
    
    // defining some iterables
    long i = 0, j = 0;
    long k = start;

    // using the while loop and swapping the elements to sort the array 
    while (i < num1 and j < num2) {
        if (Left[i] <= Right[j]) {
            arr[k] = Left[i]; i++;
        }
        else {
            arr[k] = Right[j]; j++;
        }
        k++;
    }
    while (i < num1) {
        arr[k] = Left[i]; i++; k++;
    }
    while (j < num2) {
        arr[k] = Right[j]; j++; k++;
    }
}

// defining a function to perform Merge Sort
void MergeSort(long arr[], long start, long end){
    // returning, if the starting point is greater than and equal to the ending point
    if(start >= end)
        return;
    // defining and initializing a variable
    long middle = start + (end - start) / 2;

    // recursively calling the MergeSort() function
    MergeSort(arr, start, middle);
    MergeSort(arr, middle + 1, end);

    // calling the merge_subarray() function
    merge_subarray(arr, start, middle, end);
}

// main function
int main(){
    // defining and initializing an array
    long arr[] = {25, 23, 28, 16, 18};

    // calculating the size of array
    long size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the MergeSort() function to sort the given array in ascending order    
    MergeSort(arr, 0, size - 1);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
25 23 28 16 18
Sorted Array :
16 18 23 25 28

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 merge_subarray() 的函数，它接受多个参数，如数组名、起始点、中间点和终点。在此函数内部，我们定义了一些变量以及一些数组。然后我们使用 for 循环将元素插入到这些数组中。然后我们定义并初始化了一些可迭代对象，并使用 while 循环通过交换它们的元素来对子数组进行排序。然后我们定义了另一个名为 MergeSort() 的函数，它接受三个参数——数组名、起始点和终点。在此函数内部，

我们使用 if 条件语句来检查起始点是否大于或等于终点，并添加一个 return 语句来中断循环。然后我们定义并初始化了一个名为 middle 的变量，并递归调用 MergeSort() 函数来对数组进行排序。然后我们调用 merge_subarray() 函数。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名以及起始点和终点来调用 MergeSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (25, 23, 28, 16, 18)）被排序为升序（16, 18, 23, 25, 28）。

归并排序的性能分析

现在让我们观察归并排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察归并排序的空间复杂度。

时间复杂度

最坏情况：O(n * log n)
平均情况：Θ(n * log n)
最佳情况：O(n * log n)

辅助空间复杂度: O(n)

归并排序的一些应用

以下是归并排序的一些应用：

在链表等数据结构的情况下，归并排序速度很快。
归并排序广泛用于外部排序，其中与顺序访问相比，随机访问的成本可能相当高。

计数排序

计数排序是一种有趣的排序算法，主要侧重于特定范围内唯一数据元素的频率（类似于哈希）。

此排序算法通过计算具有不同键值的数据元素的数量，然后在估算每个唯一数据元素在未排序序列中的位置后构建一个排序数组。

计数排序与我们之前讨论的算法不同，因为它不涉及输入数据元素之间的比较。

让我们通过一个例子来理解计数排序的直观方法：

示例

为简单起见，假设我们有一个从 0 到 3 的数据元素组成的未排序数组。

给定数组：(1, 0, 3, 1, 3, 1)
首先，我们将构建一个频率数组来存储每个唯一元素的计数。

索引	0	1	2	3
Counter	1	3	0	2

我们现在将修改计数器数组，形成一个前缀和数组，如下所示：

索引	0	1	2	3
Counter	1	4	4	6

修改后的计数器数组指示了输出序列中每个对象的位置。
输出输入序列中的每个对象，然后将其计数减 1。通过将每个数据元素向右移动 1 位来构建以下数组。

索引	0	1	2	3
Counter	0	1	4	4

现在处理输入数据：1, 0, 3, 1, 3, 1

根据最终数组（第 3 步），2 的位置是 4。因此，我们将数据 2 放在输出序列的索引 4 处，同时将其计数减 1，以便将下一个数据 2 放在比当前索引小 1 的索引 3 处。
通过将此方法扩展到完整的输入数组，我们将得到如下所示的排序序列：

最终数组：(0, 1, 1, 1, 3, 3)

现在我们已经理解了计数排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的计数排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining the function to get the maximum value from the array
long getMaximum(long arr[], long size) {
    // defining and initializing an initial maximum value from the array
    long maximum = arr[1];
    // using the for-loop to iterate through the array
    for(long i = 2; i <= size; i++) {
        // updating the value in the maximum variable with the maximum value from the array
        if(arr[i] > maximum)
            maximum = arr[i];
    }
    // returning the final maximum value
    return maximum;
}

// defining the function to perform Counting Sort
void CountingSort(long *arr, long size) {
    // defining an array for output
    long output_array[size + 1];
    
    // calling the getMaximum() function and storing the returned value in a variable
    long maximum = getMaximum(arr, size);
    
    // defining an array to store count
    long counter[maximum + 1];
    
    // using the for-loop to set the initial values of the elements of the counter array to 0 
    for(long i = 0; i <= maximum; i++)
        counter[i] = 0;

    // using the for-loop to update the values in the counter array for the given array
    for(long i = 1; i <= size; i++)
        counter[arr[i]]++;
    
    // using the for-loop to modify the counter array to form a prefix sum array
    for(long i = 1; i <= maximum; i++)
        counter[i] += counter[i - 1];
    
    // using the for-loop to generate the output from the input sequence followed by decreasing its count by 1    
    for(long i = size; i >= 1; i--) {
        output_array[counter[arr[i]]] = arr[i];
        counter[arr[i]] -= 1;
    }

    // using the for-loop to update the values in the original array using output array
    for(long i = 1; i <= size; i++) {
        arr[i] = output_array[i];
    }
}

// main function
int main(){
    // defining and initializing an array
    long arr[] = {0, 1, 0, 3, 1, 3, 1};

    // calculating the size of array
    long size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 1; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the CountingSort() function to sort the given array in ascending order    
    CountingSort(arr, size - 1);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 1; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
1 0 3 1 3 1
Sorted Array :
0 1 1 1 3 3

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 getMaximum() 的函数，它接受两个参数——数组名及其大小，以便从数组中检索最大值。在此函数内部，我们首先初始化一个变量并赋予初始最大值。然后我们遍历数组，将变量值更新为最终的最大值，并返回它。然后我们定义了另一个名为 CountingSort() 的函数，它接受两个参数——数组名及其大小。在此函数内部，我们定义了一个用于存储输出的数组，调用了 getMaximum() 函数，以及一个计数器数组。然后我们使用 for 循环将计数器数组的初始值设置为 0。我们再次使用 for 循环来更新给定数组在计数器数组中的值。然后我们再次使用 for 循环遍历计数器数组，修改其值以形成前缀和数组。我们再次使用 for 循环从输入序列生成输出，然后将其计数减 1。最后，我们使用 for 循环遍历数组的数据元素，并根据输出数组修改它们的值。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名以及起始点和终点来调用 CountingSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (1, 0, 3, 1, 3, 1)）被排序为升序（0, 1, 1, 1, 3, 3）。

计数排序的性能分析

现在让我们观察计数排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察计数排序的空间复杂度。

时间复杂度

最坏情况：O(n + k)
平均情况：Θ(n + k)
最佳情况：Ω(n + k)

辅助空间复杂度：O(k)，其中 k 是数组中唯一元素的计数。

计数排序的一些应用

以下是计数排序的一些应用：

计数排序是一种非常高效的排序算法，用于对可数对象（如有限整数）进行排序。
计数排序也用于线性复杂度排序。

基数排序

正如我们已经讨论过的，计数排序之所以与众不同，是因为它不像归并排序或冒泡排序那样是基于比较的排序算法。因此，我们可以将它的时间复杂度降低到线性时间。

然而，当输入数组的数据元素范围从 1 到 n² 时，这种排序技术就会失败，导致其时间复杂度增加到 O(n²)。

基数排序的基本概念是扩展计数排序的功能，以便在输入数组的数据元素范围从 1 到 n² 时获得更好的时间复杂度。

让我们简要了解一下这种排序算法：

算法

对于每个数字 i，其中 i 从数字的最低有效位到最高有效位变化，我们将使用计数排序算法对输入数组进行第 i 位排序。

注意：我们使用了计数排序，因为它是一种稳定的排序算法。

让我们通过一个例子来理解基数排序的直观方法：

示例

假设我们有一个包含六个不同数据元素的未排序数组。

给定数组：(54, 90, 151, 37, 634, 232)

我们现在将使用基数排序以升序排列这些数组数据元素。

对于 i = 0，我们将对数组中每个数据元素的第零位（在本例中是数字的最低有效位）应用计数排序。

排序后，我们将得到以下数组：

(90, 151, 232, 54, 634, 37)

对于 i = 1，我们将根据数据元素的第一个有效位（从右边开始）对数组数据元素进行排序。

排序后，我们将得到以下数组：

(232, 634, 37, 151, 54, 90)

对于 i = 2，数组的数据元素将根据它们第二个有效位（从右边开始）进行排序。

排序后，我们将得到以下数组：

(37, 54, 90, 151, 232, 634)，这也是最终的排序数组。

现在我们已经理解了基数排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的基数排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining the function to get the maximum value from the array
long getMaximum(long arr[], long size) {
    // defining and initializing a initial maximum value from the array
    long maximum = arr[1];
    
    // using the for-loop to iterate through the array
    for(long i = 2; i <= size; i++) {
        // updating the value in the maximum variable with the maximum value from the array
        if(arr[i] > maximum)
            maximum = arr[i];
    }
    
    // returning the final maximum value
    return maximum;
}

// defining the function to perform Counting Sort
void CountingSort(long arr[], long size, long bit){
    // defining an array to store result
    long result[size];
    
    // defining the counter array
    long counter[10] = {0};
    
    // defining an iterable
    long i;

    // using the for-loops to sort the array
    for (i = 0; i < size; i++)
        counter[(arr[i] / bit) % 10]++;
    
    for (i = 1; i < 10; i++)
        counter[i] += counter[i - 1];
    
    for (i = size - 1; i >= 0; i--) {
        result[counter[(arr[i] / bit) % 10] - 1] = arr[i];
        counter[(arr[i] / bit) % 10]--;
    }
    
    for (i = 0; i < size; i++)
        arr[i] = result[i];
}

// defining the function to perform Radix Sort
void RadixSort(long arr[], long size){
    // calling the getMaximum() function
    long max = getMaximum(arr, size);
    
    // using the for-loop and calling the CountingSort() function
    for (long i = 1; max / i > 0; i *= 10)
        CountingSort(arr, size, i);
}

// main function
int main(){
    // defining and initializing an array
    long arr[] = { 54, 90, 151, 37, 634, 232 };

    // calculating the size of array
    long size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the RadixSort() function to sort the given array in ascending order    
    RadixSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
54 90 151 37 634 232
Sorted Array :
37 54 90 151 232 634

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 getMaximum() 的函数，它接受两个参数——数组名及其大小，以便从数组中检索最大值。在此函数内部，我们首先初始化一个变量并赋予初始最大值。然后我们遍历数组，将变量值更新为最终的最大值，并返回它。然后我们定义了另一个名为 CountingSort() 的函数，它接受多个参数，如数组名、其大小和有效位。在此函数内部，我们定义了一个用于存储输出的数组，一个计数器数组和一个可迭代对象。然后我们使用多个 for 循环根据选定的有效位对数组进行排序。然后我们定义了一个名为 RadixSort() 的函数，它接受两个参数——数组名及其大小。在此函数内部，我们调用了 getMaximum() 函数，并使用 for 循环调用 CountingSort() 函数。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名及其大小来调用 RadixSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (54, 90, 151, 37, 634, 232)）被排序为升序（37, 54, 90, 151, 232, 634）。

基数排序的性能分析

现在让我们观察基数排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察基数排序的空间复杂度。

时间复杂度

最坏情况：O(n * k)
平均情况：Θ(n * k)
最佳情况：Ω(n * k)

辅助空间复杂度：O(n + k)，其中 n 是数组中的元素数量，k 是数组中唯一元素的计数。

基数排序的一些应用

以下是基数排序的一些应用：

基数排序用于并行计算等应用。
基数排序也用于 DC3 算法（Kärkkäinen-Sanders-Burkhardt）来构建后缀数组。

桶排序

桶排序是一种基于比较的排序算法，它将数组的数据元素递归地分成多个桶，然后使用不同的排序算法对这些桶进行单独排序。最后，将已排序的桶重新组合以生成排序后的数组。

让我们借助伪代码来理解桶排序算法：

我们可以通过假设已经创建了一个包含多个“桶”（列表）的数组来进一步探索桶排序算法的工作原理。数据元素现在根据它们的属性从未排序的数组插入到这些“桶”中。这些桶最终使用插入排序算法（如前所述）进行单独排序。

以下是桶排序算法的伪代码：

伪代码

Start
    for i = 0 to size - 1
        inserting array[i] into the bucket indexed (size * array[i])
    done
    for i = 0 to size - 1
        sorting bucket[i] using insertion sort
    done
    for i = 0 to size - 1
        combining elements of bucket[i] and inserting in array in sorted order
    done
End

现在我们已经理解了桶排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的桶排序实现

// including the required header file and defining a constant
# include <bits/stdc++.h>
# define pushback push_back

// using the standard namespace
using namespace std;

// defining a function to perform BucketSort
void BucketSort(float arr[], int size){
    // defining a vector to represent bucket
    vector<float> bucket[size];

    // using the for-loop to iterate through the array and pushing the elements from the array to bucket
    for (int i = 0; i < size; i++) {
        int b_size = size * arr[i];
        bucket[b_size].pushback(arr[i]);
    }

    // using the for-loop to sort the elements of the bucket using the insertion sort
    for (int i = 0; i < size; i++)
        sort(bucket[i].begin(), bucket[i].end());

    // defining and initializing an initial value to represent cursor position
    int position = 0;
    // using the for-loop to iterate through the elements of the buckets and inserting them into the array
    for (int i = 0; i < size; i++)
        for (int j = 0; j < bucket[i].size(); j++)
            arr[position++] = bucket[i][j];
}

// main function
int main(){
    // defining and initializing an array
    float arr[]= { 0.454, 0.583, 0.4471, 0.6146, 0.563, 0.9412 };

    // calculating the size of array
    long size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the BucketSort() function to sort the given array in ascending order    
    BucketSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
0.454 0.583 0.4471 0.6146 0.563 0.9412
Sorted Array :
0.4471 0.454 0.563 0.583 0.6146 0.9412

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件，定义了一个常量来执行 push back 并使用了标准命名空间。然后我们定义了一个名为 BucketSort() 的函数，它接受两个参数——数组名及其大小，以便对数组的元素进行排序。在此函数内部，我们首先使用 vector 定义了一个数组来表示桶。然后我们使用 for 循环遍历数组，将数据元素从数组推送到桶中。然后我们再次使用 for 循环遍历桶中的元素，并使用插入排序以升序对它们进行排序。然后我们再次使用 for 循环将排序后的元素从桶更新回数组。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名及其大小来调用 BucketSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (0.454 0.583 0.4471 0.6146 0.563 0.9412)）被排序为升序（0.4471 0.454 0.563 0.583 0.6146 0.9412）。

桶排序的性能分析

现在让我们观察桶排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察桶排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n + k)
最佳情况：Ω(n + k)

辅助空间复杂度：O(n)，其中 n 是数组中的元素数量，k 是数组中唯一元素的计数。

桶排序的一些应用

以下是桶排序的一些应用：

当输入均匀分布在某个范围内时，使用桶排序。
桶排序也用于浮点数。

梳排序

梳排序（Comb Sort）非常有趣。它是冒泡排序算法的一个改进版本。正如有些人之前观察到的，冒泡排序算法在每次迭代中都会比较相邻的数据元素。

然而，梳排序算法通过一个大的间隔值来比较和交换数据元素。间隔值在每次迭代中按 1.3 的因子缩小，直到间隔值达到 1，此时它停止执行。

该收缩因子通过试错法（在测试了超过 20 万个随机数组的梳排序算法后）计算得出为 1.3。

让我们通过一个例子来理解梳排序的直观方法：

示例

假设我们有一个包含十个不同数据元素的未排序数组。

给定数组：(100, 90, 80, 70, 60, 50, 40, 30, 20, 10)

初始间隔值：10

收缩后，我们将得到以下间隔值：10/1.3 = 7

因此，元素将按以下格式排序：

100, 90, 80, 70, 60, 50, 40, 30, 20, 10

30, 90, 80, 70, 60, 50, 40, 100, 20, 10

30, 20, 80, 70, 60, 50, 40, 100, 90, 10

30, 20, 10, 70, 60, 50, 40, 100, 90, 80

再次收缩后，我们将得到以下间隔值：7/1.3 = 5

由于间隔值为 5 时，数据元素已按升序排列。因此，数组将保持不变，如下所示：

30, 20, 10, 70, 60, 50, 40, 100, 90, 80

再次收缩后，我们将得到以下间隔值：5/1.3 = 3

因此，元素将按以下格式排序：

30, 20, 10, 70, 60, 50, 40, 100, 90, 80

30, 20, 10, 40, 60, 50, 70, 100, 90, 80

再次收缩后，我们将得到以下间隔值：3/1.3 = 2

因此，元素将按以下格式排序：

30, 20, 10, 40, 60, 50, 70, 100, 90, 80

10, 20, 30, 40, 60, 50, 70, 100, 90, 80

10, 20, 30, 40, 60, 50, 70, 80, 90, 100

再次收缩后，我们将得到以下间隔值：2/1.3 = 1

因此，元素将按以下格式排序：

10, 20, 30, 40, 60, 50, 70, 80, 90, 100

10, 20, 30, 40, 50, 60, 70, 80, 90, 100

现在我们的数组已经排序，不再需要交换。

现在我们已经理解了梳排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的梳排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to perform Comb Sort
void CombSort(long *arr, long size) {
    // defining the gap value and initializing it as the size of the array
    long gapValue = size;
    // defining a flag
    bool flag = true;

    // using the while loop to iterate until the gapValue is equal to 1 
    while (gapValue != 1 || flag == true) {
        // updating the gap value
        gapValue = (gapValue) / 1.3;
        // if gap value is less than 1, setting the gap value to 1
        if (gapValue < 1) gapValue = 1;
        // updating the flag value
        flag = false;
        // using the for-loop to iterate through the array and sort them according to the gap value
        for (long i = 0; i < size - gapValue; i++) {
            // swapping the elements in the array
            if (arr[i] > arr[i + gapValue]) {
                swap(arr[i], arr[i + gapValue]);
                flag = true;
            }
        }
    }
}

// main function
int main(){
    // defining and initializing an array
    long arr[] = {100, 90, 80, 70, 60, 50, 40, 30, 20, 10};

    // calculating the size of array
    long size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    Cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the CombSort() function to sort the given array in ascending order
    CombSort(arr, size);

    // printing the sorted array for the users
    Cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
100 90 80 70 60 50 40 30 20 10
Sorted Array :
10 20 30 40 50 60 70 80 90 100

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 CombSort() 的函数，它接受两个参数——数组名及其大小，以便对数组的元素进行排序。在此函数内部，我们首先定义了指定间隔值的变量，并将一个布尔标志设置为 True。然后我们使用 while 循环，该循环将一直迭代直到间隔值减小到 1 并且标志变为 False。我们通过将当前间隔除以 1.3 来更新间隔值。我们还使用了 if 条件语句来检查间隔值是否小于 1 并将其设置为 1。我们还更新了标志的值，并使用 for 循环遍历数组中的数据元素并根据它们的间隔值进行排序。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名及其大小来调用 CombSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (100, 90, 80, 70, 60, 50, 40, 30, 20, 10)）被排序为升序（10, 20, 30, 40, 50, 60, 70, 80, 90, 100）。

梳排序的性能分析

现在让我们观察梳排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察梳排序的空间复杂度。

时间复杂度

最坏情况：O(n²)
平均情况：Θ(n²/2^p)，其中 p 是增量数
最佳情况：Ω(n log n)

辅助空间复杂度: O(1)

梳排序的一些应用

以下是梳排序的一些应用：

梳排序通过较大的间隔值消除了列表中末尾的小值。
梳排序是冒泡排序的一个重要改进版本。

希尔排序

希尔排序算法是插入排序算法的一个改进版本，在该版本中，我们采用递减分区来对数据进行排序。

在每次传递中，对于数组的每次传递，间隔大小都减半。因此，对于每次迭代，数组的数据元素都会与计算出的间隔值进行比较（如果需要）并交换。

让我们借助伪代码来理解希尔排序算法：

以下是希尔排序算法的伪代码：

伪代码

Begin
    for gapValue = N / 2, where gapValue > 0 and gapValue updates to gapValue / 2:
        for i = gapValue to N - 1:
            for j = j - gapValue to 0, decrease by gapValue value:
                if arr[j + gapValue] >= arr[j]
                    break
                else
                    swap arr[j + gapValue] with arr[j]
            done
        done
    done
End

希尔排序的概念允许交换相距很远的数据元素。在希尔排序中，我们将数组 N 排序为较大的 N 值。

然后我们不断减小 N 的值，直到它变为 1。如果数组中每 N 个元素的子数组都已排序，则该数组称为 N 排序。

对于每次迭代，间隔大小将是 floor(N/2)。

现在我们已经理解了希尔排序的直观概念，是时候考虑它在 C++ 编程语言中的标准实现了。

C++ 中的希尔排序实现

// including the required header file
# include <bits/stdc++.h>

// using the standard namespace
using namespace std;

// defining a function to perform Shell Sort
void ShellSort(int arr[], int size){
    // using the nested for-loop to iterate through the array on the basis of the gap values
    for (int gapValue = size / 2; gapValue > 0; gapValue /= 2){
        for (int i = gapValue; i < size; i ++ ){
            // defining and intializing a variable as the ith element of the array
            int num = arr[i];
            // defining an iterable
            int j;
            // using the for-loop to sort the array in ascending order
            for (j = i; j >= gapValue && arr[j - gapValue] > num; j -= gapValue)
                arr[j] = arr[j - gapValue];
            arr[j] = num;
        }
    }
}

// main function
int main(){
    // defining and initializing an array
    int arr[] = {100, 90, 80, 70, 60, 50, 40, 30, 20, 10};

    // calculating the size of array
    int size = sizeof(arr) / sizeof(arr[0]);

    // printing the unsorted array for the users
    cout << "Unsorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    // calling the ShellSort() function to sort the given array in ascending order
    ShellSort(arr, size);

    // printing the sorted array for the users
    cout << "Sorted Array : \n";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

输出

Unsorted Array : 
100 90 80 70 60 50 40 30 20 10
Sorted Array :
10 20 30 40 50 60 70 80 90 100

说明

我们在上面的代码片段中包含了 'bits/stdc++.h' 头文件并使用了标准命名空间。然后我们定义了一个名为 ShellSort() 的函数，它接受两个参数——数组名及其大小，以便对数组的元素进行排序。在此函数内部，我们使用了嵌套的 for 循环来根据间隔值遍历数组的元素。然后我们定义并初始化了变量作为当前数组元素以及一个可迭代对象。然后我们再次使用 for 循环以升序对数组进行排序。

现在在 main 函数内部，我们定义并初始化了一个未排序的数组 arr。然后我们计算了它的大小。我们还为用户打印了未排序数组的元素。然后我们通过传递数组名及其大小来调用 ShellSort() 函数。最后，我们为用户打印了排序后的数组元素。

结果，给定的数组（即 (100, 90, 80, 70, 60, 50, 40, 30, 20, 10)）被排序为升序（10, 20, 30, 40, 50, 60, 70, 80, 90, 100）。

希尔排序的性能分析

现在让我们观察希尔排序在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将观察希尔排序的空间复杂度。

时间复杂度

最坏情况：O(n (log n)²)
平均情况：Θ(n (log n)²)
最佳情况：Ω(n log n)

辅助空间复杂度: O(1)

希尔排序的一些应用

以下是希尔排序的一些应用：

当接近的数据元素相距较远时，插入排序性能不佳。希尔排序有助于减小接近数据元素之间的距离。
当递归超过限制时，也使用希尔排序。

排序算法的完整性能分析图

以下是我们之前研究过的不同排序算法以及一些其他算法的完整性能分析图：

复杂度比较表

序号。	算法	时间复杂度			空间复杂度
		最佳	平均数	最坏	最坏
1	快速排序	Ω(n log n)	Θ(n log n)	O(n²)	O(n log n)
2	合并排序	Ω(n log n)	Θ(n log n)	O(n log n)	O(n)
3	Timsort	Ω(n)	Θ(n log n)	O(n log n)	O(n)
4	堆排序	Ω(n log n)	Θ(n log n)	O(n log n)	O(1)
5	冒泡排序	Ω(n)	Θ(n²)	O(n²)	O(1)
6	插入排序	Ω(n)	Θ(n²)	O(n²)	O(1)
7	选择排序	Ω(n²)	Θ(n²)	O(n²)	O(1)
8	树排序	Ω(n log n)	Θ(n log n)	O(n²)	O(n)
9	希尔排序	Ω(n log n)	Θ(n (log n)²)	O(n (log n)²)	O(1)
10	桶排序	Ω(n + k)	Θ(n + k)	O(n²)	O(n)
11	基数排序	Ω(nk)	Θ(nk)	O(nk)	O(n + k)
12	计数排序	Ω(n + k)	Θ(n + k)	O(n + k)	O(k)
13	Cubesort	Ω(n)	Θ(n log n)	O(n log n)	O(n)
14	梳排序	Ω(n log n)	Θ(n²/2^p)	O(n²)	O(n log n)

什么是最好的排序算法？

从上表可以看出，快速排序在最佳和平均情况下的时间复杂度为 O(n log n)，在最坏情况下的时间复杂度为 O(n²)。

然而，由于快速排序在大多数输入的平均情况下占有优势，因此该算法通常被认为是“最快”的排序算法。

最简单的排序算法是什么？

冒泡排序被广泛认为是所有排序算法中最简单的。该算法的基本概念是扫描整个数组，比较相邻的数据元素并交换它们（如果需要），直到数组被排序。

对于几乎排序的列表，会优先选择哪种排序算法？

当我们必须对几乎排序的列表进行排序时，插入排序算法是明确的选择，特别是因为其时间复杂度在这种样本上从惊人的 O(n²) 降低到 O(n)。

与插入排序相比，归并排序和快速排序等算法通常不适合几乎排序的数组。

下一个主题扩展欧几里得算法

← 上一个下一个 →

排序算法：最慢到最快

什么是排序算法？

理解排序算法的重要性

理解数据结构中的排序类型

一些常见的排序算法

冒泡排序

C++ 中的冒泡排序实现

选择排序

C++ 中的选择排序实现

选择排序的性能分析

插入排序

C++ 中的插入排序实现

快速排序

C++ 中的快速排序实现

合并排序

C++ 中的归并排序实现

计数排序

C++ 中的计数排序实现

基数排序

注意：我们使用了计数排序，因为它是一种稳定的排序算法。

C++ 中的基数排序实现

桶排序

C++ 中的桶排序实现

梳排序

C++ 中的梳排序实现

希尔排序

C++ 中的希尔排序实现

排序算法的完整性能分析图

复杂度比较表

什么是最好的排序算法？

最简单的排序算法是什么？

对于几乎排序的列表，会优先选择哪种排序算法？

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

DAA 教程

渐进分析

复发

排序分析

分而治之

排序

下界理论

线性时间排序

哈希

二叉搜索树

红黑树

动态规划

贪婪算法

回溯

最小生成树

最短路径

所有对最短路径

最大流

排序网络

复杂度理论

近似算法

字符串匹配

面试题

其他

排序算法：最慢到最快

什么是排序算法？

理解排序算法的重要性

理解数据结构中的排序类型

一些常见的排序算法

冒泡排序

C++ 中的冒泡排序实现

选择排序

C++ 中的选择排序实现

选择排序的性能分析

插入排序

C++ 中的插入排序实现

快速排序

C++ 中的快速排序实现

合并排序

C++ 中的归并排序实现

计数排序

C++ 中的计数排序实现

基数排序

注意：我们使用了计数排序，因为它是一种稳定的排序算法。

C++ 中的基数排序实现

桶排序

C++ 中的桶排序实现

梳排序

C++ 中的梳排序实现

希尔排序

C++ 中的希尔排序实现

排序算法的完整性能分析图

复杂度比较表

什么是最好的排序算法？

最简单的排序算法是什么？

对于几乎排序的列表，会优先选择哪种排序算法？

相关帖子

二分搜索算法

扩展欧几里德算法

Kruskals 算法的时间复杂度