排序算法1：交换排序

一、冒泡排序

谈到排序算法，首先映入脑中的便是冒泡排序，这也是我接触的第一种排序算法，的确算是一个比较经典的算法。冒泡排序的算法应该是从鱼吐泡泡的事件中启发出来的。也应该算是最容易理解的一种排序算法了

1.算法思想图解

从左到右的按照从小到大的顺序依次排列

第一次排序

第二轮排序

第三轮排序

随着比赛轮数的增加，比赛次数呈现递减趋势

2.时间复杂度

时间复杂度的算法：如果是四个数字排序的话，那第一轮排序需要进行3次，第二轮需要进行2次，第三轮需要1次，则为3+2+1次，推及到Nge数字排序的话那就是（n-1）+(n-2)+.....+1=n^2/2-n/2.根据复杂度的规则，去掉低阶项n/2,和常数系数，那么时间复杂度就是O（n^2）

3.空间复杂度

空间复杂度就是在交换元素时那个临时变量所占的内存。最优的空间复杂度为开始元素已排序即不需要进行交换，则空间复杂度为 0；最差的空间复杂度为原始元素为逆排序，则空间复杂度为 O(N);那么平均的空间复杂度为O(1)。

4.算法实现（java）

5.算法改进

看一下算法思想图解中，第二轮排序完成后已经完成了所有的排序，但是按照上面的算法实现，依然会进行第三轮比较排序，虽然单看上面的仅仅进行了最后一轮的操作，但是如果数组中的数量成百上千呢，如果数组的顺序一开始就是已经排序好了呢，那么这个耗费的时间也是不可低估的，所以要在原来算法的基础上进行改良，如下给定一个 整数型标识符 flag ,当某次外层循环中，内循环里没有发生相邻元素的交换，则表示当前数组已排序成功，直接跳出外层循环。

二、快速排序

1.算法思想及图解

（1）算法的思想

是冒泡排序的改进型。

a.在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率），然后分别从数组的两端扫描数组.

b.设两个指示标志（low指向起始位置，high指向结束位置)，首先从尾部逆序开始，如果发现有元素比该基准点的值小，就交换low和high位置的值

c.然后从前半部分正序开始扫描，如果有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到lo>=hi,

d.把基准点的值放到hi这个位置

e.使用递归方法对前半部分和后半部分进行以上步骤的排序即可。

（2）图解

第一轮排序：

然后将low和high重合前的数组和重合后数字之后的数组用递归方法进行一样的排序

注意：交换的是低位和高位的值，而不是基准值

2.时间复杂度

快速排序时间复杂度是O(NlogN).

3.算法代码实现（java）