数据结构中排序算法

介绍

排序算法是计算机科学中的一类算法，用于对元素序列进行排序，以便按照某种特定的顺序（如升序或降序）组织数据。这些算法在软件开发和数据处理中扮演着至关重要的角色，因为它们可以提高搜索效率、优化数据结构的访问和处理等。

类型时间复杂度空间复杂度
冒泡排序（Bubble Sort）O(n^2)，其中n是数列的长度O(1)
选择排序（Selection Sort）O(n^2)O(1)
插入排序（Insertion Sort）O(n^2)O(1)
归并排序（Merge Sort）O(n log n)O(n)
快速排序（Quick Sort）平均O(n log n)，最坏O(n^2)O(log n)
堆排序（Heap Sort）O(n log n)O(1)
希尔排序（Shell Sort）取决于间隔序列的选择，最好可以达到O(n log^2 n)O(1)
计数排序（Counting Sort）O(n + k)O(k)
桶排序（Bucket Sort）O(n + k)O(n + k)
基数排序（Radix Sort）时间复杂度：O(nk)O(n + k)
  • 此外还有鸡尾酒排序（Cocktail Sort，双向冒泡排序）、图书馆排序（Library Sort，Cocktail Sort的变种）、鸽巢排序（Pigeonhole Sort）、啤酒排序（Beer Sort）、循环排序（Cyclic Sort）、位排序（Bitonic Sort）、梳排序（Comb Sort）、TimSort（一种混合排序算法，Python的内置排序算法之一）、Bogo Sort（一种通过随机打乱输入数据来排序的非常低效算法）、Stooge Sort（通过递归地将数组分成三部分来排序的算法）、Panama Sort（通过移除数组中最小或最大的元素来排序的算法）、Cocktail Shaker Sort（双向选择排序）、Tree Sort（利用二叉搜索树进行排序的算法）、Cycle Sort（通过循环交换来排序的算法）、Gnome Sort（通过比较和移动来排序的算法，类似于插入排序）等等。

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）是一种简单的排序算法，它的原理基于重复遍历待排序的数列，通过比较相邻的元素并在必要时交换它们的位置来实现排序。冒泡排序的基本思想是：在每次遍历过程中，将最大的元素“冒泡”到数列的末尾，这个过程类似于气泡从水底升到水面。以下是

冒泡排序的详细步骤：

  • 比较相邻元素：从数列的开始位置，比较第一个和第二个元素，如果第一个元素大于第二个元素（升序排序的情况），则交换它们的位置。继续比较第二个和第三个元素，以此类推，直到到达数列的末尾。

  • 冒泡至末尾：在第一次遍历结束时，最大的元素会被放置在数列的最后一个位置。接下来的遍历将忽略这个已经排序好的元素，因为它已经在正确的位置上了。

  • 重复过程：重复上述比较和交换的过程，但每次遍历时都减少一个元素的比较（因为最后一个元素已经是最大的，不需要再比较），这样进行直到整个数列都被排序。

  • 优化：在某些情况下，可以对冒泡排序进行优化。例如，如果在一次遍历中没有发生任何交换，这意味着数列已经是有序的，因此可以提前结束排序过程。

c++冒泡排序示例

#include <iostream>
using namespace std;

// 交换两个元素的值
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    bool swapped;
    // 外层循环控制遍历次数
    for (int i = 0; i < n - 1; i++) {
        swapped = false; // 标记变量，用于优化冒泡排序
        // 内层循环负责进行相邻元素的比较和交换
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true; // 发生交换，标记为true
            }
        }
        // 如果在这一轮遍历中没有发生交换，说明数组已经有序，可以提前结束排序
        if (!swapped) {
            break;
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组: ";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "排序后的数组: ";
    printArray(arr, n);
    
    return 0;
}

这段代码首先定义了一个swap函数，用于交换两个整数的值。bubbleSort函数实现了冒泡排序算法，它接受一个整数数组和数组的长度作为参数。在排序过程中，使用了一个布尔变量swapped来检查内层循环中是否发生了元素交换，如果在某次遍历中没有发生交换，说明数组已经排序完成，可以提前退出循环。

