首页 > 代码库 > 经典算法系列一-快速排序
经典算法系列一-快速排序
写一个系列的经典算法，共同学习！
1.快速排序
基本思想：
1.先从数列中取出一个数作为基准数。
2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步，直到各区间只有一个数。
在网上看到一篇博客，把快速排序命名为 挖坑填数+分治法，感觉很有道理，所以等会程序就按这两部来写。
先说说挖坑填数的思想：
1.i=L;j=R; 将基数挖出形成第一个坑a[i].
2.j--由后向前找出比它的小的数，找到后挖出此数填前一个坑a[i].
3.i++由前向后找出比它大的数，找到后挖出此数填前一个坑a[j].
4.重复2，3步骤直到i==j,将基数填入a[i]中。
代码实现
int Adjust(int a[],int i,int j)
{
int x = a[i];
while(i<j)
{
while(i<j && x <= a[j])
j--;
if(i<j)
{
a[i] = a[j];
i++;
}
while(i<j && x >= a[i])
i++;
if(i<j)
{
a[j] = a[i];
j--;
}
}
a[i] = x;
return i;
}
int x = a[i];
while(i<j)
{
while(i<j && x <= a[j])
j--;
if(i<j)
{
a[i] = a[j];
i++;
}
while(i<j && x >= a[i])
i++;
if(i<j)
{
a[j] = a[i];
j--;
}
}
a[i] = x;
return i;
}
分治：
int quick_sort(int a[],int l,int r)
{
int i;
if(l < r)
{
i = Adjust(a,l,r);
quick_sort(a,l,i-1);
quick_sort(a,i+1,r);
}
}
int i;
if(l < r)
{
i = Adjust(a,l,r);
quick_sort(a,l,i-1);
quick_sort(a,i+1,r);
}
}
这样分两步就把快速排序解决了，挺简单的。当然这样写有点麻烦，可以简单一些：
int quick(int a[],int l,int r)
{
int i = l;
int j = r;
if(l < r)
{
int x = a[i];
while(i<j)
{
while(i<j && x <= a[j])
j--;
if(i<j)
{
a[i] = a[j];
i++;
}
while(i<j && x >= a[i])
i++;
if(i<j)
{
a[j] = a[i];
j--;
}
}
a[i] = x;
quick(a,l,i-1);
quick(a,i+1,r);
}
}
int i = l;
int j = r;
if(l < r)
{
int x = a[i];
while(i<j)
{
while(i<j && x <= a[j])
j--;
if(i<j)
{
a[i] = a[j];
i++;
}
while(i<j && x >= a[i])
i++;
if(i<j)
{
a[j] = a[i];
j--;
}
}
a[i] = x;
quick(a,l,i-1);
quick(a,i+1,r);
}
}
http://www.cnblogs.com/my-life/category/425361.html
经典算法系列一-快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。