《Java数据结构和算法》- 简单排序
BitTigerio 2018-03-22
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
这样算法大约N2/ 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数据进行升序排序，数据源是随机、降序和升序的数据集合。表格给出了每个算法的执行的时间，单位是纳秒。
| 排序算法 | 随机 | 降序 | 升序 |
|---|---|---|---|
| 冒泡排序 | 892,914,054,225 | 2,464,119,746 | |
| 选择排序 | 485,797,197,595 | 4,441,700,179 | |
| 插入排序 | 420,773,500,477 | 5,189,851 |
示例：LongArray.java, LongArrayTest.java
Q: 参考?
- 《Java数据结构和算法》Robert Lafore 著，第3章 - 简单排序
冒泡排序
选择排序
- 插入排序
相关推荐
# 第三题：使用python实现冒泡排序def BubbleSort: long = len for i in range: for j in range: if list[i] < list[j]: