实现混合插入和快速排序C++
实现混合插入和快速排序C++
提问于 2018-06-09 03:50:39
我正在尝试实现一种混合插入和快速排序。任务是对大的向量使用快速排序，当向量变得小于某个指定值(交叉点)时，算法应该切换到插入排序。到目前为止，我已经有了这段代码，但它不能对向量进行排序，我不知道为什么。任何帮助都将不胜感激。谢谢!
#include <iostream>
#include "console.h"
#include "vector.h" // for Vector
#include <cmath>
using namespace std;
/* Partition for quicksort algorithm */
int partition(Vector<int> &vec, int start, int end){
int lh = start +1;
int rh = end;
int pivotVal = vec[start];
while (true){
while (lh<rh && vec[lh]<pivotVal) lh++;
while (rh>lh && vec[rh]>=pivotVal) rh--;
if (lh==rh) break;
swap(vec[lh], vec[rh]);
}
if (pivotVal<vec[lh]) return start;
swap(vec[start], vec[lh]);
return lh;
}
/* Regular quicksort */
void quickSort(Vector<int> &vec, int start, int end){
if(start<end){
int pivotIndex = partition(vec, start, end);
quickSort(vec, start, pivotIndex-1);
quickSort(vec, pivotIndex+1, end);
}
}
/* Insertion sort algorithm */
void insertionSort(Vector<int> &vec, int start, int end){
int size = vec.size();
for (int i=start; i<end; i++){
int j=i;
while (j>start && vec[j-1]>vec[j]){
swap(vec[j-1], vec[j]);
j--;
}
}
}
/* Hybrid quicksort & insertion sort, as soon as the part of the vector to
sort becomes less than the crossover value, the algorithm switches to
insertion sort, otherwise it
uses quicksort */
void hybridSort(Vector<int> &vec, int start, int end, int crossover){
if(start < end){
if (end-start <= crossover){
insertionSort(vec, start, end);
} else {
int pivotIndex = partition(vec, start, end);
hybridSort(vec, start, pivotIndex-1, crossover);
hybridSort(vec, pivotIndex+1, end, crossover);
}
}
}
int main() {
Vector<int> vec {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 14, 39, 30, 83, 92, 41};
int end = vec.size()-1;
hybridSort(vec, 0, end, 4);
cout << vec.toString() <<endl;
return 0;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-09 04:37:35
我重写了partition
int partition(Vector<int>& vec, int start, int end) {
int pivot = start;
for(int i = start + 1; i <= end; ++i) {
if(vec[i] < vec[pivot]) {
swap(vec[pivot + 1], vec[i]);
swap(vec[pivot], vec[pivot + 1]);
++pivot;
}
}
return pivot;
}在insertionSort中也有一个bug。应该是i <= end而不是i < end。以下是已修复的版本：
void insertionSort(Vector<int>& vec, int start, int end) {
for(int i = start; i <= end; i++) {
int j = i;
while(j > start && vec[j-1] > vec[j]) {
swap(vec[j-1], vec[j]);
j--;
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50767557
复制相关文章
相似问题