您好,登录后才能下订单哦!
这篇文章主要介绍了c++怎么样实现快速排序算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
第一、算法描述
快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法,
快速排序算法是采用分治思想的算法,算法分三个步骤
1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个、最后一个元素或中间的元素
2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边
3.对左右两个分区重复以上步骤直到所有元素都是有排序好。
第二、算法实现
/*序列划分函数*/ int partition(int a[], int p, int r) { int key = a[r];//取最后一个 int i = p - 1; for (int j = p; j < r; j++) { if (a[j] <= key) { i++; //i一直代表小于key元素的最后一个索引,当发现有比key小的a[j]时候,i+1 后交换 exchange(&a[i], &a[j]); } } exchange(&a[i + 1], &a[r]);//将key切换到中间来,左边是小于key的,右边是大于key的值。 return i + 1; } void quickSort(int a[], int p, int r) { int position = 0; if (p<r) { position = partition(a,p,r);//返回划分元素的最终位置 quickSort(a,p,position-1);//划分左边递归 quickSort(a, position + 1,r);//划分右边递归 } } void main() { int d[] = { 6,4,1,8,7,5 }; cout << "输入数组 { 6,4,1,8,7,5 } " << endl; quickSort(d, 0, 5); print_arr(d, 6); }
两个辅助函数:
void exchange(int * a, int* b) { int temp = *a; *a = *b; *b = temp; } void print_arr(int *a, int size) //打印函数 { cout << "打印数组:"; for (int i = 0; i<size; i++) //打印数组 { cout << a[i] << " "; } cout << endl << endl; }
测试输出:
第三、算法图解分析
下面我们来具体分析下程序怎么运行的,
quickSort(d, 0, 5);代表以靠最有一个元素5作为基数,
程序初始化时候p=0,r=5,i=-1,j=0,key=5
通过上图我们观察到:
1.i逐渐增加,它一直代表着小于key=5的最后一个元素,j也在主键增加,一直到key前面一个元素停止
2.此时循环到了最后一个元素7,以5为基数的循环已经结束,此时i=1,a[i+1]=6,交换6和5交换,完成本轮循环
返回i+1=2,依索引2为分界线拆分2个数组,进入递归循环,执行类似上图操作
感谢你能够认真阅读完这篇文章,希望小编分享的“c++怎么样实现快速排序算法”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。