介绍

在计算机科学中，排序算法是基本工具，可以让我们按数字或字母顺序排列元素。它们是将无序材料排列成逻辑序列的基本指令。我们将在这篇文章中进入排序算法的世界，并研究它们的重要性、指导原则和分类。我们将首先理解排序的基本原理以及处理大量数据集时效率的重要性。从那里，我们将看看不同的排序策略，从简单的气泡排序到有效的快速排序。到本文完成时，您将牢牢了解这些算法的运作方式，以及如何使用它们来增强计算机程序的功能。

排序算法

排序算法用于根据元素上的比较运算符重新排列给定的数组或元素列表。比较运算符用于确定各自数据结构中元素的新顺序。

在计算机科学中，排序算法就像一个配方，帮助我们按特定顺序组织事物列表。最常见的订单要么从最小到最大，要么从最大到最小。高效地整理东西很重要，因为它可以帮助其他计算机程序更快地工作，更好地完成工作。

想象一下，你在一个列表中混合了一堆数字或单词，你想把它们按顺序排列。排序算法可帮助您自动做到这一点。它采用混乱的列表，并为您提供一个新的列表，其中元素从最小到最大或从最大到最小排列，具体取决于您想要什么。

当排序算法工作时，它遵循两条重要规则：新列表中的元素按特定顺序排列。例如，如果您正在对数字进行排序，每个数字都大于或等于列表中的前一个数字。如果您正在对单词进行排序，它们将按字母顺序排列。新列表与原始列表具有相同的项目，但它们被重新排列。没有添加或删除任何项目。

为了快速整理东西，最好以允许我们轻松跳转到任何项目的方式存储原始列表，而不是逐个浏览它们。这就像有一本带有索引的食谱书，所以你可以快速找到你需要的页面，而不是翻阅每一页，直到你找到你要找的东西。

因此，排序算法是按特定顺序组织事物列表（如数字或单词）的一种方式。它有助于其他程序更快地运行，并且当原始列表以允许轻松访问任何项目的方式存储时，它效果最佳。

分类计算复杂性：排序算法可以根据其效率进行分类。我们通过查看算法的性能如何随着要排序的列表大小的增加而变化来衡量效率。我们希望随着列表越来越大，排序算法表现良好。交换和内存使用：一些排序算法可以通过重新排列列表本身中的元素来对列表进行排序，而无需额外的内存。这被称为“就地”算法。其他算法可能需要额外的内存来执行排序。递归：排序算法可以是递归的，也可以是非递归的。递归算法将排序问题分解为较小的子问题，并递归解决它们。非递归算法不使用这种方法。稳定性：在对元素进行排序时，保持值相等的项目的相对顺序很重要。例如，如果您有两张排名相同的卡片，稳定的排序算法将使它们保持排序前的相同顺序。比较排序：一些排序算法将元素成对比较，以确定其顺序。他们使用比较运算符（如“大于”或“小于”）进行这些比较。一般方法：排序算法可以使用不同的技术对元素进行排序，例如将元素插入其正确位置、交换元素、选择元素或合并列表的不同部分。串行或并行：排序算法可以设计为在单个计算机处理器（串行）或同时在多个处理器上（并行）上工作。适应性：一些排序算法可以利用列表中元素的初始顺序来提高其性能。它们被认为是“自适应”算法。在线：在线排序算法可以在添加新元素时持续对列表进行排序。它可以处理恒定的传入数据流。排序算法可以根据不同的因素进行分类：一些算法重新排列列表本身中的项目，而另一些算法则需要额外的内存来进行排序。一些算法使用分步过程，他们一次比较两个项目并决定其顺序。这就像比较两个数字，然后决定哪个更大或更小。有不同的排序方法，例如将项目插入其正确的位置，交换项目或逐个选择项目。一些算法被设计为在一个计算机处理器上工作，而另一些算法可以同时在多个处理器上工作。稳定性是一个概念，在保持其原始顺序的同时，对相等的项目进行排序。例如，如果您有两张排名相同的卡片，稳定的排序算法将使它们保持排序前的相同顺序。

排序算法可能很复杂，但主要想法是想办法有效地组织事物列表。使用的具体算法取决于列表大小、可用内存和期望结果等因素。

气泡分类

是最直接的排序算法，如果附近的元素顺序错误，则通过反复切换它们来发挥作用。由于其高平均和最坏时间复杂度，因此不应将大型数据集与这种方法一起使用。

从第一个元素（索引0）开始，并将其与下一个元素（索引1）进行比较。如果第一个元素大于第二个元素，请交换它们。移动到下一对元素（索引1和索引2）并进行比较。继续整个列表的此过程，如有必要，比较和交换相邻元素。第一次通过列表后，最大的元素将“冒泡”到列表中的最后一个位置。对列表的剩余未排序部分重复上述步骤（不包括最后一个位置，因为它已经处于正确的排序位置）。继续此过程进行多次传递，直到整个列表排序。算法代码

