当前位置： 首页 > article >正文

数据结构：排序（内部排序+各种排序算法的性质总结）

article 2024/11/18 14:23:21

数据结构的排序是计算机科学中的一个基本且重要的操作，它指的是将一组数据元素（或记录）按照一定规则（通常是关键字的大小）进行排列的过程。排序后的数据元素在物理或逻辑上呈现出某种顺序性，从而便于后续的查找、统计等操作。

排序的定义要素

  1. 数据元素：这是排序操作的基本单位，可以是一个数字、一个字符串，或者是一个包含多个字段的记录等。

  2. 关键字：用于比较的数据元素中的某个属性或字段，排序算法依据这个关键字的值来决定数据元素的顺序。例如，对于一组学生的记录，我们可以选择学生的年龄或分数作为关键字进行排序。

  3. 排序规则：即数据元素之间的比较准则，决定了数据元素在排序后的序列中的相对位置。排序规则通常是基于关键字的值，可以是升序（从小到大）或降序（从大到小）。

  4. 排序算法：是实现排序的具体步骤和方法，不同的排序算法有不同的时间复杂度、空间复杂度和稳定性等特性。

  5. 算法的稳定性：在排序算法中，稳定性指的是当待排序的序列中存在多个具有相同关键字的元素时，经过排序后这些元素的相对位置保持不变。这种性质在某些应用场景中非常重要，因为它可以保留元素之间的原始顺序信息。

排序算法的分类

排序算法可以根据多种标准进行分类，常见的分类方式包括：

  • 比较排序：通过比较数据元素之间的关键字来决定其相对位置，如冒泡排序、选择排序、插入排序、归并排序、快速排序等。

  • 非比较排序：不直接比较数据元素的关键字，而是通过其他方式确定元素的顺序，如计数排序、桶排序、基数排序等。这类排序算法通常具有更高的效率，但适用范围较窄。

  • 稳定排序：如果两个元素的关键字相同，排序后它们的相对位置不变，则称该排序算法是稳定的。例如，归并排序是稳定的，而快速排序通常不是稳定的。

  • 原地排序：排序过程中只需要用到常数额外空间的排序算法，称为原地排序。这类算法的空间复杂度较低，如冒泡排序、插入排序、堆排序等。

按数据元素是否完全存放在内存中：

  • 内部排序：

内部排序算法是指数据元素全部存放在内存中所进行的排序过程，主要包括以下几种常见的算法：

1. 插入排序

  • 直接插入排序：

将待排序的记录按其关键字值的大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成。

直接插入排序（Straight Insertion Sort）是一种简单的排序算法，它的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤
  1. 初始化：从第一个元素开始，该元素可以认为已经被排序。
  2. 取元素：取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 比较与移动：如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 插入元素：将新元素插入到该位置后。
  6. 重复步骤2~5，直到所有元素均排序完毕。
特点：

  1. 简单性：直接插入排序算法实现简单，易于理解和实现。它不需要额外的数据结构，如栈、队列等，只需要使用到少量的临时变量。

  2. 稳定性：直接插入排序是稳定的排序算法。如果在排序过程中，两个相等的元素先后出现，那么它们在排序后的序列中的相对位置不会改变。

  3. 时间复杂度：

    • 最好情况下，即待排序序列已经是有序的情况下，直接插入排序的时间复杂度为O(n)，其中n是待排序元素的数量。
    • 平均情况下和最差情况下，即待排序序列是逆序的情况下，直接插入排序的时间复杂度为O(n^2)。这是因为对于每一个元素，最坏情况下都需要与前面的所有元素进行比较和可能的移动。

  4. 空间复杂度：直接插入排序的空间复杂度非常低，为O(1)。这是因为它只需要几个临时变量来存储比较和移动过程中的数据，不需要额外的存储空间。

  5. 适用性：虽然直接插入排序在数据量较大时效率不高，但在数据量较小或者基本有序（即待排序序列中大部分元素已经处于有序状态）的情况下，它的效率还是比较高的。此外，由于它稳定性好，也常用于需要保持元素相对顺序稳定的场合。

  6. 原地排序：直接插入排序是一种原地排序算法，它只需要使用常数级别的额外空间，因此非常适合在内存受限的环境下使用。