printArray函数用于打印数组中的元素。在main函数中，定义了一个待排序的数组，并调用bubbleSort函数进行排序，然后打印排序前后的数组。

选择排序（Selection Sort）

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序主要有两种实现方式：直接选择排序和树状选择排序。

以下是选择排序的基本步骤：

  • 寻找最小元素：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
  • 重复寻找：再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

选择排序c++示例

#include <iostream>
using namespace std;

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    // 外层循环控制遍历次数
    for (i = 0; i < n - 1; i++) {
        // 找到从i到n-1中最小元素的索引
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 将找到的最小元素与第i位置的元素交换
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组: ";
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    cout << "排序后的数组: ";
    printArray(arr, n);
    
    return 0;
}

在这个示例中，selectionSort函数实现了选择排序算法。它首先在未排序的序列中找到最小元素的索引，然后将其与序列中当前位置的元素交换。这个过程会一直重复，直到整个数组被排序。

插入排序（Insertion Sort）

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是将数组分为已排序部分和未排序部分，然后逐个将未排序部分的元素插入到已排序部分的适当位置。插入排序在实际应用中非常高效，尤其是对于小型数据集或基本有序的数据集。

以下是插入排序的基本步骤：

  • 构建有序序列：将数组的第一个元素视为已排序部分，其余元素视为未排序部分。

  • 扫描未排序部分：从数组的第二个元素开始，扫描未排序部分的每个元素。

  • 插入元素：将当前元素与已排序部分的元素从后往前比较，找到合适的位置插入当前元素，保持已排序部分的有序性。

  • 重复过程：重复步骤2和3，直到所有元素都被插入到已排序部分，完成排序。

插入排序c++示例

#include <iostream>
using namespace std;

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    
    // 从第二个元素开始，进行插入排序
    for (i = 1; i < n; i++) {
        key = arr[i]; // 当前需要插入的元素
        j = i - 1;
        
        // 将大于key的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        // 插入key到正确的位置
        arr[j + 1] = key;
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组: ";
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    cout << "排序后的数组: ";
    printArray(arr, n);
    
    return 0;
}

在这个示例中，insertionSort函数实现了插入排序算法。它从数组的第二个元素开始，将每个元素与已排序部分的元素进行比较，并找到合适的位置插入。这个过程一直重复，直到整个数组都被排序。

归并排序（Merge Sort）

归并排序（Merge Sort）是一种分治算法，它通过递归地将数组分成两半，然后对这两半分别进行排序，最后将排序好的两半合并成一个有序的数组。归并排序的核心在于合并两个有序数组的过程，这个过程是稳定的，即相同元素在合并后保持原来的相对顺序。

以下是归并排序的基本步骤：

  • 分解：将数组递归地分成两半，直到每个子数组只包含一个元素。由于每个元素本身可以视为一个有序数组，所以当子数组的大小为1时，递归结束。

  • 合并：将两个有序的子数组合并成一个更大的有序数组。合并过程是逐个比较两个子数组的元素，将较小的元素放入新的数组中，直到所有元素都被合并。

  • 递归合并：重复合并过程，直到整个数组被合并成一个有序的数组。

归并排序c++示例

#include <iostream>
using namespace std;

// 合并两个有序数组的函数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左半部分的大小
    int n2 = right - mid;    // 右半部分的大小

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组回原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // 找到中间位置，将数组分为两半
        int mid = left + (right - left) / 2;

        // 递归地对左右两半进行排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组: ";
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    cout << "排序后的数组: ";
    printArray(arr, n);
    
    return 0;
}

在这个示例中，mergeSort函数实现了归并排序算法。它首先找到数组的中间位置，递归地对左右两半进行排序，然后调用merge函数将排序好的两半合并成一个有序数组。

快速排序（Quick Sort）

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的关键在于选择一个元素作为“基准”（pivot），并围绕这个基准进行分区（partition）操作，使得小于基准的元素都在其左侧，大于基准的元素都在其右侧。

以下是快速排序的基本步骤：

  • 选择基准：从数组中选择一个元素作为基准。选择方式有多种，如选择第一个元素、最后一个元素、中间元素或随机一个元素。

  • 分区操作：重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相等的数可以到任一边）。在这个分区退出之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。

  • 递归排序：递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。

快速排序c++示例

#include <iostream>
using namespace std;

// 交换两个元素的值
void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

// 分区函数，选择左端点作为基准
int partition(int arr[], int low, int high) {
    int pivot = arr[low]; // 选择基准
    int i = low + 1;
    int j = high;

    while (true) {
        // 找到比基准大的元素
        while (i <= j && arr[i] < pivot) {
            i++;
        }
        // 找到比基准小的元素
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i > j) {
            break;
        }
        // 交换两个元素的位置
        swap(arr[i], arr[j]);
    }
    // 将基准元素放到正确的位置
    swap(arr[low], arr[j]);
    return j;
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]现在在正确的位置
        int pi = partition(arr, low, high);

        // 分别递归地对基准前后的子数组进行快速排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

在这个示例中，quickSort函数实现了快速排序算法。它首先调用partition函数来选择基准并进行分区操作，然后递归地对基准前后的子数组进行快速排序。

堆排序（Heap Sort）

堆排序（Heap Sort）是一种基于比较的排序算法，它使用二叉堆（特殊的完全二叉树）的数据结构来对元素进行排序。堆排序的特点是无论升序还是降序排序，都可以在O(n log n)的时间复杂度内完成。堆排序的工作原理可以分为两个主要步骤：建立堆和堆排序。

以下是堆排序的基本步骤：

  • 建立堆：将无序的输入数组构造成一个最大堆（或最小堆，取决于排序的类型）。最大堆的性质是每个节点的值都大于或等于其子节点的值，而最小堆则相反。

  • 堆排序：将堆顶元素（最大或最小元素）与堆的最后一个元素交换，这样最大或最小元素就放置到了数组的末尾。减少堆的大小（排除已经排序好的最后一个元素），并对新的堆顶元素进行“堆化”（heapify），以恢复堆的性质。
    重复上述过程，直到堆的大小减少到1，这时数组已经完全排序。

堆排序c++示例

#include <iostream>
using namespace std;

void buildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始，向上调整每个节点
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapifyMax(arr, n, i);
    }
}

