如何用C实现快速排序算法++

本文介绍了如何用C实现快速排序算法++的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这里是从MITOcw快速排序算法（ 算法导论 ）演讲

here is the of quick sort algorithm from the MITOcw(Introduction To Algorithms ) lecture

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

和这里的 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不会产生有序阵列虽然快速排序函数提供所需的输出的前两个运行。这是它的第一个枢轴元件放置到正确的位置

code doesn't yield sorted array although the first two runs of quickSort function gives desired output. that is it place the first pivot element to its correct position

推荐答案

您的考虑是错误的。值研究并没有改变，因为它是作为价值的快速排序功能（不是一个引用）。 你处​​理与 P ，①的范围内，这样 P 在范围内第一个索引，而①的范围内第一个指数不

Your consideration is wrong. The value of r does not change, since it is given as value to the Quicksort function(not a reference). You handle the ranges with p,q such that p is the first index in the range and q the first index not in the range.

因此​​，你的电话是错误的：

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]

下面是完整的例子。我用的的std ::交换的改变元素 ANS的std ::向量，而不是一个数组。

Here is the complete example. I used std::swap to change elements and ans std::vector instead of an array.

#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; }

活生生的例子： ideone