C++ 如何在C++中实现快速排序算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22504837/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
how to implement quick sort algorithm in C++
提问by Udit Bhardwaj
here is the of quick sort algorithm from the MITOcw(Introduction To Algorithms) lecture
这是 MITOCw（算法介绍）讲座中的快速排序算法
QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
QUICKSORT(A,p,r-1)
QUICKSORT(A,r+1,q)
PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
if A[j] <= x
then i = i+1
swap A[i] with A[j]
swap A[p] with A[i]
return i
and here its C++implementation on an integer array
这是它在整数数组上的C++实现
#include <iostream>
using namespace std;
void quickSort(int *,int,int);
int partition(int *, int,int);
int main()
{
int A[10]={6,10,13,5,8,3,2,25,4,11};
int p=0,q=10;
cout<<"======Original======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
}
void quickSort(int *A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
// is reducing the value of r and hence value of q becomes
// less than p recursively. How can I separate both calls
// one for left and one for right sub array of the pivot.
quickSort(A,(r+1),q);
}
}
int partition(int *A, int p,int q)
{
int x= A[p];
int i=p;
int temp;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
temp= A[j];
A[j]=A[i];
A[i]=temp;
}
}
temp= A[p];
A[p]=A[i];
A[i]=temp;
return i;
}
code doesn't yield sorted array although the first two runs of quickSortfunction gives desired output. that is it place the first pivot element to its correct position
尽管quickSort函数的前两次运行给出了所需的输出，但代码不会产生排序的数组。就是将第一个枢轴元素放置到正确的位置
回答by tgmath
Your consideration is wrong. The value of rdoes not change, since it is given as value to the Quicksort function(not a reference).
You handle the ranges with p,qsuch that pis the first index in the range and qthe first index notin the range.
你的考虑是错误的。的值r不会改变，因为它是作为 Quicksort 函数的值给出的（不是引用）。您使用 处理范围p，q即p范围内q的第一个索引和不在范围内的第一个索引。
Thus, your calls were wrong:
因此，您的电话是错误的：
r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1]
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]
Here is the complete example. I used std::swapto change elements and ans std::vector instead of an array.
这是完整的示例。我使用std::swap来更改元素和 ans std::vector 而不是数组。
#include <iostream>
#include <vector>
using namespace std;
void quickSort(vector<int>&,int,int);
int partition(vector<int>&, int,int);
int main()
{
vector<int> A = {6,10,13,5,8,3,2,25,4,11};
int p=0;
int q=10;
cout<<"======Original======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
quickSort(A,p,q);
cout<<"======Sorted======="<<endl;
for(auto e: A)
cout<< e <<" ";
cout<< endl;
}
void quickSort(vector<int>& A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,r);
quickSort(A,r+1,q);
}
}
int partition(vector<int>& A, int p,int q)
{
int x= A[p];
int i=p;
int j;
for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
swap(A[i],A[j]);
}
}
swap(A[i],A[p]);
return i;
}
Live example: ideone
实例：ideone
回答by J. Doe
This is a template based solution. However, it works only for arrays of elements for now. If anyone has an improvement to make it generic for both arrays and STL containers, please do so.
这是一个基于模板的解决方案。但是，它目前仅适用于元素数组。如果有人有改进使其对数组和 STL 容器通用，请这样做。
template<typename T, typename compare = std::less<T>>
void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) {
if (l_idx >= r_idx)
return;
// The below is the partition block (can be made a sub function)
int left = l_idx;
int right = r_idx;
{
int pivot_idx = l_idx;
T pivot = input[pivot_idx];
while (left < right) {
while (comp(input[left], pivot))
left++;
while (comp(pivot, input[right]))
right--;
swap(input[left], input[right]);
}
swap(pivot, input[left]);
}
q_sort(input, l_idx, left, comp);
q_sort(input, left+1, r_idx, comp);
}
template<typename T, typename compare = std::less<T>>
void quick_sort(T array[], int N, compare comp = compare()) {
// This is an improvisation on the merge sort algorithm
// is in-place and works on the divide-and-conquer methodology
// Choose a pivot and find its appropriate place, such that
// All elements less than the pivot are on its left and all elements
// greater are on its right. Once found, split the porlblem into subsets
// of elements less than and greater than the pivot and recursively
// follow the process.
q_sort(array, 0, N-1, comp);
}
int main()
{
int input[] = {11, 6, 3, 21, 9, 12};
std::cout << "Before : ";
for (int i=0; i < 6; i++)
std::cout << input[i] << " ";
std::cout << std::endl;
quick_sort(input, 6);
// or
//quick_sort(input, 6, std::greater<int>());
std::cout << "After : ";
for (int i=0; i < 6; i++)
std::cout << input[i] << " ";
std::cout << std::endl;
}
回答by Rupinder Ghotra
A much easier and clean implementation, also gives you number of minimum SWAPS in for QuickSort:
一个更简单和干净的实现，还为您提供了 QuickSort 的最小 SWAPS 数量：
int quickSort(int[], int, int);
int partition(int[], int, int, int&);
int main()
{
int array[] = {4, 2, 5};
int size = sizeof(array)/sizeof(array[0]);
/*
first and last indices are passed
idea is to move lower elements to the left of the list/pivot
*/
int swaps = quickSort(array, 0, size-1);
std::cout << "Minimum Swaps are: " << swaps << std::endl;
for(int i = 0; i < size; i++)
{
std::cout << array[i] << " ";
}
}
int quickSort(int array[], int start, int end)
{
int swaps = 0;
if(start < end)
{
int pIndex = partition(array, start, end, swaps);
//after each call one number(the PIVOT) will be at its final position
swaps += quickSort(array, start, pIndex-1);
swaps += quickSort(array, pIndex+1, end);
}
return swaps;
}
int partition(int array[], int start, int end, int& swaps)
{
int pivot = array[end];
int pIndex = start;
for(int i = start; i < end; i++)
{
if(array[i] <= pivot)
{
if(pIndex != i)
{
std::swap(array[i], array[pIndex]);
swaps++;
}
pIndex++;
}
}
if(pIndex != end)
{
std::swap(array[pIndex], array[end]);
swaps++;
}
return pIndex;
}
回答by gsamaras
Since I see various answers, you could try this:
由于我看到各种答案，你可以试试这个：
#include <iostream>
void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);
using namespace std;
int main()
{
int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
int N = sizeof(test)/sizeof(int);
cout << "Size of test array :" << N << endl;
cout << "Before sorting : " << endl;
print(test, N);
quickSort(test, 0, N-1);
cout << endl << endl << "After sorting : " << endl;
print(test, N);
return 0;
}
/**
* Quicksort.
* @param a - The array to be sorted.
* @param first - The start of the sequence to be sorted.
* @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last )
{
int pivotElement;
if(first < last)
{
pivotElement = pivot(a, first, last);
quickSort(a, first, pivotElement-1);
quickSort(a, pivotElement+1, last);
}
}
/**
* Find and return the index of pivot element.
* @param a - The array.
* @param first - The start of the sequence.
* @param last - The end of the sequence.
* @return - the pivot element
*/
int pivot(int a[], int first, int last)
{
int p = first;
int pivotElement = a[first];
for(int i = first+1 ; i <= last ; i++)
{
/* If you want to sort the list in the other order, change "<=" to ">" */
if(a[i] <= pivotElement)
{
p++;
swap(a[i], a[p]);
}
}
swap(a[p], a[first]);
return p;
}
I have it in Quicksort (C++).
我在Quicksort (C++) 中有它。
