排序算法的比较

假设存在一个数组arr[]={a[0],a[1],a[2],......,a[n]}，请按从小到大的顺序排列。

1 冒泡排序

1. 比较a[0]与a[1]：若a[0]>a[1]；则交换a[0]与a[1]，此时a[1]是两个数中最大的那个；
2. 比较a[1]与a[2]：若a[1]>a[2]；则交换a[1]与a[2]，此时a[2]是两个数中最大的那个；
3. 依次两个相邻的数比较，直到a[n-1]与a[n]相比，若a[n-1]>a[n]；则交换，否则，不变，这样a[n]就是最大的值；

举例：一轮冒泡排序的过程和结果

      4. 这样完成一轮排序，a[n]（例子中的6）已经是所有数中最大的，不再参与排序，则，剩下a[0]~a[n-1]（5~1）的n-1个数再按照1~3步骤排序。

 一轮比较需要比较（n-i）次得到该轮的最大值，总共需要比较（n-1）轮。

2 选择排序

1. a[0]与a[1]~a[n]依次进行比较，将较小值与a[0]互换，一轮比较下来，a[0]是数组中最小的数；

举例：一轮快速排序的过程和结果

    2. 再按照1.的方法完成a[1]~a[n]的排序，总共需要做（n-1)轮排序，每轮排序需要比较的次数为（n-i)。

总结：

1.  若是将数组从小到大排列，冒泡排序是比较出该轮的最大值放于未排序数组的最后一个元素的位置，下轮比较不再比较该位置以后的元素；快速排序是将该轮的最小值放于未排序元素的首个元素的位置，下轮不再比较该位置之前的元素。
2. 冒泡排序是相邻两个元素的比较；快速排序是未排序的数组元素的第一个元素与剩下的数组元素依次比较。