void InsertSort(ElemType A[],int n){
    int i,j;
    for(i=2;i<n;i++){
        if(A[i]<A[i-1]){
            A[0]=A[i];
            for(j=i-1;A[0]<A[j];--j){
                A[j+1]=A[j];
            }
            A[j]=A[0];
        }
    }
}
  • 折半插入排序： 

折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。在插入排序中，算法不断地将元素插入到前面已经排好序的序列中。而折半插入排序则利用了折半查找（二分查找）的方法来加速寻找插入点的过程，从而减少了比较的次数，但元素的移动次数并未改变。

基本思想

折半插入排序的基本思想是将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素。排序过程即每次从无序表中取出第一个元素，通过折半查找的方式找到它在有序表中的正确位置，并将其插入，使之成为新的有序表，重复n-1次完成整个排序过程。

排序过程
  1. 初始化：设第一个元素为已排序序列，其余n-1个元素为待排序的无序序列。
  2. 取元素：从无序序列中取出第一个元素，记为temp。
  3. 折半查找：在有序序列中，利用折半查找的方式找到temp的正确插入位置。具体做法是，通过不断将有序序列的中间元素与temp进行比较，根据比较结果调整查找范围，直到找到temp的正确位置。
  4. 元素后移：为了将temp插入到有序序列的正确位置，需要将该位置及其之后的所有元素向后移动一位。
  5. 插入元素：将temp插入到有序序列的正确位置。
  6. 重复操作：重复步骤2至步骤5，直到无序序列为空，排序完成。
特点
  • 时间复杂度：虽然折半插入排序减少了比较的次数，但由于元素的移动次数并未改变，因此其时间复杂度仍为O(n^2)。
  • 空间复杂度：折半插入排序是一种原地排序算法，不需要额外的存储空间，因此其空间复杂度为O(1)。
  • 稳定性：折半插入排序是一种稳定的排序算法。在比较时，如果两个元素相等，则不会进行移动，因此排序完成后，相同元素之间的先后顺序不变。
注意事项
  • 在实现折半插入排序时，需要注意防止整数溢出问题。在求中间下标mid时，应使用mid = low + (high - low) / 2而不是mid = (high + low) / 2，以避免在high和low都很大时发生整数溢出。
  • 折半插入排序适用于数据量不是很大的情况。对于大数据量的排序，可能需要考虑使用更高效的排序算法，如归并排序、快速排序等。

综上所述，折半插入排序是一种通过折半查找来加速插入过程的排序算法，具有稳定性高、空间复杂度低的特点，但时间复杂度仍为O(n^2)。

//折半插入
void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){
    A[0]=A[i];
    low=1;high=i-1;
    while(low<=high){
        mid=(low+high)/2;
        if(A[0]<A[mid])
        high=mid-1;
        else
        low=mid+1;
    }
    for(j=i-1;j>=high+1;--j){
        A[j+1]=A[j];
    }
    A[j]=A[0];
}
}
  • 希尔排序：

希尔排序（Shell's Sort），又称缩小增量排序（Diminishing Increment Sort），是插入排序的一种更高效的改进版本。该算法由D.L.Shell在1959年提出，并因其名字而得名。希尔排序的基本思想是将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

特点：
  1. 非稳定排序算法：希尔排序不是稳定的排序算法，因为相同的元素可能在排序过程中改变相对位置。
  2. 基于插入排序的改进：希尔排序通过引入增量的概念，允许元素在较大的间隔上进行比较和移动，从而减少了元素移动的次数，提高了排序效率。
  3. 增量序列的选择：希尔排序的性能在很大程度上取决于增量序列的选择。不同的增量序列会导致不同的排序效率。常用的增量序列有希尔原始增量序列、Hibbard增量序列、Knuth增量序列和Sedgewick增量序列等。
步骤：
  1. 初始化增量序列：选择一个递减的增量序列，通常从数组长度的一半开始，每次减半，直到增量为1。
  2. 外层循环：逐步缩小增量，对每组元素进行排序。
  3. 内层循环：在每个增量下，对分组后的元素进行插入排序。这包括比较和移动元素，以确保分组内的元素有序。
  4. 完成排序：当增量减小至1时，整个数组已经基本有序，最后进行一次插入排序，完成整个排序过程。
特点：

优点：

  • 希尔排序比简单插入排序更加快速，特别是在处理大规模数据集时。
  • 希尔排序的适应环境能力强，每排序完一遍，数据就越接近有序状态。
  • 希尔排序的算法代码短而简单，易于实现。

