Java数据结构和算法 - 简单排序

时间:2023-12-05 11:59:38

Q: 冒泡排序?

A: 
1) 比较相邻的元素。如果第一个比第二个大,就交换它们两个; 
2) 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数; 
3) 针对所有的元素重复以上的步骤,除了最后一个。因此总共有N - 1 趟; 
4) 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

Q: 冒泡排序的Java代码?

A: 示例: BubbleSort.java, BubbleSortTest.java

Q: 冒泡排序的不变性?

A: 在许多算法中,有些条件在算法执行时是不变的,这些条件被称为不变性。识别不变性对算法很有用,在一定情况下对调试也很有用:可以反复地检查不变性是否为真,如果不是的话就标记出错。

A: 在BubbleSort.java程序中,不变性是指i右边的所有数据项为有序。在算法的整个运行过程中这个条件始终为真。(在第一趟排序开始前,尚未排序,因为i开始时在数据项的最右边,没有数据项在i的右边。)

Q: 冒泡排序的效率?

A: 一般来说,数组中有N个数据项,则第一趟排序中有N - 1次比较,第二趟中有N - 2次,以此类推,总共用N - 1趟。这种序列的求和公式如下:

(N - 1) + (N - 2) + ... + 1 = (N - 1) * N / 2

这样算法大约N/ 2次比较,如果数据是随机的,那么大概有一半数据需要交换,则交换的次数为N2 / 4。因此交换和比较操作次数都和N2成正比。由于常数不算在大O表示法中,可以忽略2和4,并且认为冒泡排序运行需要O(N2)时间级别。

无论何时,只要看到一个循环嵌套在另一个循环里,都可以怀疑这个算法的运行时间为O(N2)级。

Q: 选择排序?

A: 选择排序改进了冒泡排序,将必要的交换次数从O(N2)较少到O(N),不幸的是比较次数仍保持O(N2)。然而这也是一个重大的改进,因为大量的记录在内存中移动,使得交换所需CPU时间比比较所需的CPU时间多。(一般来说,Java语言不是这种情况,Java只是改变了引用位置,而实际对象的位置并没有发生改变。)

Q: 选择排序的Java代码?

A: 示例: SelectSort.java, SelectSortTest.java

Q: 选择排序的不变性?

A: 在SelectSort.java程序中,下标小于或等于i的位置的数据项总是有序的。

Q: 选择排序的效率?

A: 选择排序和冒泡排序执行了相同次数的比较:N * (N - 1) / 2。然而交换次数,最好情况是,已经有序交换0次,最坏情况交换n-1次。

A: 当N值较大时,比较次数是主要的,所以结论是选择排序和冒泡排序一样运行了O(N2)时间,但是选择排序无疑更快,因为它进行的交换少的多。

A: 当N值较小时,特别如果交换的时间级比比较的时间级大的多时,选择排序实际上是相当快的。

Q: 插入排序?

A: 在大多数情况下,插入排序算法是本篇描述简单排序算法中最快的一种,虽然插入排序算法仍然需要O(N2)的时间,但是在一般情况下,它要比冒泡排序快一倍,比选择排序还要快一点。 尽管它比冒泡排序和选择排序算法要麻烦一些,但它并不复杂。

Q: 插入排序的Java代码?

A: 示例: InsertSort.java, InsertSortTest.java

Q: 插入排序的不变性

A: 在每趟结束时,在将tmp位置的项插入后,比i变量下标小的数据项都是局部有序的。

Q: 插入排序的效率?

A: 在第一趟排序中,它最多比较一次,第二趟最多比较两次,以此类推,最后一趟最多比较N - 1次,因此有最坏的情况为1 + 2 + 3 + ... + (N - 1) = N * (N - 1) / 2。

A: 然而,因为在每一项排序发现插入点之前,平均只有一半在进行比较,因此我们还要除以2,即N * (N - 1) / 4。

A: 对于已经有序的数据来说,插入排序要好的多。当数据有序时,while循环循环的条件总是假,所以它变成了外部循环的简单语句,执行了N - 1次,在这种情况下,算法运行只需要O(N)的时间。

Q: 给对象进行排序?

A: 为简单起见,前面应用排序算法使用基本数据类型long,但是实际场景中却更多地应用对象的排序,因此下面的程序,是对一组Person对象进行排序的代码。

示例: ObjectArray.java, ObjectArrayTest.java

Q: 几种简单排序之间的比较?

A: 除非手边没有算法书可参考,一般情况下几乎不太使用冒泡排序。它过于简单,以至于可以毫不费力地写出来,然而当数据量很小的时候它会有些应用价值。

A: 选择排序虽然把交换次数降到了最低,但比较的次数仍然很大。当数据量很小,并且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序。

A: 在大多数情况下,假设当数据量比较小或基本有序时,插入排序算法是三种简单排序算法中最好的选择。

A: 除了在速度方便比较排序算法外,还有一种对各种算法的衡量标准是算法需要的内存空间有多大。本篇的三种算法除了初始化数组外几乎不需要其他内存的空间,只是需要一个额外的变量来暂时存储交换时的数据项。

A: 下面的示例是对100万条long数据进行升序排序,数据源是随机、降序和升序的数据集合。表格给出了每个算法的执行的时间,单位是纳秒。

排序算法 随机 降序 升序
冒泡排序 16,596,040,573 892,914,054,225 2,464,119,746
选择排序 4,398,524,493 485,797,197,595 4,441,700,179
插入排序 1,620,718,024 420,773,500,477 5,189,851

示例: LongArray.java, LongArrayTest.java

 

Q: 参考?

    1. 《Java数据结构和算法》Robert Lafore 著,第3章 - 简单排序
    2. 冒泡排序

    3. 选择排序

    4. 插入排序