`
guimingyue
  • 浏览: 75750 次
  • 性别: Icon_minigender_1
  • 来自: 湖北
社区版块
存档分类
最新评论

自底向上的归并排序

 
阅读更多
自底向上的归并排序(即非递归归并排序)方法,排序过程如下图:


 
首先两两归并,然后再归并元素数量加倍,这样的归并规程就像一颗二叉树。
在下面的代码中,函数mergeSort就是控制数组进行自底向上的归并的。m用于指定每次每个归并数组的归并元素的数量,i用于控制归并数组的选择(即指针的偏移)。在归并的时候(merge函数),使用一个辅助数组aux来进行归并,辅助数组aux是一个全局变量,大小应该与待排序数组一样,下面的代码中为了简单,直接设置成了15(即带排序数组a的大小)
#include <stdio.h>
#include <stdlib.h>
 
#define min(A, B) (A < B)? A:B
typedef char Item;
 
void mergeSort(Item a[], int l, int r);
void merge(Item a[], int start, int mid, int end);
 
Item aux[15];
/**
自底向上的归并排序
*/
int main() {
    int i;
    Item a[] = {'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
    mergeSort(a, 0, 14);
    for(i = 0; i < 15; i++) {
        printf("%4c", a[i]);
    }
    return 0;
}
/*自底向上的归并排序方法*/
void mergeSort(Item a[], int l, int r) {
    int m, i;
    for(m = 1; m < r; m += m) {
        for(i = 0; (l+i+m-1) < r; i = i + m + m) {
            merge(a, l+i, l+i+m-1, min(l+i+m-1+m, r));
        }
    }
}
 
/**
改进的归并方法,这样就可以减少检测是否到队尾的比较次数
*/
void merge(Item a[], int start, int mid, int end) {
    int i, j, k;
    for(i = mid + 1; i > start; i--) aux[i-1] = a[i-1];
    for(j = mid; j < end; j++) aux[end+mid-j] = a[j+1];
 
    for(k = start; k <= end; k++)
        if(aux[i] < aux[j])
            a[k] = aux[i++];
        else
            a[k] = aux[j--];
}
  • 大小: 53.8 KB
分享到:
评论

相关推荐

    自底向上归并排序和冒泡排序时间对比

    自底向上归并排序不同于传统的递归版本,它避免了递归带来的额外开销,而是通过一系列的合并操作逐步将数组排序。首先,它将数组分成两个子数组,然后不断将已排序的小数组合并成更大的有序数组,直至整个数组有序。...

    归并排序c语言实现

    4. **自底向上的归并排序**:与递归版本不同,自底向上归并排序通过从小规模数组开始,逐步合并成更大规模的有序数组,避免了递归带来的开销。 总之,归并排序是一种高效的排序算法,其C语言实现涉及递归、临时数组...

    归并排序(JAVA)

    - **自底向上的归并排序**:与传统的自顶向下递归不同,自底向上归并排序通过一系列的合并操作逐步将小的有序序列合并成大的有序序列,减少了递归带来的开销。 - **使用更少的临时空间**:在某些情况下,可以通过...

    排序算法-归并排序详细讲解(MergeSort)

    1. 自底向上归并排序:为了避免递归带来的开销,可以采用自底向上的方法,从长度为1的子序列开始,逐步合并成更大的有序序列。 2. 插入排序优化:对于小规模的子序列,可以考虑使用插入排序,因为插入排序在小规模...

    C++实现自底向上的归并排序算法

    自底向上的归并排序是一种高效的排序算法,它利用了分治的思想,通过逐步合并小的有序序列来构建大的有序序列。在C++中实现这种排序算法,首先需要理解其基本原理。 一、算法描述 自底向上的归并排序算法主要分为...

    算法-理论基础- 排序- 归并排序(包含源程序).rar

    6. 可能还包括一些优化技巧,如自底向上归并排序、三向切分归并排序(用于处理有大量重复元素的数组)等。 通过深入学习和理解归并排序,你可以提升在算法设计和数据结构方面的技能,这对于解决复杂的编程问题和...

    算法-数据结构之归并排序.rar

    - **自底向上的归并排序**:与传统的自顶向下递归方法相比,自底向上归并排序避免了重复的子问题,减少了函数调用的开销。 - **三向切分归并排序**:在处理包含大量重复元素的数组时,三向切分归并排序可以减少...

    数据结构——归并排序

    归并排序通常有两种实现方式:自底向上的归并排序和自顶向下的归并排序。 1. 自底向上:从长度为1的子序列开始,不断合并相邻的子序列,直至整个序列有序。这种方法避免了递归,但需要额外的空间来存储子序列。 2....

    java 排序算法 选择排序,插入排序,自顶向上合并排序,合并排序,快速排序

    3. **自顶向上归并排序(Top-down Merge Sort)** 归并排序是一种采用分治法的排序算法,自顶向下的归并排序则是从大问题开始分解,每次将两个子序列合并成一个有序序列。具体步骤如下: - 将大序列不断拆分成长度为...

    C++/GoLang如何实现自底向上的归并排序

    在本文中,我们将探讨如何使用C++和GoLang实现自底向上的归并排序。归并排序是一种基于分治策略的排序算法,它将大问题分解为小问题,然后逐步合并解决,最终达到整个序列有序的状态。自底向上的归并排序方法避免了...

    归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

    - 如果内存限制允许,可以使用自底向上的归并排序方法,避免递归带来的开销。 - 在合并过程中,可以使用“缓冲区”技术,减少不必要的内存分配和释放,提高效率。 归并排序的应用场景: - 数据量较大且对稳定性有...

    排序-归并排序(Merge sort)

    虽然它的空间复杂度相对较高,但通过优化,例如使用自底向上的归并策略,可以在一定程度上减少空间需求。在理解和实现排序算法的过程中,掌握归并排序对于提升编程技能和解决问题能力是非常有益的。

    归并排序 排序

    归并排序是一种基于分治策略的高效排序算法,它的核心思想是将大问题分解成小问题,逐个解决,然后再将结果合并,最终得到整个问题...在自底向上的归并排序实现中,这可以通过在合并过程中维护一个逆序对计数器来完成。

    归并排序算法源代码

    - **效率优化**:可以采用自底向上的归并排序方法,避免过多的递归调用,从而减少函数调用开销。 - **稳定性**:归并排序是稳定的排序算法,即相等的元素在排序后相对位置不变,这对于处理需要保持原有顺序的场景...

    归并排序VS2010代码

    在实现归并排序时,通常有两种方法:自顶向下和自底向上。自顶向下的方法是直接应用递归,而自底向上的方法是通过迭代逐步合并较小的子数组,直到整个数组被排序。 归并排序的时间复杂度是O(n log n),其中n是待...

    实验二:几种排序算法的实验性能比较1

    在这个实验中,我们探讨了几种不同的排序算法,包括插入排序(Insertion Sort,IS)、自顶向下归并排序(Top-down Mergesort,TDM)、自底向上归并排序(Bottom-up Mergesort,BUM)、随机快速排序(Random ...

    8中顺序排序

    自底向上归并排序是先从小规模的子序列开始,不断将相邻的有序子序列合并成更大的有序序列,直到整个序列有序。 - 时间复杂度:无论最好、最坏还是平均情况,归并排序的时间复杂度都是O(n log n),但需要额外的O(n)...

    归并排序c源程序

    2路归并排序循环算法,避免递归调用带来的麻烦,采用自底向上的方法

    guibingpaixu.rar_归并排序

    - 实现方式:归并排序可以采用自顶向下(递归)或自底向上(迭代)的方式实现。递归方法直观但会增加函数调用的开销,而迭代方法通常更节省内存。 在实际应用中,归并排序常用于以下情况: - 当数据量非常大,无法...

Global site tag (gtag.js) - Google Analytics