额。。。 我发现一直写数据结构的可能有点枯燥。 于是我准备开始写点我常用的算法。再说,复杂的我也不会
今天,我就写个简单的归并排序。本来想写冒泡或者选择排序的。但写的时候,很好就完了,于是决定写点有意思的排序算法。
归并排序,熟悉排序算法的都应该不会陌生吧。 因此,我就不讲一堆理论(其实,我也不太清楚)。总之,了解归并排序的核心思想就对了。 当然,还是使用python实现。因为我最近在学python啊。感觉python很有意思
如有问题,请指正。
代码如下:
# -*- coding: cp936 -*- #--------------------------------------------- # #author chile #version 1.0 #since #date 2014-02-18 #desc 归并排序 # # # #--------------------------------------------- class MergeSort: def __init__(self): self.src = [] self.help = [] def sort(self,src): if len(src) == 0: return self.src = src self.initTarget() low , high = 0 , len(src) - 1 self.megersort(low,high) #由于python中数组是动态型的,需要手动初始化 def initTarget(self): target = self.help for i in range(len(self.src)): target.append(0) #递归调用 def megersort(self,low,high): if low >= high: return mid = low + (high - low ) / 2 self.megersort(low,mid) self.megersort(mid+1,high) self.merge(low,mid,high) #核心方法 (归并排序的思想是,当只有一个时,那个这个数就是有序的) def merge(self,low ,mid , high): src , help = self.src , self.help for i in range(low,high+1): help[i] = src[i] i , j = low , mid + 1 for k in range(low,high + 1): if i > mid: src[k] = help[j] j += 1 elif j > high: src[k] = help[i] i += 1 elif help[i] < help[j]: src[k] = help[i] i += 1 else: src[k] = help[j] j += 1 val = range(15,2,-1) print val sort = MergeSort() sort.sort(val) print sort.src
相关推荐
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
**三路归并排序**是一种高效的排序算法,尤其在处理含有大量重复元素的序列时表现优秀。该算法基于归并排序的思想,但将其分为三个部分处理,而不是传统的两个部分。在本文中,我们将深入探讨三路归并排序的原理、...
以下是关于"插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序"这十大经典排序算法的详细解释: 1. 插入排序:插入排序是一种简单的排序算法,它通过构建有序...
归并排序是一种基于分治思想的排序算法,而插入排序则是一种简单直观的排序算法,适用于小规模或部分有序的数据。 **归并排序**: 1. **基本原理**:归并排序将待排序的序列分为两半,对每一半递归地进行归并排序,...
### C语言二路归并排序算法 #### 概述 归并排序是一种高效的排序算法,其基本思想是采用分治法(Divide and Conquer),将一个数组分成两个子数组,然后递归地对这两个子数组进行排序,最后将两个有序的子数组合并...
以下是关于"冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序"这七种常见排序算法的源码实现及相关知识点的详细解释: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,它重复地遍历待排序的...
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
归并排序(Merge Sort)是一种基于分治策略的高效排序算法,由计算机科学家John W. Backus于1945年提出。它的工作原理可以分为三个主要步骤:分解、解决和合并。 1. 分解:将原始数据序列分成两个相等(或接近相等...
### 分治策略与归并排序 #### 一、分治策略概述 在计算机科学领域,分治(Divide and Conquer)是一种非常重要的算法设计思想。它的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子...
### 外排序(磁盘排序)之多路归并排序的简单实现 #### 知识点概述 在计算机科学领域,排序算法是数据处理的重要组成部分。对于内存足够存放所有待排序元素的情况,我们通常采用诸如快速排序、堆排序等内部排序方法...
归并排序(Merge Sort)是一种非常有效的排序算法,尤其在处理大量数据时表现出良好的稳定性和效率。 归并排序的基本思想源于分治法,即将大问题分解为小问题来解决。在归并排序中,我们首先将待排序的序列拆分为两...
以下是一个简单的归并排序算法的伪代码: ```python def merge_sort(arr): # 基线条件:如果数组只包含一个元素,它已经有序 if len(arr) return arr # 将数组分为两半 mid = len(arr) // 2 left_half = ...
归并排序(Merge Sort)是一种高效的排序算法,其主要基于分治法(Divide and Conquer)的思想。在C++中实现归并排序,我们需要理解以下几个关键知识点: 1. **分治法**:分治法是计算机科学中常用的一种算法设计...
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...
归并排序是一种高效的排序算法,基于“分治”策略。分治法是计算机科学中解决问题的一种常见方法,它将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题...
在这个场景中,我们讨论的焦点是使用 Java Swing 来实现一个排序算法的动画展示,特别是归并排序。归并排序是一种高效的、稳定的排序算法,它的基本思想是将大问题分解为小问题来解决,通过递归地将两个或更多有序数...
本项目涵盖了五种经典的排序算法:快速排序、堆排序、归并排序、插入排序和选择排序。接下来,我们将深入探讨这些算法的原理、实现及性能特点。 1. **快速排序**: 快速排序由C.A.R. Hoare在1960年提出,是一种采用...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
两阶段多路归并排序算法是一种常用于数据库管理系统中的高效排序方法。本文将深入探讨这个算法,并结合C语言的实现来阐述其工作原理。 首先,我们要理解什么是归并排序。归并排序是一种基于分治思想的排序算法,它...