今天完成的事情：

学习了排序的基本概念，插入排序，冒泡排序

插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

冒泡排序：依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。

 以下面5个无序的数据为例：

插入排序：

65 27 59 64 58 

第1次: 27 65 59 64 58

第2次: 27 59 65 64 58

第3次: 27 59 64 65 58

第4次: 27 58 59 64 65

冒泡排序：

假设有一个无序序列 

 { 4. 3. 1. 2, 5 }

第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。

第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。

第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。

假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。 

(1) 每趟排序过程中需要通过比较找到第 i 个小的元素。

所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。

(2) 假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。

所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。

分析:

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。

若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax = N(N-1)/2 = O(N2)

Mmax = 3N(N-1)/2 = O(N2)

冒泡排序的最坏时间复杂度为O(N2)。

因此，冒泡排序的平均时间复杂度为O(N2)。

总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。

如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程

明天计划的的事情：

继续

收获：

如上