#include <stdio.h>// 执行气泡排序的功能void bubbleSort(int arr[], int n) {    // 外部循环来控制通过数组的次数    for (int i = 0; i < n - 1; i++) {        // 假设数组最初对每个通道进行排序        int sortedFlag = 1；        // 内部循环来比较相邻的元素，并在必要时交换它们        for (int j = 0; j < n - 1 - i; j++) {            // 比较相邻的元素            if (arr[j] > arr[j + 1]) {                // 如果元素的顺序错误，请交换它们                int temp = arr[j];arr[j] = arr[j + 1]；arr[j + 1] = 温度；                // 将 sortedFlag 设置为 0，表示发生了交换排序标志 = 0；}}        // 如果此通道中没有发生交换，则数组已排序，我们可以提前终止        如果（sortedFlag == 1）{            休息；}}}// 打印数组元素的函数void printArray(int arr[], int size) {    for (int i = 0; i < size; i++) {        printf("%d ", arr[i]);}    printf("\n");}// 示例用法int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    printf("未排序数组: ");    printArray（arr，n）；    bubbleSort（arr，n）；    printf("Sorted array: ");    printArray（arr，n）；    返回0；}

选择排序是一种简单而高效的排序算法，其工作原理是从列表的未排序部分反复选择最小（或最大）元素，并将其移动到列表的排序部分。

该算法从列表的未排序部分中反复选择最小的元素，并将其与未排序部分的第一个元素交换。对剩余的未排序部分重复此过程，直到整个列表被排序。

伪代码

我们可以说主要是两个步骤

查找最小值交换算法从第一个元素作为最小值开始（假设它是最小的）。将此元素与数组中的其余元素进行比较，以找到数组未排序部分中的实际最小元素。将步骤2中找到的最小元素与第一个未排序元素（当前起始位置的元素）交换。将未排序部分的起始位置向右移动（将索引增加1）。重复步骤1到4，直到整个数组排序。整个数组从索引0到4依次遍/遍了排序数组中的第一个位置。在浏览完整个数组后，很明显，11是第一个最低值，现在存储了64。因此，将64换成11。11往往在一次迭代后出现在排序列表的顶部，尽管是数组中的最小值。重复数组其余部分的顺序遍历，其中存在25。遍历数组后，我们发现12是第二低的值，它属于第二位，因此我们切换了这些值。接下来，通过遍历数组的剩余元素，确定数组中再次存在25的第三个最小值。由于22在遍历过程中被发现是第三小值，并且应该在数组中的第三个位置，因此将22与当前位于第三个位置的元素交换。同样，对于位置四，搜索数组的剩余元素，以确定第四个最小元素。25将排在第四位，因为它是第四低值。最后，数组的最大值会自动定位在最终位置。生成的数组是排序数组。代码

#include <stdio.h>// 执行选择排序的函数void selectionSort(int arr[], int n) {    for (int i = 0; i < n - 1; i++) {        // 假设当前元素是最小值        int minIndex = i；        // 在数组的未排序部分中查找最小元素的索引        for (int j = i + 1; j < n; j++) {            if (arr[j] < arr[minIndex]) {                // 如果找到较小的元素，请更新minIndexminIndex = j；}}        // 将最小元素与第一个未排序的元素交换        // 第一个未排序的元素位于索引'i'        // 最小元素位于索引'minIndex'        // 此步骤将最小元素放在排序部分的正确位置        int temp = arr[i];arr[i] = arr[minIndex]；arr[minIndex] = 温度；}}// 打印数组元素的函数void printArray(int arr[], int size) {    for (int i = 0; i < size; i++) {        printf("%d ", arr[i]);}    printf("\n");}// 示例用法int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    printf("未排序数组: ");    printArray（arr，n）；    selectionSort（arr，n）；    printf("Sorted array: ");    printArray（arr，n）；    返回0；}

你随机选择一个数字，开始排列左边小于该数字的所有数字，右边所有大于该数字的数字，并这样做，直到你对所有数组进行排序

