189 8069 5689

c++怎么样实现快速排序算法

这篇文章主要介绍了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
两个辅助函数：
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
测试输出：
c++怎么样实现快速排序算法
第三、算法图解分析
下面我们来具体分析下程序怎么运行的，
quickSort(d, 0, 5);代表以靠最有一个元素5作为基数，
程序初始化时候p=0,r=5,i=-1,j=0,key=5
c++怎么样实现快速排序算法
通过上图我们观察到：
1.i逐渐增加，它一直代表着小于key=5的最后一个元素，j也在主键增加，一直到key前面一个元素停止
2.此时循环到了最后一个元素7，以5为基数的循环已经结束，此时i=1，a[i+1]=6,交换6和5交换，完成本轮循环
返回i+1=2，依索引2为分界线拆分2个数组，进入递归循环，执行类似上图操作
感谢你能够认真阅读完这篇文章，希望小编分享的“c++怎么样实现快速排序算法”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!
            
            
                        

            当前标题：c++怎么样实现快速排序算法            

            标题链接：http://cdxtjz.cn/article/jdpiih.html

其他资讯