首页 > 编程语言 > 详细

Java数据结构与算法(第三章简单排序)

时间:2015-10-23 00:17:56      阅读:300      评论:0      收藏:0      [点我收藏+]

如何排序?

            这一章中主要是三个比较简单的算法:冒泡排序、选择排序和插入排序。计算机程序不能像人一样通览所有的数据。它只能根据计算机的“比较”操作原理,在同一时间内对来个数据项进行比较。

            这三种算法都包括如下两个步骤,这两部循环执行,直到全部数据有序为止;

            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













Java数据结构与算法(第三章简单排序)

原文:http://my.oschina.net/u/1431757/blog/520946

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!