算法交换功能快速排序快速排序递归分区功能快速排序递归函数算法放置基本条件通过调用分区函数来带来pivot_index的值用左数组调用自己用数组的正确部分调用自己分区函数算法Partition函数用于为QuickSort对数组进行分区。它需要一个数组arr，以及两个low和high的索引，这定义了需要分区的数组的范围。在步骤1中，选择枢轴。在本例中，我们选择数组的最后一个元素作为枢轴，但您可以使用不同的技术选择枢轴，例如随机选择它。在步骤2中，我们将变量i初始化为low - 1i将表示数组中较小元素的索引。在步骤3中，我们将数组从索引low循环到high - 1如果索引j处的元素小于或等于枢轴，我们增加i，并将索引i处的元素与索引j处的元素交换。此步骤将较小的元素移动到枢轴的左侧。在步骤4的循环之后，i + 1将是枢轴的正确索引。我们将索引i + 1的元素与枢轴元素（位于索引high）交换，将枢轴置于其正确的排序位置。在步骤5中，我们返回索引i + 1这是排序数组中枢轴的索引。数组现在分区，枢轴左侧有较小的元素，右侧有较大的元素。实施

#include <stdio.h>// 交换两个元素的函数void swap(int* a, int* b) {    int temp = *a;*a = *b；*b = 温度；}// 执行分区步骤的功能int partition(int arr[], int low, int high) {    // 选择枢轴元素（在这种情况下，我们选择最后一个元素作为枢轴）    int pivot = arr[高]；        // 初始化较小元素的索引    int i = 低 - 1；    // 在数组上循环进行分区    for (int j = low; j < high; j++) {        if (arr[j] <= pivot) {i = i + 1；            // 交换arr[i]和arr[j]，因为arr[j]属于左分区交换(&arr[i], &arr[j]);}}    // 循环之后，'i + 1'将是枢轴的正确索引    // 交换arr[i + 1]和枢轴（arr[high]）以将枢轴置于其正确位置交换（&arr[i + 1]，&arr[高]）；    // 返回索引'i + 1'，这是排序数组中枢轴的索引    返回i + 1；}// 执行QuickSort的功能void quickSort(int arr[], int low, int high) {    如果（低<高）{        // 执行分区步骤以获得枢轴的正确位置        int pivotIndex = partition(arr, low, high);        // 递归对左右分区进行排序quickSort（arr，低，枢轴索引-1）；quickSort（arr，pipontIndex + 1，高）；}}// 打印数组元素的函数void printArray(int arr[], int size) {    for (int i = 0; i < size; i++) {        printf("%d ", arr[i]);}    printf("\n");}// 示例用法int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    printf("未排序数组: ");printArray（arr，n）；quickSort（arr，0，n - 1）；    printf("Sorted array: ");printArray（arr，n）；    返回0；}

是一个简单的排序算法，其工作原理类似于您手中扑克牌的排序方式。数组实际上分为排序部分和未排序部分。从未排序部分的值被挑选并放置在排序部分的正确位置。

插入排序算法要按升序对大小为N的数组进行排序，在数组上进行遍及将当前元素（密钥）与其前身进行比较如果关键元素比其前身小将其与之前的元素进行比较。将较大的元素向上移动一个位置，为交换的元素腾出空间。它是如何运作的

让我们有一个数组。首先

数组的前两个成员最初使用插入排序进行比较。由于12大于11，它们没有按升序排列，12也不在适当的位置。所以，改变11和12。因此，11目前保存在一个排序的子阵列中。下一个通行证：继续以下两个组件，现在进行比较。在这里，13大于12，因此两个项目似乎都呈升序；因此，不会有任何切换。第三个通行证：12个也保存在一个排序的子数组中，有11个第四个通行证：现在，11和12是排序子阵列中仅有的两个元素。转到以下两个组成部分，即13和5，更改5和13，因为它们都不在正确的位置。交换后，元素12和5不再排序；因此，再次交换。同样，在这种情况下，11和5没有排序，所以再次交换。在这里，位置5是正确的第四通道：目前，排序子数组中的元素是5、11和12。以下两个组成部分是13和6它们显然没有分类，所以在它们之间切换。现在6小于12，再切换一次。在这里，交换也使11和6不排序，因此，再次交换最后，数组完全排序。实施

#include <stdio.h>void insertionSort(int arr[], int n) {    int i，j，键；    // 从第二个元素开始遍默数组    对于（i = 1; i < n; i++）{        // 存储要插入到数组的排序部分的当前元素key = arr[i];        // 在数组的排序部分找到正确的位置（索引）以插入键j = i - 1；        // 将大于键的元素移到右边        // 直到我们找到密钥的正确位置        while (j >= 0 && key < arr[j]) {arr[j + 1] = arr[j]；j--;}        // 将键插入其正确位置arr[j + 1] = 键；}}int main() {    int arr[] = {12, 11, 13, 5, 6};    int n = sizeof(arr) / sizeof(arr[0]);    printf("原始数组: ");    对于（int i = 0; i < n; i++）{        printf("%d ", arr[i]);}    // 调用插入排序函数    插入Sort（arr，n）；    printf("\nSorted array: ");    对于（int i = 0; i < n; i++）{        printf("%d ", arr[i]);}    返回0；}