首页 / 算法 / C++实现快速排序(原理分析+源代码)
C++实现快速排序(原理分析+源代码)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++实现快速排序(原理分析+源代码),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2710字,纯文字阅读大概需要4分钟。
内容图文
![C++实现快速排序(原理分析+源代码)](/upload/InfoBanner/zyjiaocheng/620/ee6b22df80f04494aefda2279dc696ff.jpg)
快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序是一种不稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
以一个数组作为示例,取区间第一个数为基准数。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
初始时,i = 0; j =9; X = a[i] = 72
由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3];j--;
数组变为:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
i = 3; j =7; X=72
再重复上面的步骤,先从后向前找,再从前向后找。
从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;
从i开始向后找,当i=5时,由于i==j退出。
此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。
数组变为:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
代码如下:
#include<iostream>
using namespace std;
void quickSort(int a[],int,int);
int main()
{
int array[]={34,65,12,43,67,5,78,10,3,70},k;
int len=sizeof(array)/sizeof(int);
cout<<"The orginal arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
quickSort(array,0,len-1);
cout<<"The sorted arrayare:"<<endl;
for(k=0;k<len;k++)
cout<<array[k]<<",";
cout<<endl;
system("pause");
return 0;
}
void quickSort(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
?
原文地址:http://blog.sina.com.cn/s/blog_5c5bc9070100y4zv.html
内容总结
以上是互联网集市为您收集整理的C++实现快速排序(原理分析+源代码)全部内容,希望文章能够帮你解决C++实现快速排序(原理分析+源代码)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。