轻松学习快速排序（二 ）-- 快速排序优化
2021-07-10 03:05
标签：ati 源码下载 median imp swap href media ase [] 在上一篇文章轻松学习快速排序（一 ） -- 基本的快速排序中介绍了快速排序的算法，末尾提出了一个问题：例如这样的一个数组：1 10 23 6 9 10，一般来说会选择数组的第一个元素（也就是1）作为基准点，很显然以数组的第一个元素1作为基准点，本来1就是这个数组中最小的一个数，那么排序未达到预期的效果。如何来来选择这个基准点呢？一般来说，所选择的这个数最好是位于这个排序区间内所有数字的中间（也就是中位数），这样排序效果会最好。接下来，将会给出快速排序优化的两种方式：三数取中法和小区间优化。 基本思想：选择这组数据的第一个元素、中间的元素、最后一个元素，并在这三个数中取中间的元素作为基准点。比如有这样一组元素：1 10 23 6 9 10 ，第一个元素、中间的元素。最后一个元素分别为：1，23，10，那么这个中位数应该10。 选取中位数的实现代码如下： 下面的代码只不过是一些无聊的逻辑判断，如果某个数M是中位数，那么有 L
当划分的子区间的元素个数很小的时候（一般为十几个，比如说13个），使用插入排序比快速排序更加的高效。因为如果区间的元素个数为13时，此时再继续进行划分的话，区间会比较小。下面的代码是简单的插入排序的实现： 将上面两种优化结合在一起，最终完成快速排序的优化，如下的代码只给出了关键的一部分代码，完成的代码请点击相关资源下面的本文例子代码下载进行下载。 轻松学习快速排序（二 ）-- 快速排序优化 标签：ati 源码下载 median imp swap href media ase [] 原文地址：https://www.cnblogs.com/zhangfengxian/p/quick-sort-simple-optmized.html优化一：三数取中法
/** 获取从left到right间的中位数的索引 */
static int getMedianIndex(int[] arr, int left, int right) {
int mid = left + (right - left) >> 1;
if (arr[left] > arr[mid]) {
if (arr[left] arr[right]) {
return left; // mid
} else {
if (arr[right] > arr[mid]) {
return right; // mid
}
return mid; // right
}
} else {
if (arr[mid] arr[right]) {
return mid; // left
} else {
if (arr[left] > arr[right]) {
return left; // right
}
return right; // left
}
}
}
优化二：小区间优化
/** 在数组中的left到right区间进行插入排序 */
static void insertionSort(int[] arr, int left, int right) {
for (int m = left + 1; m ) {
int pos = m;
while (pos != left && arr[pos - 1] > arr[pos]) {
int temp = arr[pos - 1];
arr[pos - 1] = arr[pos];
arr[pos] = temp;
pos--;
}
}
}
最后的优化的结果
static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int insertionThreshold = 13;
// 如果此区间只有13个元素，则直接进行插入排序
if (right - left + 1 insertionThreshold) {
insertionSort(arr, left, right);
return;
}
int first = left, last = right;
// 三数取中
int mid = getMedianIndex(arr, left, right);
swap(arr, mid, first);
int base = arr[first];
//... 其余的代码省略了
}
static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
相关资源