「数据结构」八大排序(超详解 附动图 源码)(7)

动图演示：

代码如下：
// 冒泡排序void BubbleSort(int* a, int n){ int i = 0; int flag = 0; //n-1趟排序 for (i = 0; i < n-1; i ) { int j = 0; //一趟冒泡排序 for (j = 0; j < n - i - 1; j ) { if (a[j] > a[j 1]) { Swap(&a[j], &a[j 1]); flag = 1; } } //若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序 if (flag == 0) { break; } }}
冒泡排序的特性总结：
冒泡排序是一种非常容易理解的排序 时间复杂度：O(N^2) 空间复杂度：O(1) 稳定性：稳定

6.快速排序

这里是排序算法的重点了，非常重要！
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，
其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

6.1 hoare版本

具体思路是：
选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。 确定两个指针left 和right 分别从左边和右边向中间遍历数组。 如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。 然后右边的指针再走，遇到小于基准值的数就停下来。 交换left和right指针对应位置的值。 重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
这样基准值左边的所有数都比他小，而他右边的数都比他大，从而他所在的位置就是排序后的正确位置。