缺点：

  • 希尔排序的时间复杂度在最坏情况下可以达到O(n^2)，尽管在实际应用中通常表现更好。
  • 希尔排序不是稳定的排序算法，可能会改变相同元素的相对位置。
  • 希尔排序的性能受到增量序列选择的影响，需要选择合适的增量序列以达到最优的排序效率。
应用场景：

希尔排序适用于中等大小规模的数据排序，对于规模非常大的数据排序可能不是最优选择。此外，如果数据已经部分有序，希尔排序能够利用这种部分有序性进一步优化排序过程。在动态数据集和实时系统中，希尔排序由于其较好的性能和较小的内存占用，也是一个合适的选择。

总的来说，希尔排序是一种在实际应用中非常有用的排序算法，特别是在处理中等规模数据集时。通过选择合适的增量序列，可以进一步提高希尔排序的效率和性能。

void ShellSort(ElemType A[],int n){
    int i,j,dk;
    for(dk=n/2;dk>=1;dk=dk/2){//增量的选取不唯一
        for(i=dk+1;i<=n;i++){
            if(A[i]<A[i-dk])
             A[0]=A[i];
        for(j=i-dk;j>0&&A[j]>A[0];j-=dk){
            A[j+dk]=A[j];
        }
        A[j+dk]=A[0];
        }
       
    }
}

2. 选择排序

  • 简单选择排序：

简单选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置（或末尾位置），然后再从剩余的未排序元素中继续寻找最小（或最大）元素，放到已排序的序列的末尾（或起始位置）。以此类推，直到全部待排序的数据元素都排序完毕。

步骤：
  1. 初始化：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
  2. 遍历查找：从剩余未排序元素中继续寻找最小（或最大）元素。
  3. 交换：如果找到的最小（或最大）元素不是位于未排序序列的起始位置，则将其与未排序序列起始位置的元素进行交换。
  4. 重复步骤：将未排序序列的起始位置向后移动一位，重复上述步骤，直到所有元素都排序完毕。
特点：
  • 时间复杂度：简单选择排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。这是因为算法需要两层嵌套循环来完成排序过程，外层循环控制排序的轮数，内层循环负责在每一轮中找到最小（或最大）元素。
  • 空间复杂度：简单选择排序的空间复杂度为O(1)，因为它只需要固定的额外空间来存储临时变量，如最小元素的索引和用于交换的临时变量。
  • 稳定性：简单选择排序是不稳定的排序算法。因为算法在交换元素时，可能会改变相同元素的相对位置。
  • 堆排序：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
void SelectSort(ElemType A[],int n){
    for(int i=0;i<n;i++){
        int min=i;
        for(int j=i+1;j<n;j++){
            if(A[j]<A[min])
            min=j;
            
        }
        if(min!=i)
        swap(A[i],A[min]);
    }

}
  • 堆排序：

堆排序（Heapsort）是一种基于比较的排序算法，它利用了堆这种数据结构进行排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序可以分为两个主要的过程：构建初始堆和调整堆以进行排序。

步骤：
  1. 构建初始堆：
    • 将待排序的序列构造成一个大顶堆（对于升序排序）或小顶堆（对于降序排序）。大顶堆的根节点是所有节点中最大的，小顶堆的根节点是所有节点中最小的。
    • 通常从最后一个非叶子节点开始，自底向上进行堆的调整，确保每个子树都满足堆的性质。
  2. 排序过程：
    • 将堆顶元素（即当前最大值或最小值）与堆的最后一个元素交换。
    • 减小堆的大小（即不考虑已经排序的最后一个元素），并重新调整堆，使其满足堆的性质。
    • 重复上述步骤，直到堆的大小为1，此时整个序列已经有序。
特点：
  1. 时间复杂度：
    • 堆排序的时间复杂度主要由构建初始堆和反复调整堆的时间开销构成。构建初始堆的时间复杂度为O(n)，调整堆的时间复杂度为O(logn)，由于需要调整n-1次，所以堆排序的总时间复杂度为O(nlogn)。
  2. 空间复杂度：
    • 堆排序是原地排序算法，除了用于交换的临时变量外，不需要额外的存储空间，因此空间复杂度为O(1)。
  3. 稳定性：
    • 堆排序不是稳定的排序算法，因为相等的元素可能会在排序过程中因为交换而改变它们在原序列中的相对顺序。
  4. 适用性：
    • 堆排序适用于大规模数据的排序，尤其是当内存不足以容纳全部待排序数据，需要在外部存储设备（如硬盘）上进行排序时。由于堆排序不需要额外的存储空间，且时间复杂度较低，因此在这些场景中具有较高的实用价值。
