clojure的冒泡排序兑现

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)

clojure的冒泡排序兑现

相关推荐