快速排序算法是基于分治策略的一个排序算法,其基本思想是,对于输入的子数组,按以下三个步骤求解:
1 分解:选择一个基准元素,将整个数组分为大于基准元素,等于基准元素,小于基准元素的三组。基准元素在在划分的过程中确定
2 递归求解:通过递归调用快速排序算法分别对大于和小于基准元素的数组进行排序
3 合并:将递归的子数组进行合并最后成为排好序的数组
下面是程序的代码:
#include<iostream>
using namespace std;
int Partition(int a[],int p ,int r)
{
int i = p,j=r+1,sub;
int x = a[p];
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
while(true)
{
while(a[++i]<x&&j<r);
while(a[--j]>x);
if(i>=j) break;
sub = a[i];
a[i] = a[j];
a[j] =sub;
}
a[p] = a[j];
a[j] =x;
return j;
}
void QuickSort(int a[],int p,int r)
{
if(p<r)
{
int q = Partition(a,p,r);
QuickSort(a,p,q-1);//对左半段排序
QuickSort(a,q+1,r);//对右半段排序
}
}
int main()
{
int aa[4]={2,3,1,5};
QuickSort(aa,0,3);
for(int i= 0; i<4;i++)
cout<<aa[i]<<" ";
}
分享到:
相关推荐
快速排序有很多不同的算法来解决,在此我是用C++来编写这个程序的,根据快速排序的算法思想,很容易将此问题解决。还可以运用非递归的方法解决,但是我不熟练。
二分搜索算法和快速排序算法及分治策略.doc
主要介绍了Java基于分治法实现的快速排序算法,结合实例形式分析了java基于分治法的快速排序相关实现技巧,代码中备有较为详细的注释说明便于理解,需要的朋友可以参考下
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的...这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
快速排序是一种非常高效的排序算法,它的基本原理是采用分治策略。以下是快速排序的原理和实现步骤: 原理: 1、选择一个基准值。 2、通过一趟排序将待排序的序列分割成独立的两部分,其中一部分的所有数据都比另一...
算法课程实验一五种排序算法的分析比较实验目的掌握选择排序、插入排序、冒泡排序、快速排序、归并排序五种排序算法原理,并实现上述算法;
理解递归的概念 掌握设计有效算法的分治策略:分治法的基本思想 通过范例学习分治策略的算法分析及设计技巧 二分搜索技术、大整数的乘法、Strassen矩阵乘法 合并排序和快速排序
实现了快速排序的基本算法,程序可以正常运行。 其实快速排序的核心思想是分治策略,即先分解再递归求解,最后再合并。具体来说就是在待排序记录序列中选取一个记录(通常先选取第一个记录)为驱轴,其关键字设为K1...
快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个元素,但也有其他选取策略如“三数取中”等。 2. 重新排列数组,使得所有小于...
分治策略 内容: 用分治法实现一组无序序列的两路合并排序和快速排序。 要求:理解分治法的算法思想,清楚两路合并排序和快速排序算法的基本原理和实施过程,能将输入的一组无序序列排列为有序序列后输出。比较不同...
快速排序是一种高效的排序算法,基于分治策略。其基本步骤如下: 1. 选择一个基准元素(pivot),通常选择数组的第一个元素或者最后一个元素,但也有其他选取策略如“三数取中”等。 2. 重新排列数组,使得所有小于...
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 算法步骤: 1 从数列中挑出一个元素,称为 “基准”(pivot), 2 重新排序数列,所有元素比基准值小的摆放在...
快速排序算法来源于分治法的思想策略,这里我们将来为大家简单解析一下快速排序的算法思想及Python版快速排序的实现示例:
快速排序是一种采用分治法策略的高效排序算法,其基本思想是选取一个基准元素,将数组分为两部分,使得一部分的元素都小于基准元素,另一部分的元素都大于基准元素。 快速排序过程 快速排序的过程包括选取基准、分区...
阶乘函数,Fibonacci数列,基于递归的插入排序,时间递归方程和复杂性分析,整数划分问题,Hanoi塔问题,分治法的适用条件,二分搜索算法,大整数的乘法,Strassen矩阵乘法, 棋盘覆盖,合并排序,快速排序
快速排序是对冒泡排序的一种改进,采用了一种分治的策略。 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别...
递归算法和分治算法的大概内容,有兴趣的可以看看!