应用场景：
  1. 优先队列：堆排序是构建优先队列的一种常用方法。优先队列是一种特殊的队列，它可以按照元素的优先级进行排序，使得优先级最高的元素能够首先被取出。
  2. 大规模数据处理：在处理大规模数据集时，堆排序具有显著的优势。由于堆排序只需要维护部分数据的堆结构，而不需要将所有数据都加载到内存中进行排序，因此它适用于无法一次性加载整个数据集的情况。
  3. 查找最大（或最小）的K个元素：通过维护一个大小为K的最小堆（或最大堆），可以在O(nlogK)的时间复杂度内找到最大（或最小）的K个元素。这种方法在处理海量数据时非常高效。

综上所述，堆排序是一种基于堆数据结构的排序算法，具有时间复杂度低、空间复杂度小、实现简单等特点，适用于大规模数据的排序和优先队列的构建等场景。

//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>0;i++){
        HeadAdjust(A,i,len)
    }
}

void HeadAdjust(ElemType A[],int k,int len){
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2){
        if(i<len&&A[i]<A[i+1])
        i++;
        if(A[0]>=A[i])
        break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){
        swap(A[i],A[0]);
        HeadAdjust(A,1,i-1);
    }
}

3. 交换排序

  • 冒泡排序：

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这意味着该数列已经排序完成。

工作原理：
  1. 比较相邻的元素：如果第一个比第二个大（对于升序排序），就交换它们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
特点：

冒泡排序（Bubble Sort）是一种简单的排序算法，它的工作原理是通过重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序的特点包括：

  1. 简单性：冒泡排序的算法逻辑非常直观简单，容易理解和实现。

  2. 稳定性：冒泡排序是一种稳定的排序算法。在排序过程中，如果两个相等的元素相遇，它们的相对位置不会改变。

  3. 时间复杂度：

    • 最好情况下，即待排序序列已经是有序的情况下，冒泡排序的时间复杂度为O(n)，因为只需要遍历一遍数组即可。
    • 平均情况下和最差情况下，即待排序序列是逆序的情况下，冒泡排序的时间复杂度为O(n^2)。因为对于每一个元素，最坏情况下都需要与后面的所有元素进行比较和可能的交换。

  4. 空间复杂度：冒泡排序的空间复杂度为O(1)，因为它只需要几个临时变量来存储比较和交换过程中的数据，不需要额外的存储空间。

  5. 适用性：冒泡排序适用于数据量较小的情况，或者当数据基本有序时，因为其时间复杂度会随着数据的有序程度而降低。然而，在处理大规模数据时，由于其时间复杂度的限制，冒泡排序可能不是最优选择。

  6. 原地排序：冒泡排序是一种原地排序算法，它只需要使用常数级别的额外空间。

示例：

假设有一个数组 arr = [64, 34, 25, 12, 22, 11, 90]，进行冒泡排序的过程如下：

  • 第一轮排序后：[25, 12, 22, 11, 34, 64, 90]（将64与前面的元素比较并交换）
  • 第二轮排序后：[12, 22, 11, 25, 34, 64, 90]（将25与前面的元素比较并交换）
  • 第三轮排序后：[11, 22, 12, 25, 34, 64, 90]（将22与前面的元素比较并交换）
  • ...（继续此过程）
  • 最终排序结果：[11, 12, 22, 25, 34, 64, 90]
void BubbleSort(ElemType A[],int n){
    int i,j;
    
    for(i=0;i<n-1;i++){
        bool flag=false;
        for(j=n-1;j>i;j--){
            if(A[j]<A[j-1]){
                swap(A[j],A[j-1]);
                flag=true;
            }
        }
        if(flag==false)
        return;
    }
}
  • 快速排序：

快速排序（Quick Sort）是计算机科学与技术领域中非常经典的一种排序算法，它采用了分治的思想进行排序。以下是关于快速排序的详细解释：

基本原理：

快速排序的基本原理是选择一个基准元素（pivot），然后将数组分为两部分，一部分包含小于基准的元素，另一部分包含大于基准的元素。接着，对这两部分继续进行快速排序，直到整个数组都有序。这个过程不断递归进行，因为每次都能将数组规模大致减半，所以在平均情况下能实现较高的排序效率。

