交换类排序的基本思想

对待排序列记录的关键字两两进行比较，只要发现两个记录为逆序就进行交换，直到没有逆序的记录为止。

---

冒泡排序

思想：每一趟依次比较相邻两个记录的关键字大小，如果逆序就交换位置，这样一趟下来满足顺序的最大记录或者最小记录必然冒出到最顶尖，重复多趟，直至完成排序。

平均时间复杂度：O(n^2)。

稳定性：稳定。

代码：

---

快速排序

思想：从待排序列中任意选择一个记录，以该记录的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[1...n]将分割为左右两个子序列，然后分别对分割所得的两个子序列递归地进行快速排序，以此类推，直至每个子序列中只含一个记录为止。

平均时间复杂度：O(nlog2n)。注，当枢轴的选择为第一个记录或者最后一个记录的关键字时，如果待排序列有序的话，这种是最差的情况，时间复杂度为O(n^2)，为避免这种问题，可选用中间位置(low+height)/2作为枢轴。

稳定性：不稳定。

代码：