`
songry
  • 浏览: 84607 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

clojure的冒泡排序实现

阅读更多

    冒泡排序的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:

首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和 第3个数,将小数放前,大数放后

,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。

在第二趟:仍从第一对数 开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),

将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已 经是最大的),第二趟结束,

在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,

直至最终完成排序。(概念来自百度百科)

  由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

    从概念中我们可以发现,冒泡排序实际上被分为两个过程,一个是针对集合的交换循环,做的是两两比较,

小数置前,大数置后;交换循环的结果只是保证了集合中最后一个元素是最大数,

所以我们还需要另外一个排序循环来对除了最大数之外剩余的元素进行再一次的交换循环,

直到所有的元素都排序完成。

    在排序过程中,执行完一次排序后,程序无法判断是否完成排序,为了解决这一不足,

可设置一个标志单元isChanged,如果在交换循环中有对元素位置的交换操作,则isChanged为true,

表示被排序的表示是一个无序的集合。在每一排序开始时,检查此标志,若此标志为false,

则结束排序;否则进行排序。

    首先我们看看java版本的实现,代码来自百度百科:

public static void sort(Comparable[] data) {
		// 数组长度
		int len = data.length;
		for (int i = 0; i < len - 1; i++) {//排序循环
			// 临时变量
			Comparable temp = null;
			// 交换标志,false表示未交换
			boolean isExchanged = false;
			for (int j = len - 1; j > i; j--) {//交换循环
				// 如果data[j]小于data[j - 1],交换
				if (data[j].compareTo(data[j - 1]) < 0) {
					temp = data[j];
					data[j] = data[j - 1];
					data[j - 1] = temp;
					// 发生了交换,故将交换标志置为真
					isExchanged = true;
				}// end if
			}// end for
			// 本趟排序未发生交换,提前终止算法,提高效率
			if (!isExchanged) {
				break;
			}// end if
		}// end for
	}// end sort

	public static void main(String[] args) {
		// 在JDK1.5版本以上,基本数据类型可以自动装箱
		// int,double等基本类型的包装类已实现了Comparable接口
		Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
		sort(c);
		for (Comparable data : c) {
			System.out.println(data);
		}	
	}

 然后我们看看clojure的代码:

(defn step             ;交换循环
     [opr arr changed]  ;changed就是标志位
     (if (< (count arr) 2) ;集合中只剩最后一个元素,代表在一个交换循环中已经将本次的冒泡完成了
       [arr (not changed)] ;将交换循环中是否有元素改变位置的布尔值反转作为排序是否结束的标识
                             ;如果有元素改变了位置即changed为true,则说明排序尚未结束
        (let [[ x1 x2 & other] arr
             first-smaller (opr x1 x2);判断是否需要元素改变位置
             is-changed (or changed (not first-smaller));判断之前和本次交换循环中是否
                                                            ;有元素改变了位置
             [smaller larger] (if first-smaller [x1 x2] [x2 x1]);进行位置交换
             [result is-sorted] (step opr (cons larger other) is-changed)];将冒泡的元素
                             ;和剩余的元素一起进入下一轮循环,并将之前和此次循环中是否有
                             ;元素改变位置的标识传递下去
              [(cons smaller result) is-sorted])))
(defn maopao-sort    ;排序循环
     ([arr] (maopao-sort <= arr))
     ([opr arr]
     (let [[result is-sorted] (step opr arr false)]
       (if is-sorted
         result
         (recur opr result)))))
 (maopao-sort [4,1,9,2,8,5])
=>(1 2 4 5 8 9)
 (maopao-sort > [4,1,9,2,8,5])
=> (9 8 5 4 2 1)

    这仅仅是代码演示而已,如果真要排序,如下即可:

(sort [2 1 4 5 8 9])
=> (1 2 4 5 8 9)
 (sort > [2 1 4 5 8 9])
=>(9 8 5 4 2 1)
 

 

0
0
分享到:
评论

相关推荐

    Lacinia纯Clojure实现的GraphQL

    【Lacinia:纯Clojure实现的GraphQL解析器】 在当今的Web开发中,GraphQL作为一种强大的数据查询语言,已经越来越受到开发者的欢迎。它提供了一种高效、灵活的方式来获取API数据,允许客户端指定他们需要什么数据,...

    clojure 解释程序

    带语法高亮的clojure 1.4 解释器, 对学习clojure很有帮助

    在 Clojure中实现遗传算法的框架_Clojure_代码_下载

    在Clojure中实现遗传算法的框架是一个有趣且富有挑战性的任务,因为Clojure是一种功能编程语言,它提供了独特的视角和工具来处理这类问题。遗传算法(Genetic Algorithms, GA)是一种模拟自然选择和遗传学原理的优化...

    clj-sorting-algorithms:Clojure中实现的排序算法

    在这个名为"clj-sorting-algorithms"的项目中,开发者提供了一系列经典的排序算法实现,旨在展示Clojure语言在处理这类问题时的独特优势。下面我们将深入探讨这些排序算法以及它们在Clojure中的实现。** ### 1. ...

    Clojure编程乐趣]+clojure_programming.pdf

    这种性质使得Clojure代码能够操作自身,实现自我修改,增加了代码的灵活性。同时,Clojure提供了强大的映射(map)、序列(sequence)和集合(set)操作,以及高阶函数,如`map`、`filter`和`reduce`,这些都极大地...

    Practical Clojure.pdf

    这是因为Clojure内部实现了高级别的并发抽象,例如软件事务内存(STM)和其他并发原语。 不可变性是Clojure中的另一个核心概念。在Clojure中,数据结构默认是不可变的,这意味着一旦创建了数据结构,就无法更改。这...

    Clojure Data Structures and Algorithms Cookbook

    - 提供多种排序算法的具体实现,如冒泡排序、插入排序、选择排序等。 - 对比不同排序算法的时间复杂度和空间复杂度。 5. **第5章:搜索算法** - 讲解深度优先搜索、广度优先搜索等搜索算法。 - 分析算法在实际...

    Python-cljcbloom一个用Clojure脚本实现的跨平台布隆过滤器

    Python-cljcbloom项目是基于Clojure语言实现的一个跨平台的布隆过滤器库,它允许Python开发者利用Clojure的优势来处理大规模数据的去重问题。 1. **布隆过滤器原理**: 布隆过滤器由一块位数组和几个独立的哈希...

    clojure1.3.0及资料

    这个文件可能是Storm的Clojure实现或相关工具,对于进行大规模实时数据处理的开发者来说很有价值。 综上所述,这个压缩包包含了一系列资源,可以帮助开发者深入理解Clojure语言,尤其是1.3.0版本及其后续演进。书籍...

    Programming Clojure 英文电子版

    - **Concurrency**:Clojure通过软件事务内存(Software Transactional Memory, STM)实现了安全和高效的并发处理。STM允许开发者以一种简单直观的方式处理并发问题,避免了传统锁机制带来的复杂性和潜在死锁问题。 ...

    Clojure入门教程- Clojure – Functional Programming for the JVM中文版

    - **软件事务内存(STM)**: Clojure通过STM机制实现了高度并发的编程模型,它允许开发者以事务的方式更新共享状态,从而简化了并发编程的复杂度。 #### 六、学习资源与社区 - **官方文档**: Clojure官方网站提供了...

    clojure电子书

    《Clojure电子书》集合包含了三本关于Clojure编程的重要书籍和一个Leiningen的Windows安装程序,这对于学习和深入理解Clojure语言至关重要。Clojure是一种基于Lisp的函数式编程语言,它运行在Java虚拟机(JVM)上,...

    Clojure Data Analysis Cookbook

    - **机器学习基础**:介绍如何使用 Clojure 实现简单的机器学习算法,如线性回归、决策树等。 3. **实践篇**:通过具体的项目案例来巩固前面所学的知识。 - **文本分析**:使用自然语言处理技术进行文本挖掘,如...

    Professional.Clojure.1119267277

    Clear, practical Clojure for the professional programmer Professional Clojure is the experienced developer's guide to functional programming using the Clojure language. Designed specifically to meet ...

    Clojure电子书合集1(12本)

    [2009] Programming Clojure.(Stuart Halloway).[1934356336].pdf [2010] Functional Programming with Clojure - Simple Concurrency on the JVM.(Tim Berglund, Matthew McCullough).[193650202X].pdf [2010] ...

    clojure相关书籍1

    【1】[Clojure编程乐趣](The Joy of Clojure).pdf 【2】Clojure – Functional Programming for the JVM中文版.pdf 【3】Clojure Cookbook.pdf 【4】Clojure Data Analysis Cookbook.pdf 【5】clojure Hand book...

    programming-clojure-3rd

    《Programming Clojure 第三版》是一本深入探讨Clojure编程语言的专业书籍,旨在帮助开发者全面理解和掌握这门基于Lisp的现代函数式编程语言。Clojure是由Rich Hickey设计的,它运行在Java虚拟机(JVM)上,同时也...

Global site tag (gtag.js) - Google Analytics