排序流程：
  1. 选择基准值：从数组中选择一个元素作为基准值，通常可以选择第一个元素、最后一个元素或者随机选择一个元素。
  2. 分区操作：通过一系列的比较和交换操作，使得小于基准值的元素都在基准值的左边，大于基准值的元素都在基准值的右边。这个过程中，会用到两个指针（通常称为low和high），分别指向数组的起始和结束位置，然后通过这两个指针的移动来完成分区。
  3. 递归排序：对划分出来的左右两个子数组，分别重复上述的选择基准和划分操作，直到整个数组都有序。
优点：
  1. 平均时间复杂度低：在平均情况下，快速排序的时间复杂度为O(nlogn)，这使得它成为处理大规模数据排序的有效算法。
  2. 原地排序：快速排序是一种原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。
  3. 实现简单：快速排序的实现相对简单，代码量较少，易于理解和实现。
缺点：
  1. 最坏情况时间复杂度高：当输入数组已经有序或接近有序时，快速排序的时间复杂度会退化为O(n^2)。为了避免这种情况，可以采用随机选择基准值的方法。
  2. 稳定性差：快速排序不是稳定的排序算法，因为相等的元素可能会在排序过程中改变相对位置。
应用场景：

快速排序由于其高效的排序性能，被广泛应用于各种需要排序的场景中，特别是在处理大规模数据集时。此外，JDK中的Arrays.sort()方法内部就使用了快速排序的思想来实现数组的排序工作。

综上所述，快速排序是一种高效、实用的排序算法，它在处理大规模数据排序时具有显著的优势。然而，在实际应用中，也需要注意其最坏情况下的时间复杂度以及稳定性问题。

int Partition(ElemType A[],int low,int high){
    ElemType pivot=A[low];
    while(low<high){
        while(A[high]>=pivot&&low<high)
        high--;
        A[low]=A[high];
        while(A[low]<=pivot&&low<high)
        low++;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}
void QuickSort(ElemType A[],int low,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);
        QuickSort(pivotpos,low,pivotpos-1);
        QuickSort(pivotpos,pivotpos+1,high);
    }
}

4. 归并排序

归并排序（Merge Sort）是一种建立在归并操作上的有效、稳定的排序算法，它采用了分治法（Divide and Conquer）的思想。以下是归并排序的详细介绍：

基本原理：

归并排序的主要思想是将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并在一起。归并操作是将两个已排序的子序列合并成一个有序序列的过程。

排序步骤：

归并排序的详细步骤包括分解、递归排序和合并：

  • 分解：将待排序的数组分解成两个子数组，直到每个子数组只包含一个元素（因为一个元素的数组自然是有序的）。
  • 递归排序：对分解后的子数组分别进行归并排序，这是通过递归调用归并排序函数来实现的。
  • 合并：将两个已经有序的子数组合并成一个有序的数组。具体操作是比较两个子数组的头元素，将较小的元素取出放入新的合并后的数组中，然后相应子数组的指针后移，继续比较，直到其中一个子数组的元素全部取出，再将另一个子数组的剩余元素依次放入合并后的数组。
优点：
  • 稳定性：归并排序是一种稳定的排序算法，即相等的元素在排序后的顺序与它们在排序前的顺序相同。
  • 高效性：归并排序的时间复杂度为O(n log n)，这是基于比较的排序算法所能达到的最好时间复杂度。
  • 适用性：归并排序适用于大规模数据的排序，尤其是当内存足够大时，可以高效地对大量数据进行排序。
缺点：
  • 空间复杂度：归并排序需要O(n)的辅助空间来存储临时数组，这在处理大规模数据时可能会成为问题。
  • 递归深度：归并排序是递归算法，对于递归深度较大的情况，可能会导致栈溢出的问题。虽然在现代计算机上这通常不是问题，但在某些特定环境下（如嵌入式系统）仍需注意。
应用场合：
  • 数据库排序：在数据库系统中，经常需要对大量数据进行排序，归并排序是一种高效的排序算法。
  • 网络排序：在网络传输中，需要对数据进行排序以确保数据的正确性和有序性，归并排序可以确保数据的稳定性和完整性。
  • 数字信号处理：在数字信号处理领域，需要对大量信号数据进行排序和归并处理，归并排序可以高效地完成这一任务。
  • 图像处理：在图像处理中，有时需要对像素点进行排序和归并处理，归并排序是一种常用的算法。
  • 科学计算：在科学计算中，经常需要对模拟和仿真产生的大量数据进行排序和归并处理，归并排序是一种高效的算法选择。
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int high,int mid){
    int i,j,k;
    for(k=low;k<=high;k++){
        B[k]=A[k];
    }
    for(i=low,j=mid+1,k=i;i<mid&&j<high;k++){
        if(B[i]>B[j])
        A[k]=B[j];
        else
        A[k]=B[i];
    }
    if(i<=mid)
    A[K++]=B[i++];
    else
    A[k++]=B[j++];
}
void MergeSort(ElemType A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,high,mid);
    }
}

5. 基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行比较和排序。基数排序是桶排序的扩展，又称“分配式排序”或“桶子法”（bucket sort）。以下是基数排序的详细介绍：

基本原理：

基数排序通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。具体来说，基数排序从最低位（或最高位）开始，按照每一位的数值将元素分配到不同的桶中，然后对每个桶中的元素进行收集，并重复这一过程，直到最高位（或最低位）排序完成。

排序步骤：

基数排序的排序步骤主要包括分配和收集两个过程，具体如下：

  • 分配：对于数字，每位的取值范围是0-9（对于十进制数），因此需要10个容器（桶），这10个桶标号为0-9。每趟排序时，取每一个元素在该位的数值，依次放入对应的桶中。
  • 收集：在一趟排序完成后，按顺序从0-9的桶中依次取出元素，放回原数组或另一个数组中。
  • 重复：继续进行分配和收集，直到最大位数排序完成。
特点：
  • 非比较型排序：基数排序不需要进行元素之间的比较，而是通过分配和收集的方式实现排序，这使得基数排序在某些情况下比比较型排序算法更高效。
  • 稳定排序：基数排序是一种稳定的排序算法，即相等的元素在排序前后的相对顺序保持不变。
  • 适用范围广：基数排序不仅适用于整数排序，还可以扩展到字符串和特定格式的浮点数排序。由于整数也可以表达字符串（如名字、日期等）和浮点数，因此基数排序的应用范围非常广泛。
  • 时间复杂度：基数排序的时间复杂度主要取决于最大元素的位数K和待排序元素的数量n。在平均情况下，时间复杂度为O(n*k)，其中k是最大元素的位数。虽然时间复杂度是线性的，但有一个系数k，这使得基数排序在处理大范围数据时非常高效。
  • 空间复杂度：基数排序的空间复杂度主要取决于桶的数量和待排序元素的数量。在最坏情况下，空间复杂度为O(n+k)，其中n是待排序元素的数量，k是最大元素的位数。
应用场合：
  • 数据库查询：在处理大量数据库查询时，经常需要对查询结果进行排序。基数排序由于其高效性和稳定性，在数据库查询排序中得到了广泛应用。
  • 图像处理：在图像处理领域，有时需要对像素点进行排序和归并处理。基数排序可以高效地处理这类问题。
  • 数据分析：在数据分析领域，经常需要对大量数据进行排序和统计。基数排序能够快速高效地处理这些数据，提高数据分析的效率。
  • 其他领域：除了上述领域外，基数排序还可以应用于股票技术分析、金融数据分析、科学计算等多个领域。

这些内部排序算法各有特点，适用于不同的数据规模和排序需求。在实际应用中，可以根据具体情况选择合适的排序算法。

void CountSort(ElemType A[],int n,int k){
    int i,C[k];//C[k]存储计数值
    for(i=0;i<k;i++){
        C[i]=0;
    }
    for(i=0;i<n;i++){
        C[A[i]]++;
    }
    for(i=1;i<k;i++){
        C[i]=C[i]+C[i-1];//统计比自己小的数 
    }
    for(i=n-1;i>=0;i--){
        B[C[A[i]]]=A[i];
        C[A[i]]=C[A[i]]-1;
    }

}

各种排序算法的性质：

排序算法的选取：

选取排序算法时，需要考虑多个因素以确保算法的选择能够满足实际需求并达到最佳效果。以下是一些主要的考虑因素：

