Open MicroKibaco opened 3 years ago
固定基准元，一般选取中间值或头部值或尾部值。如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时或部分有序，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，数组全部有序时，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为O(n^2)。所以此种方式要慎用。
三数取中，一般是分别取出数组的头部元素，尾部元素和中部元素， 在这三个数中取出中位数，作为基准元素。最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形。（简单来说，就是随机取三个数，取中位数）。
基准取头法
固定基准元，一般选取中间值或头部值或尾部值。如果输入序列是随机的，处理时间是可以接受的。如果数组已经有序时或部分有序，此时的分割就是一个非常不好的分割。因为每次划分只能使待排序序列减一，数组全部有序时，此时为最坏情况，快速排序沦为冒泡排序，时间复杂度为O(n^2)。所以此种方式要慎用。
基准取中法
三数取中，一般是分别取出数组的头部元素，尾部元素和中部元素， 在这三个数中取出中位数，作为基准元素。最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形。（简单来说，就是随机取三个数，取中位数）。