快速排序(分治)

注:本站的大多数算法为本人手打，如果该算法有错误，或阅者有更好的代码优化建议，请评论！将立即修改！

分治快速排序
由著名的计算机科学家霍尔给出的快速分类算法，不同于归并，取一个元素值作为划分值，元素小的直接靠前，元素大的直接靠后。强于归并。
时间复杂度
事实上，在快速算法中最坏的情况下，划分元素总是最大或最小的元素，快排算法中会退化成冒泡，即:O(n^2)，但我们考虑的是平均复杂度O(nlog n)。

flag=4   4 1 5 3 6 0 7 -1
flag=4   4 1 -1 3 6 0 7 5
flag=4   4 1 -1 3 0 6 7 5
flag=4 1 -1 3 0 4 6 7 5//插入flag
flag=1  1 -1 0 3 4 6 7 5
flag=1 -1 0 1 3 4 6 7 5//插入flag
flag=6 -1 0 1 3 4 6 5 7
flag=6 -1 0 1 3 4 5 6 7//插入flag
[cpp]//假设falg为分割元素
#include <iostream>
using namespace std;
void swap(int &a,int &b)
{
 int t=a;a=b;b=t;
}
int partition(int *r,int low ,int high)
{
 int flag=r[low];//分割元素flag
 int k=low;
 while(low<high)
 {
 while(r[low]<=flag) if(low>high) break;else low++;
 while(r[high]>=flag)if(low>high) break;else high–;
 if(low>high) break;
 else swap(r[low],r[high]);
 }
 for(;k<high;k++) r[k]=r[k+1];r[high]=flag;//移位赋值将flag插入到元素
 return high;
}
void quicksort(int *r,int s,int e)
{
 if(s<e)
 {
 int flag=partition(r,s,e);
 quicksort(r,s,flag-1);
 quicksort(r,flag+1,e);
 }
}
int main()
{
 cout<<“Input the numbers of elemment:”;
 int n,i,*r;cin>>n;
 r=new int[n];
 for(i=0;i<n;i++) cin>>r[i];
 quicksort(r,0,n-1);
 for(i=0;i<n;i++) cout<<r[i]<<” “;
 cout<<endl;
 delete[] r;
 return 0;
}
运行测试:
Input the numbers of elemment:8
4 0 5 2 1 3 7 5
0 1 2 3 4 5 5 7
[/cpp]
感觉这样写代码不是最优的，正在思考,优化代码稍后会附上.