1. 数据量大小

  • 小数据量：对于较小的数据集，可以选择时间复杂度稍高但实现简单的排序算法，如插入排序、选择排序或冒泡排序。这些算法在数据量不大时表现良好，且易于理解和实现。
  • 大数据量：对于大数据集，应选择时间复杂度较低的排序算法，如快速排序、归并排序、堆排序等。这些算法能够更有效地处理大量数据，减少排序所需的时间。

2. 稳定性要求

  • 稳定排序：如果排序后的数据需要保持原有的相对顺序（即相等元素的相对位置不变），则应选择稳定的排序算法，如归并排序、插入排序、冒泡排序等。
  • 非稳定排序：如果不需要保持元素的相对顺序，可以选择非稳定的排序算法，如快速排序、选择排序等。这些算法在某些情况下可能具有更高的效率。

3. 空间复杂度

  • 原地排序：如果内存空间有限，应选择原地排序算法，即不需要额外分配大量存储空间的算法，如快速排序（在某些实现中）、堆排序等。
  • 非原地排序：如果内存空间相对充足，可以考虑使用非原地排序算法，如归并排序，该算法虽然需要额外的存储空间，但排序效率较高。

4. 数据的初始状态

  • 已排序或近似排序：如果数据已经部分排序或接近排序状态，插入排序等算法可能会表现得更好，因为它们可以利用数据的初始有序性来减少比较和移动的次数。
  • 完全无序：对于完全无序的数据集，快速排序、归并排序等算法通常能够更快地完成排序任务。

5. 排序元素的特性

  • 整数、浮点数或字符串：不同类型的元素可能需要不同的排序算法。例如，对于字符串排序，可能需要考虑字符的编码和比较规则。
  • 特定范围的元素：如果元素属于一个特定的范围，并且该范围相对较小，可以考虑使用桶排序或基数排序等算法，这些算法在某些情况下能够提供接近线性的时间复杂度。

6. 算法的可读性和可维护性

  • 代码可读性：选择易于理解和实现的排序算法可以提高代码的可读性和可维护性。
  • 算法复杂度：在保证性能的前提下，选择复杂度适中的算法可以使得代码更加简洁明了。

综上所述，在选取排序算法时，需要综合考虑数据量大小、稳定性要求、空间复杂度、数据的初始状态、排序元素的特性以及算法的可读性和可维护性等多个因素。根据实际需求选择合适的排序算法可以提高程序的性能和可维护性。

排序的目的

排序的主要目的是提高数据的检索效率，使得后续的数据处理（如查找、合并等）能够更快地进行。此外，排序也是数据分析和数据展示的基础，通过排序可以更容易地发现数据中的规律和趋势。


http://www.kler.cn/a/322839.html

相关文章：

  • 基于视觉智能的时间序列基础模型
  • Web导出Excel表格
  • 嵌入式课程day13-C语言指针
  • DAY120java审计第三方组件依赖库挖掘FastjsonShiroLog4jH2DB
  • git创建远程仓库，以gitee码云为例GitHub同理
  • 类和对象——拷贝构造函数，赋值运算符重载（C++）
  • 小程序兼容问题
  • OpenEuler22.03 LTS-SP1 开启SSH的X11 Forwarding，并使用Edge浏览器
  • 我们是向量数据库的领军企业，我们只招TOP人才
  • AI创作类工具系列之:芝士AI（paperzz）详细测评介绍
  • 【LLM】 TinyAgent 构建指南
  • 【CSS/HTML】CSS实现两列布局，一列固定宽度，一列宽度自适应方法
  • 软考高级：企业信息化-数据挖掘中的上卷和下钻、旋转分析
  • 一文速学-知识图谱从零开始构建实战:知识图谱的基本概念
  • PyQt5实现QLabel中的字体多种颜色闪烁效果
  • H. Sakurako‘s Test
  • 趋势外推法
  • Linux学习之路 -- 线程 -- 互斥
  • 20 基于STM32的温度、电流、电压检测proteus仿真系统（OLED、DHT11、继电器、电机）
  • [SwiftUI 开发] @dynamicCallable 与 callAsFunction：将类型实例作为函数调用
  • 虚假唤醒（Spurious Wakeup）详解：从概念到实践
  • laravel延迟队列 取消未支付超时订单订单
  • 堆排序，TopK问题|向上调整建堆|向下调整建堆(C)
  • Kafka系列之：安装使用kafka_exporter详细步骤
  • Agent智能体
  • 常见错误1：访问指针类型