如何排序?
这一章中主要是三个比较简单的算法:冒泡排序、选择排序和插入排序。计算机程序不能像人一样通览所有的数据。它只能根据计算机的“比较”操作原理,在同一时间内对来个数据项进行比较。
这三种算法都包括如下两个步骤,这两部循环执行,直到全部数据有序为止;
1、比较两个数据项;
2、交换两个数据项,或复制其中一项。
但是,每种算法具体实现的细节有所不同。
冒泡排序
冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡排序算法在刚开始研究排序技术时时一个非常好的算法。
冒泡排序的Java代码:
public class ArrayTest { public static void main(String[] args) { //冒牌排序法 int[] a = {34,21,5,2,3,12,56,13,37,22}; for (int i = 0; i < a.length; i++) { System.out.print(a[i]+","); } System.out.println(""); for (int i = a.length-1; i >1; i--) { for (int j = 0; j < i; j++) { if(a[j]>a[j+1]){ int temp=a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (int i = 0; i < a.length; i++) { System.out.print(a[i]+","); } } } //输出: 34,21,5,2,3,12,56,13,37,22, 2,3,5,12,13,21,22,34,37,56,
这个算法的思路是要将最小的数据项放在数组的最开始(数组的下标为0),并将最大的数据项放在数组的最后(数组下标为nElems-1)。外层for循环的计数器 i 从数组的最后开始,即i等于i等于nEmels-1,没经过一次循环i减一。小标大于i的数据项都已经排好序的了。变量i在每完成一次内部循环(计数器为j)后左移一位,因此算法就不再处理那些已经排好序的数据了。
内层for循环计数器j从数组的最开始算起,即j=0,没完成一次内部循环体加一,当它等于out时结束一次循环。在内层for循环体中,数组小标为j和j+1的两个数据项进行比较,如果小标为j的数据项大于小标为j+1的数据项项,则交换两个数据项。
不变性
在许多算法中,有些条件在算法执行时时不变的。这些条件被称为不变性。这些条件被称为不变性。认识不变性对理解算法是有用的。在一定情况先他们对调试也有用;可以反复检查不变性为否为真,如果不是的话就标记出错。
在上述代码中不变性是指i右边的数据项为有序。在算法的整个运行过程中这个条件始终为真。(在第一次排序开始前,尚未排序,因为i开始时在数据项的最左边,没有数据项在i的右边。)
冒泡排序法的效率
通过分析10分数据项的数组,第一趟排序时进行了9次比较,第二趟排序进行了8次比较。如此类推,知道最后一趟进行了一次比较。对于10个数据项就是
9+8+7+6+5+4+3+2+1=45
一般来说数组中有N个数据项,则第一趟排序中有N-1次比较,第二趟中有N-2次比较,如此类推公式如下
(N-1)+(N-2)+(N-3)+…+1=N(N-1)/2
当N为10时,N*(N-1)/2等于45 (10*9/2)。
这样,算法作了约N2/2次比较(忽略减一,不会有很大的差别,特别是当N很大时)。
选择排序
待续。。。。。。
64
原文:http://my.oschina.net/u/1431757/blog/520946