快速排序是怎样实现的？最坏情况怎样出现、怎样避免？
先自己想一想，再看参考要点
参考要点
- 选一个切分元素，把数组分成左边不大于它、右边不小于它的两部分，切分元素落在最终位置，再递归排序两边
- 切分时左指针向右找不小于切分元素的、右指针向左找不大于的，两者交换，相遇后把切分元素换到右指针的位置，遇到相等的元素也要停下交换，否则全部相等的数组会退化为平方级别
- 最坏情况是每次都用最小或最大的元素切分，约比较 N²/2 次、递归深度达到 N，取第一个元素作切分元素时有序数组正好如此，所以排序前先随机打乱，或者三数取中
- 改进：小数组切换到插入排序，大量重复元素时用三向切分，把等于切分元素的集中在中间不再递归，先递归较短的一侧可以保证栈深度不超过 logN