void heapifyMax(int arr[], int n, int i) {
    int largest = i; // 初始化为当前节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于当前最大值，则更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大值，则更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是当前节点，交换它们，并继续调整交换后的子树
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapifyMax(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n); // 建立最大堆
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大元素与末尾元素交换
        swap(arr[0], arr[i]);
        // 堆的大小减少1，调整剩余的堆
        heapifyMax(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

在这个示例中，heapSort函数实现了堆排序算法。首先调用buildMaxHeap函数建立最大堆，然后通过不断地将堆顶元素与末尾元素交换并调整堆来完成排序。

希尔排序（Shell Sort）

希尔排序（Shell Sort）是插入排序的一种改进版本，也被称为“缩小增量排序”。它通过引入一个增量（gap）来允许交换更远距离的元素，从而可以快速减少大量的小范围无序情况。希尔排序的核心思想是将相距一定间隔的一组元素进行插入排序，随着间隔逐渐减小，整个数组趋于有序，最后当间隔为1时，进行最后一次插入排序，此时数组已经基本有序，所以需要的移动次数会很少。

以下是希尔排序的基本步骤：

选择增量序列：增量序列的选择对希尔排序的性能有很大影响。常见的增量序列有希尔原始序列（N/2，N/4，…，1），Hibbard增量序列（1, 3, 7, …, 2^k - 1），Knuth序列（1, 4, 13, …, (3^k - 1)/2）等。

分组插入排序：按照当前增量将数组分为若干子序列，对每个子序列进行插入排序。

减小增量，重复排序：减小增量值，并重复上述排序过程，直到增量为1，进行最后一次插入排序。

完成排序：当增量减至1时，整个数组将进行一次标准的插入排序，此时数组已经基本有序，所以排序会很快完成。

希尔排序c++示例

#include <iostream>
using namespace std;

// 插入排序的辅助函数
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 希尔排序函数
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 从第gap个元素开始，逐个对其所在组进行直接插入排序
        for (int i = gap; i < n; i++) {
            insertionSort(arr, 1); // 这里只对一个元素进行插入排序
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

在这个示例中，shellSort函数实现了希尔排序算法。它首先计算出每次排序的增量gap，然后对每个子序列进行插入排序。随着增量gap的减小，数组逐渐变得接近有序，最后当gap为1时，整个数组将进行一次插入排序，完成排序。


http://www.niftyadmin.cn/n/5450219.html

相关文章

蔚来JAVA面试（收集）

蔚来JAVA面试（收集）

先叠加&#xff0c;这个是自己找的答案不一定对&#xff0c;只是给我参考看看而已。 一、项目 这个没有&#xff0c;根据实际项目情况来。蔚来比较喜欢拷打项目&#xff0c;所以要对项目非常熟悉&#xff08;慌&#xff09; 二、JAVA基础 2.1 Java中的IO模型有用到过吗&#…
阅读更多...
C++ ：静态绑定与动态绑定

C++ ：静态绑定与动态绑定

看下面这段代码 #include<iostream> using namespace std; struct A{int num10;virtual void fun(){cout<<"a:"<<num<<endl;} }; struct B:public A{B(){num20;}virtual void fun(){cout<<"b:"<<num<<endl;} }…
阅读更多...
C++语言学习（三）—— 文件操作

C++语言学习（三）—— 文件操作

目录 一、文件操作 1.1 打开文件 1.2 关闭文件 1.3 读取文件 1.4 写入文件 1.5 文件指针 1.6 文件状态 1.7 其他文件操作 二、文件操作函数 2.1 打开文件函数 2.2 关闭文件函数 2.3 写入文件函数 2.4 读取文件函数 2.5 读取一行函数 2.6 获取文件大小函数 2.7 …
阅读更多...
不愧是淘天，全方位八股拷打

不愧是淘天，全方位八股拷打

恭喜发现宝藏&#xff01;搜索公众号【TechGuide】回复公司名&#xff0c;解锁更多新鲜好文和互联网大厂的笔经面经&#xff0c;目前已更新至美团、微软… 作者TechGuide【全网同名】 基本情况 投递岗位&#xff1a;后台开发 投递部门&#xff1a;阿里淘天 招聘类型&#xf…
阅读更多...
什么是浏览器指纹识别？Maskfog指纹浏览器有用吗？

什么是浏览器指纹识别？Maskfog指纹浏览器有用吗？

浏览器指纹识别是好是坏&#xff1f;这现在确实是一个有争议的话题。83%的消费者经常或偶尔会根据浏览历史记录看到广告。其实这就是利用了浏览器指纹技术。 如果您想了解浏览器指纹识别是什么&#xff0c;那就看下去&#xff01; 一、什么是浏览器指纹识别 浏览器指纹是指无…
阅读更多...
Elasticsearch 的 scroll API

Elasticsearch 的 scroll API

对于大量数据&#xff0c;可以使用 Elasticsearch 的 scroll API 来分批次地读取数据&#xff0c;以避免一次性读取所有数据造成的内存负担。这段代码使用滚动查询&#xff08;scroll&#xff09;来分批次地读取数据。首先&#xff0c;它发送初始的搜索请求&#xff0c;并获取第…
阅读更多...
Windows如何搭建 ElasticSearch 集群

Windows如何搭建 ElasticSearch 集群

单机 & 集群 单台 Elasticsearch 服务器提供服务&#xff0c;往往都有最大的负载能力&#xff0c;超过这个阈值&#xff0c;服务器 性能就会大大降低甚至不可用&#xff0c;所以生产环境中&#xff0c;一般都是运行在指定服务器集群中。 除了负载能力&#xff0c;单点服务器…
阅读更多...
QT深入解析数控机床或激光切割机的nc文件包括读取与数据处理技巧

QT深入解析数控机床或激光切割机的nc文件包括读取与数据处理技巧

QT深入解析数控机床或激光切割机的nc文件包括读取与数据处理技巧 代码功能说明：代码运行过程代码功能说明： 这个代码是用来读取一个名为 “C:/QCY/qcy.nc” 的文件，这个文件中包含了一系列数据，每行数据可能包含 X、Y、Z 坐标值。这些坐标值可以代表某种路径或轨迹。 代码…
阅读更多...
最新文章

Copyright @ 2022~2023