• 数据结构与算法-常用排序算法

    承接Qt/C++软件开发项目，高质量交付，灵活沟通，长期维护支持。需求所寻，技术正适，共创完美，欢迎私信联系！

    一、常用排序说明

            当涉及排序算法时，理解每个算法的工作原理、时间复杂度和空间复杂度是至关重要的。下面对常用排序算法进行详细说明：     

            1、冒泡排序（Bubble Sort）：

            工作原理：比较相邻的元素并交换，每一轮将最大（或最小）的元素移动到数组末尾（或开头）。

            时间复杂度：平均情况和最坏情况均为 O(n^2)。

            空间复杂度：O(1)，原地排序，不需要额外空间。

            适用场景：适用于小规模数据集，对稳定性要求高的场景，或者作为教学和理解排序算法的基础。

            2、选择排序（Selection Sort）：

            工作原理：每一轮选择最小（或最大）的元素放在已排序序列的末尾（或开头）。

            时间复杂度：平均情况和最坏情况均为 O(n^2)。

            空间复杂度：O(1)，原地排序，不需要额外空间。

            适用场景：适用于小规模数据集，简单易实现，但性能较差。对稳定性要求不高的场景。

            3、插入排序（Insertion Sort）：

            工作原理：将未排序序列中的元素逐个插入到已排序序列中的适当位置。

            时间复杂度：平均情况和最坏情况均为 O(n^2)。

            空间复杂度：O(1)，原地排序，不需要额外空间。

            适用场景：适用于小规模或基本有序的数据集，对稳定性要求高的场景，用于改进其他排序算法的一部分。

            4、希尔排序（Shell Sort）：

            工作原理：是插入排序的改进版，通过比较距离较远的元素进行交换，最终使数据基本有序，然后再使用插入排序。

            时间复杂度：取决于增量序列的选择，在实践中介于 O(n log^2 n) 和 O(n^2) 之间。

            空间复杂度：O(1)，原地排序，不需要额外空间。

            适用场景：适用于小规模或基本有序的数据集，对稳定性要求高的场景，用于改进其他排序算法的一部分。

            5、归并排序（Merge Sort）：

            工作原理：采用分治法，将数组分成两半，分别排序，然后合并两个有序数组。

            时间复杂度：平均情况和最坏情况均为 O(n log n)。

            空间复杂度：O(n)，需要额外的内存来存储临时数组。

            适用场景：适用于小规模或基本有序的数据集，对稳定性要求高的场景，用于改进其他排序算法的一部分。

            6、快速排序（Quick Sort）：

            工作原理：采用分治法，选取一个基准值，将小于基准值的放在左边，大于基准值的放在右边，然后递归地对左右两部分进行排序。

            时间复杂度：平均情况为 O(n log n)，最坏情况为 O(n^2)。

            空间复杂度：取决于实现方式，通常为 O(log n)。

            适用场景：适用于大规模数据集，性能优秀且易于实现。常用于实际生产环境中的排序需求。

            7、堆排序（Heap Sort）：

            工作原理：利用堆的性质（最大堆或最小堆），将待排序数组构建成堆，然后每次取出堆顶元素，重新调整堆，直至完成排序。

            时间复杂度：平均情况和最坏情况均为 O(n log n)。

            空间复杂度：O(1)，原地排序，不需要额外空间。

            适用场景：适用于大规模数据集，性能稳定且不受输入数据分布情况影响。适合内存受限的情况下进行排序。

            8、计数排序（Counting Sort）：

            工作原理：统计待排序数组中每个元素出现的次数，然后根据元素的值将其放到正确的位置。

            时间复杂度：平均情况和最坏情况均为 O(n + k)，其中 k 是非负整数的最大值。

            空间复杂度：O(n + k)，需要额外空间来存储计数数组和输出数组。

            适用场景：适用于输入数据的范围相对较小，但数量较大的情况下，可以快速排序。对数字的频率进行统计。

            9、桶排序（Bucket Sort）：

            工作原理：将待排序数据分到有限数量的桶里，每个桶再分别进行排序，最后合并所有桶的结果。

            时间复杂度：平均情况为 O(n + k)，最坏情况为 O(n^2)。

            空间复杂度：O(n + k)，需要额外空间来存储计数数组和输出数组。

            适用场景：适用于数据均匀分布在一个范围内的情况下，将数据分到多个桶中，然后对每个桶单独进行排序。

            10、基数排序（Radix Sort）：

            工作原理：根据数字位进行排序，先按个位排序，再按十位排序，依次类推，直到最高位排序完成。

            时间复杂度：平均情况和最坏情况均为 O(d * (n + k))，其中 d 是数字位数，k 是基数（如 10 进制中的 10）。

            空间复杂度：O(n + k)，需要额外空间来存储计数数组和输出数组。

            适用场景：适用于对数字进行排序的场景通过按位进行排序，每次排序根据数字位数来确定，效率高且稳定。

    二、时间复杂度说明

            O(1)：常数时间复杂度。无论输入规模的大小如何，算法的执行时间都是固定的。例如，访问数组中的一个元素，计算数组的长度等。无论数组中有多少个元素，时间都是恒定的。

            O(log n)：对数时间复杂度。算法的执行时间与输入规模的对数成正比。典型的例子是二分查找算法。在一个有序数组中查找一个元素时，每次都将搜索空间减半，因此时间复杂度为对数级别。

            O(n)：线性时间复杂度。算法的执行时间与输入规模成正比，呈线性增长。例如，遍历数组或链表中的所有元素。如果一个数组有 n 个元素，那么对每个元素的访问将花费 O(n) 的时间。

            O(n log n)：线性对数时间复杂度。典型的例子是快速排序和归并排序等基于比较的排序算法。这些算法的执行时间与输入规模的对数乘以线性成正比。

            O(n^2)：平方时间复杂度。算法的执行时间与输入规模的平方成正比。例如，嵌套循环的排序算法（如冒泡排序、选择排序），每个元素都需要与其他元素比较。

            O(2^n)：指数时间复杂度。通常出现在递归算法中，每次递归都会产生指数级别的子问题。例如，求解所有可能的子集或排列问题。

            O(n!)：阶乘时间复杂度。通常出现在全排列等组合问题中，需要计算所有可能的排列。例如，求解 n 个元素的所有排列可能性的问题。

    三、空间复杂度说明

            O(1)：常数空间复杂度。算法的额外空间使用是一个固定的常数，与输入规模无关。例如，原地排序算法，如冒泡排序、选择排序，不需要额外的空间。

            O(log n)：对数空间复杂度。算法的额外空间使用与输入规模的对数成正比。例如，递归算法每次调用都会消耗对数级别的栈空间。二分搜索的递归版本就是一个典型的例子。

            O(n)：线性空间复杂度。算法的额外空间使用与输入规模成正比，呈线性增长。例如，需要一个与输入规模相同大小的数组来存储数据，或者使用一个辅助数组来进行排序。

            O(n^2)：平方空间复杂度。算法的额外空间使用与输入规模的平方成正比。例如，使用一个二维数组来存储所有可能的组合情况。

            O(2^n)：指数空间复杂度。算法的额外空间使用与输入规模的指数成正比。通常出现在递归的指数增长情况下，例如，子集生成问题。

            O(n!)：阶乘空间复杂度。算法的额外空间使用与输入规模的阶乘成正比。通常出现在全排列等组合问题中，需要存储所有可能的排列。

    四、代码样例

    (一) 冒泡排序（Bubble Sort）

    1. #include 
    2. using namespace std;
    3.  
    4. void bubbleSort(int arr[], int n) {
    5.     for (int i = 0; i < n-1; i++) {
    6.         for (int j = 0; j < n-i-1; j++) {
    7.             if (arr[j] > arr[j+1]) {
    8.                 swap(arr[j], arr[j+1]);
    9.             }
    10.         }
    11.     }
    12. }
    13.  
    14. int main() {
    15.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
    16.     int n = sizeof(arr) / sizeof(arr[0]);
    17.     bubbleSort(arr, n);
    18.     cout << "Sorted array: ";
    19.     for (int i = 0; i < n; i++) {
    20.         cout << arr[i] << " ";
    21.     }
    22.     cout << endl;
    23.     return 0;
    24. }

    (二) 选择排序（Selection Sort）

    1. #include 
    2. using namespace std;
    3.  
    4. void selectionSort(int arr[], int n) {
    5.     for (int i = 0; i < n-1; i++) {
    6.         int min_idx = i;
    7.         for (int j = i+1; j < n; j++) {
    8.             if (arr[j] < arr[min_idx]) {
    9.                 min_idx = j;
    10.             }
    11.         }
    12.         swap(arr[i], arr[min_idx]);
    13.     }
    14. }
    15.  
    16. int main() {
    17.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
    18.     int n = sizeof(arr) / sizeof(arr[0]);
    19.     selectionSort(arr, n);
    20.     cout << "Sorted array: ";
    21.     for (int i = 0; i < n; i++) {
    22.         cout << arr[i] << " ";
    23.     }
    24.     cout << endl;
    25.     return 0;
    26. }

    (三) 插入排序（Insertion Sort）

    1. #include 
    2. using namespace std;
    3.  
    4. void insertionSort(int arr[], int n) {
    5.     for (int i = 1; i < n; i++) {
    6.         int key = arr[i];
    7.         int j = i - 1;
    8.         while (j >= 0 && arr[j] > key) {
    9.             arr[j+1] = arr[j];
    10.             j--;
    11.         }
    12.         arr[j+1] = key;
    13.     }
    14. }
    15.  
    16. int main() {
    17.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
    18.     int n = sizeof(arr) / sizeof(arr[0]);
    19.     insertionSort(arr, n);
    20.     cout << "Sorted array: ";
    21.     for (int i = 0; i < n; i++) {
    22.         cout << arr[i] << " ";
    23.     }
    24.     cout << endl;
    25.     return 0;
    26. }

    (四) 希尔排序（Shell Sort）

    1. #include 
    2. using namespace std;
    3.  
    4. void shellSort(int arr[], int n) {
    5.     for (int gap = n/2; gap > 0; gap /= 2) {
    6.         for (int i = gap; i < n; i++) {
    7.             int temp = arr[i];
    8.             int j;
    9.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
    10.                 arr[j] = arr[j - gap];
    11.             }
    12.             arr[j] = temp;
    13.         }
    14.     }
    15. }
    16.  
    17. int main() {
    18.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
    19.     int n = sizeof(arr) / sizeof(arr[0]);
    20.     shellSort(arr, n);
    21.     cout << "Sorted array: ";
    22.     for (int i = 0; i < n; i++) {
    23.         cout << arr[i] << " ";
    24.     }
    25.     cout << endl;
    26.     return 0;
    27. }

    (五) 归并排序（Merge Sort）

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void merge(vector<int>& arr, int l, int m, int r) {
    6.     int n1 = m - l + 1;
    7.     int n2 = r - m;
    8.  
    9.     vector<int> L(n1), R(n2);
    10.  
    11.     for (int i = 0; i < n1; i++)
    12.         L[i] = arr[l + i];
    13.     for (int j = 0; j < n2; j++)
    14.         R[j] = arr[m + 1 + j];
    15.  
    16.     int i = 0, j = 0, k = l;
    17.     while (i < n1 && j < n2) {
    18.         if (L[i] <= R[j]) {
    19.             arr[k] = L[i];
    20.             i++;
    21.         } else {
    22.             arr[k] = R[j];
    23.             j++;
    24.         }
    25.         k++;
    26.     }
    27.  
    28.     while (i < n1) {
    29.         arr[k] = L[i];
    30.         i++;
    31.         k++;
    32.     }
    33.  
    34.     while (j < n2) {
    35.         arr[k] = R[j];
    36.         j++;
    37.         k++;
    38.     }
    39. }
    40.  
    41. void mergeSort(vector<int>& arr, int l, int r) {
    42.     if (l < r) {
    43.         int m = l + (r - l) / 2;
    44.  
    45.         mergeSort(arr, l, m);
    46.         mergeSort(arr, m + 1, r);
    47.  
    48.         merge(arr, l, m, r);
    49.     }
    50. }
    51.  
    52. int main() {
    53.     vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    54.     int n = arr.size();
    55.  
    56.     mergeSort(arr, 0, n - 1);
    57.  
    58.     cout << "Sorted array: ";
    59.     for (int i = 0; i < n; i++)
    60.         cout << arr[i] << " ";
    61.     cout << endl;
    62.  
    63.     return 0;
    64. }

    (六) 快速排序（Quick Sort）

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int partition(vector<int>& arr, int low, int high) {
    6.     int pivot = arr[high];
    7.     int i = low - 1;
    8.  
    9.     for (int j = low; j < high; j++) {
    10.         if (arr[j] < pivot) {
    11.             i++;
    12.             swap(arr[i], arr[j]);
    13.         }
    14.     }
    15.     swap(arr[i + 1], arr[high]);
    16.     return i + 1;
    17. }
    18.  
    19. void quickSort(vector<int>& arr, int low, int high) {
    20.     if (low < high) {
    21.         int pi = partition(arr, low, high);
    22.  
    23.         quickSort(arr, low, pi - 1);
    24.         quickSort(arr, pi + 1, high);
    25.     }
    26. }
    27.  
    28. int main() {
    29.     vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    30.     int n = arr.size();
    31.  
    32.     quickSort(arr, 0, n - 1);
    33.  
    34.     cout << "Sorted array: ";
    35.     for (int i = 0; i < n; i++)
    36.         cout << arr[i] << " ";
    37.     cout << endl;
    38.  
    39.     return 0;
    40. }

    (七) 堆排序（Heap Sort）

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void heapify(vector<int>& arr, int n, int i) {
    6.     int largest = i;
    7.     int l = 2 * i + 1;
    8.     int r = 2 * i + 2;
    9.  
    10.     if (l < n && arr[l] > arr[largest])
    11.         largest = l;
    12.  
    13.     if (r < n && arr[r] > arr[largest])
    14.         largest = r;
    15.  
    16.     if (largest != i) {
    17.         swap(arr[i], arr[largest]);
    18.         heapify(arr, n, largest);
    19.     }
    20. }
    21.  
    22. void heapSort(vector<int>& arr) {
    23.     int n = arr.size();
    24.  
    25.     for (int i = n / 2 - 1; i >= 0; i--)
    26.         heapify(arr, n, i);
    27.  
    28.     for (int i = n - 1; i > 0; i--) {
    29.         swap(arr[0], arr[i]);
    30.         heapify(arr, i, 0);
    31.     }
    32. }
    33.  
    34. int main() {
    35.     vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    36.     int n = arr.size();
    37.  
    38.     heapSort(arr);
    39.  
    40.     cout << "Sorted array: ";
    41.     for (int i = 0; i < n; i++)
    42.         cout << arr[i] << " ";
    43.     cout << endl;
    44.  
    45.     return 0;
    46. }

    (八) 计数排序（Counting Sort）

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void countingSort(vector<int>& arr) {
    6.     int n = arr.size();
    7.     int maxVal = *max_element(arr.begin(), arr.end());
    8.     int minVal = *min_element(arr.begin(), arr.end());
    9.     int range = maxVal - minVal + 1;
    10.  
    11.     vector<int> count(range), output(n);
    12.     for (int i = 0; i < n; i++)
    13.         count[arr[i] - minVal]++;
    14.  
    15.     for (int i = 1; i < range; i++)
    16.         count[i] += count[i - 1];
    17.  
    18.     for (int i = n - 1; i >= 0; i--) {
    19.         output[count[arr[i] - minVal] - 1] = arr[i];
    20.         count[arr[i] - minVal]--;
    21.     }
    22.  
    23.     for (int i = 0; i < n; i++)
    24.         arr[i] = output[i];
    25. }
    26.  
    27. int main() {
    28.     vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    29.     countingSort(arr);
    30.  
    31.     cout << "Sorted array: ";
    32.     for (int i = 0; i < arr.size(); i++)
    33.         cout << arr[i] << " ";
    34.     cout << endl;
    35.  
    36.     return 0;
    37. }

    (九) 桶排序（Bucket Sort）

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. void bucketSort(vector<float>& arr) {
    7.     int n = arr.size();
    8.     vectorfloat>> buckets(n);
    9.  
    10.     for (int i = 0; i < n; i++) {
    11.         int bucketIndex = n * arr[i];
    12.         buckets[bucketIndex].push_back(arr[i]);
    13.     }
    14.  
    15.     for (int i = 0; i < n; i++)
    16.         sort(buckets[i].begin(), buckets[i].end());
    17.  
    18.     int index = 0;
    19.     for (int i = 0; i < n; i++) {
    20.         for (float num : buckets[i]) {
    21.             arr[index++] = num;
    22.         }
    23.     }
    24. }
    25.  
    26. int main() {
    27.     vector<float> arr = {0.64, 0.34, 0.25, 0.12, 0.22, 0.11, 0.90};
    28.     bucketSort(arr);
    29.  
    30.     cout << "Sorted array: ";
    31.     for (int i = 0; i < arr.size(); i++)
    32.         cout << arr[i] << " ";
    33.     cout << endl;
    34.  
    35.     return 0;
    36. }

    (十) 基数排序（Radix Sort）

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. int getMax(vector<int>& arr) {
    7.     int maxVal = arr[0];
    8.     for (int i = 1; i < arr.size(); i++) {
    9.         if (arr[i] > maxVal)
    10.             maxVal = arr[i];
    11.     }
    12.     return maxVal;
    13. }
    14.  
    15. void countingSort(vector<int>& arr, int exp) {
    16.     int n = arr.size();
    17.     vector<int> output(n), count(10);
    18.  
    19.     for (int i = 0; i < n; i++)
    20.         count[(arr[i] / exp) % 10]++;
    21.  
    22.     for (int i = 1; i < 10; i++)
    23.         count[i] += count[i - 1];
    24.  
    25.     for (int i = n - 1; i >= 0; i--) {
    26.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
    27.         count[(arr[i] / exp) % 10]--;
    28.     }
    29.  
    30.     for (int i = 0; i < n; i++)
    31.         arr[i] = output[i];
    32. }
    33.  
    34. void radixSort(vector<int>& arr) {
    35.     int maxVal = getMax(arr);
    36.  
    37.     for (int exp = 1; maxVal / exp > 0; exp *= 10)
    38.         countingSort(arr, exp);
    39. }
    40.  
    41. int main() {
    42.     vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    43.     radixSort(arr);
    44.  
    45.     cout << "Sorted array: ";
    46.     for (int i = 0; i < arr.size(); i++)
    47.         cout << arr[i] << " ";
    48.     cout << endl;
    49.  
    50.     return 0;
    51. }
  • 相关阅读:
    北京十大知名律师事务所最新排名（2022前十公布）
    Excel 语法
    PDF格式分析（六十九）——注释字典
    HTML5期末考核大作业 基于HTML+CSS+JavaScript沪上美食(9页)
    勒索病毒最新变种.halo勒索病毒来袭，如何恢复受感染的数据？
    Linux命令(107)之basename
    在 Flutter 中自定义画笔 Painter
    react 18新特性 了解一下
    linux使用命令反弹到 msf
    oauth2的知识点
  • 原文地址：https://blog.csdn.net/evesmith520/article/details/136249911