冒泡排序的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:
首先比较第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)
分享到:
相关推荐
Lacinia 纯Clojure实现的GraphQL
带语法高亮的clojure 1.4 解释器, 对学习clojure很有帮助
cljc-bloom 一个用Clojure(脚本)实现的跨平台布隆过滤器
这是Programming Clojure 电子版的 纸质版本在美国亚马逊要到2009年3月才能上架 Paperback: 200 pages Publisher: Pragmatic Bookshelf (March 15, 2009) Language: English ISBN-10: 1934356336 ISBN-13: 978-...
Clojure is an opinionated language—it doesn’t try to cover all paradigms or provide every checklist bullet-point feature. Instead it provides the features needed to solve all kinds of real-world ...
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 ...
Practical Clojure Clojure语言书籍
clojure clojure clojureclojure clojure
【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...
[Pragmatic Bookshelf] 网络应用开发 (Clojure 实现) (英文版) [Pragmatic Bookshelf] Web Development with Clojure Build Bulletproof Web Apps with Less Code (E-Book) ☆ 图书概要:☆ If the usual ...
[2013] Functional Programming Patterns in Scala and Clojure - Write Lean Programs for the JVM.(Michael Bevilacqua-Linn).[1937785475].pdf+epub.rar [2014] Clojure Cookbook - Recipes for Functional ...
Typed Clojure 保留了 Clojure 的优势,是 Clojure 的可选类型系统,也可以说是 Clojure 的一个库,改善了大量的静态类型安全检测。主要特性:从 Java 中保护你的 Clojure 程序,进行安全的互操作,正确的使用外部 ...
Clojure编程乐趣和clojure_programming.pdf两本书
一个小型遗传算法框架,用 Clojure 编写
Clojure是一种LISP风格的语言,运行在JVM上。Clojure的一大特色就是其并发机制,它支持不可变的数据结构(Clojure是来自...STM还是一个有争议的技术,还需要更好的证明自己,一个简单的办法就是访问一个JVM上的实现。
[2009] Programming Clojure.(Stuart Halloway).[1934356336].pdf [2010] Functional Programming with Clojure - Simple Concurrency on the JVM.(Tim Berglund, Matthew McCullough).[193650202X].pdf [2010] ...
Learn to handle data using sequences, reducers, and transducers in Clojure Explore the lesser known and more advanced features, constructs, and methodologies of the Clojure language and its ecosystem,...
clojure1.3.0及资料,附《Programming Clojure》,《Practical Clojure》
Clojure入门教程- Clojure – Functional Programming for the JVM中文版