August 7, 2008
[算法] 分治策略：快速排序
先引用维基上的一个图，它很形象地展示了快速排序的整个过程：
快速排序的原理可参考上面的链接或任意一本算法教材，让我来讲也讲不清楚，我也是花好久才彻底看明白（基础太差了，汗），所以就贴贴代码好了，有人会说了，快排的代码网上多得很，还要你来贴干嘛。因为这些代码是我看着《算法基础》这本书上的原理和图自己琢磨出来的（完工后发现跟别人的代码惊人地雷同，汗汗汗），只有递归的终止条件那里参考了一下现成的代码，留下来当作笔记吧。
int pivot(int a[], int left_, int right_)
{
int i, j, p, k, tmp;
k = i = left_;
j = right_ + 1;
p = a[i];
while (1)
{
while (a[++i] <= p && i <right_);
while (a[--j]> p && j>= left_);
if (i <j)
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
else
break;
}
tmp = a[k];
a[k] = a[j];
a[j] = tmp;
return j;
}
void quick_sort(int a[], int left_, int right_)
{
if (left_ <right_)
{
int p = pivot(a, left_, right_);
quick_sort(a, left_, p - 1);
quick_sort(a, p + 1, right_);
}
}
int main(void)
{
int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9};
int len = sizeof(a) / sizeof(int);
quick_sort(a, 0, len - 1);
return 0;
}
vilinov at 18:25 Aug 07, 2008 ₪
貌似while(1)有点多余……
北极冰仔 at 18:29 Aug 07, 2008 ₪
@vilinov 不，如果没有这个while就不可能找出支点，你想想看。
lovea at 13:52 Oct 06, 2008 ₪
if(k != j)
{
tmp = a[k];
a[k] = a[j];
a[j] = tmp;
}
王思扬 at 20:38 Oct 20, 2008 ₪
#include
#include
using namespace std;
int Compare(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
int main()
{
int a[50000],i,n;
cin>>n;
for(i=0;i>a[i];
qsort(a, n, sizeof(int), Compare);
for(i=0;i<n;i++)
cout<<a[i]<<” “;
return 0;
}