前些日子,java网友聊排序,
谈到Java库的排序算法有双轴快排比普通快排好,
然后一个好奇,就度娘看了看原理思想,自己写着练手
QuickSort:
取一个基数,把元素划分2边,
一边小于这个基数,一边大于这个基数,
然后一直这样划分到最小,也就把所有元素排序完成了
dualPivotQuickSort:
核心思想跟上面一样,都是划分元素
不过这个有2个基数,也就是把元素划分3份
接下来直接分享学习源码:
其实,这些东西,我真心用不上
只是刚好网友聊到,自己失业没事做,陪着他玩了,
感觉这些知道下概念就行,真写都用别人封装好的
java的也写了一份,一起分享了吧
//交换2个元素
void QuickSort::swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
/**
* 快速排序的核心算法
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::qSort(int* arr, int start, int end) {
//防止无限递归
if (end > start) {
int low = start++;
int high = end;
int pivot = arr[low];
//基于pivot划分位置
while (start < end) {
if (arr[start] < pivot) {
start++;
}
else {
this->swap(arr+start, arr+end--);
}
}
//防止停止位置的值大于基数
if (arr[start] >= pivot) {
start--;
}
this->swap(arr+start, arr+low);
//继续划分更小
this->qSort(arr, low, start);
this->qSort(arr, start + 1, high);
}
}
//交换2个元素
void QuickSort::swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
/**
* 快速排序的核心算法
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::qSort(int* arr, int start, int end) {
//防止无限递归
if (end > start) {
int low = start++;
int high = end;
int pivot = arr[low];
//基于pivot划分位置
while (start < end) {
if (arr[start] < pivot) {
start++;
}
else {
this->swap(arr+start, arr+end--);
}
}
//防止停止位置的值大于基数
if (arr[start] >= pivot) {
start--;
}
this->swap(arr+start, arr+low);
//继续划分更小
this->qSort(arr, low, start);
this->qSort(arr, start + 1, high);
}
}
/**
* 双轴快速排序的核心算法
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::dualPivotQuickSort(int* arr, int start, int end) {
//如果数量太少则直接采用经典的单轴快排
if (end - start < 64) {
this->qSort(arr, start, end);
return;
}
//双轴快排核心
int low = start++;
int high = end--;
//先排序前面6个元素
this->qSort(arr, low, low + 5);
//初始化双轴的2个基数
this->swap(arr+low, arr+low + 1);
this->swap(arr+high, arr+low + 3);
int pivotLow = arr[low], pivotHigh = arr[high];
int lowIndex = low + 1, highIndex = high - 1;
//基于pivot划分位置
while (start < end) {
//小于左边基数
if (arr[start] < pivotLow) {
this->swap(arr+start++, arr+lowIndex++);
}
//大于右边基数
else if (arr[start] > pivotHigh) {
this->swap(arr+start, arr+highIndex--);
end--;
}
//位置2个基数中间
else {
start++;
}
}
//修正基数位置
--lowIndex;
if (arr[highIndex] < pivotLow) {
this->swap(arr+low, arr+highIndex);
}
else if (arr[highIndex] >= pivotHigh) {
--highIndex;
}
//继续划分更小
dualPivotQuickSort(arr, low, lowIndex);//左边
dualPivotQuickSort(arr, lowIndex + 1, highIndex);//中间
dualPivotQuickSort(arr, highIndex + 1, high);//右边
}
/**
* 双轴快速排序的核心算法
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::dualPivotQuickSort(int* arr, int start, int end) {
//如果数量太少则直接采用经典的单轴快排
if (end - start < 64) {
this->qSort(arr, start, end);
return;
}
//双轴快排核心
int low = start++;
int high = end--;
//先排序前面6个元素
this->qSort(arr, low, low + 5);
//初始化双轴的2个基数
this->swap(arr+low, arr+low + 1);
this->swap(arr+high, arr+low + 3);
int pivotLow = arr[low], pivotHigh = arr[high];
int lowIndex = low + 1, highIndex = high - 1;
//基于pivot划分位置
while (start < end) {
//小于左边基数
if (arr[start] < pivotLow) {
this->swap(arr+start++, arr+lowIndex++);
}
//大于右边基数
else if (arr[start] > pivotHigh) {
this->swap(arr+start, arr+highIndex--);
end--;
}
//位置2个基数中间
else {
start++;
}
}
//修正基数位置
--lowIndex;
if (arr[highIndex] < pivotLow) {
this->swap(arr+low, arr+highIndex);
}
else if (arr[highIndex] >= pivotHigh) {
--highIndex;
}
//继续划分更小
dualPivotQuickSort(arr, low, lowIndex);//左边
dualPivotQuickSort(arr, lowIndex + 1, highIndex);//中间
dualPivotQuickSort(arr, highIndex + 1, high);//右边
}
/**
* 双轴快速排序的核心算法_去掉递归
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::dualPivotQuickSortNoRecursion(int* arr, int start, int end) {
int indexLen = pow(log2(end - start), 2) + 8;
int current = indexLen;
int* index = new int[indexLen+1];
SORT:
//如果数量太少则直接采用经典的单轴快排
if (end - start < 64) {
this->qSort(arr, start, end);
//判断是否全部排序完成
if (current < indexLen){
start = index[++current];
end = index[++current];
goto SORT;
}
else
{
return;
}
}
//双轴快排核心
int low = start++;
int high = end--;
//先排序前面6个元素
this->qSort(arr, low, low + 5);
//初始化双轴的2个基数
this->swap(arr + low, arr + low + 1);
this->swap(arr + high, arr + low + 3);
int pivotLow = arr[low], pivotHigh = arr[high];
int lowIndex = low + 1, highIndex = high - 1;
//基于pivot划分位置
while (start < end) {
//小于左边基数
if (arr[start] < pivotLow) {
this->swap(arr + start++, arr + lowIndex++);
}
//大于右边基数
else if (arr[start] > pivotHigh) {
this->swap(arr + start, arr + highIndex--);
end--;
}
//位置2个基数中间
else {
start++;
}
}
//修正基数位置
--lowIndex;
if (arr[highIndex] < pivotLow) {
this->swap(arr + low, arr + highIndex);
}
else if (arr[highIndex] >= pivotHigh) {
--highIndex;
}
//分割位置_最大
index[current--] = high;
index[current--] = highIndex + 1;
//分割位置_中间
index[current--] = highIndex;
index[current--] = lowIndex + 1;
//分割位置_最小
end = lowIndex;
start = low;
goto SORT;
}
/**
* 双轴快速排序的核心算法_去掉递归
* @param arr 需要排序的数组
* @param start 排序的开始位置
* @param end 排序的结束位置
*/
void QuickSort::dualPivotQuickSortNoRecursion(int* arr, int start, int end) {
int indexLen = pow(log2(end - start), 2) + 8;
int current = indexLen;
int* index = new int[indexLen+1];
SORT:
//如果数量太少则直接采用经典的单轴快排
if (end - start < 64) {
this->qSort(arr, start, end);
//判断是否全部排序完成
if (current < indexLen){
start = index[++current];
end = index[++current];
goto SORT;
}
else
{
return;
}
}
//双轴快排核心
int low = start++;
int high = end--;
//先排序前面6个元素
this->qSort(arr, low, low + 5);
//初始化双轴的2个基数
this->swap(arr + low, arr + low + 1);
this->swap(arr + high, arr + low + 3);
int pivotLow = arr[low], pivotHigh = arr[high];
int lowIndex = low + 1, highIndex = high - 1;
//基于pivot划分位置
while (start < end) {
//小于左边基数
if (arr[start] < pivotLow) {
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
