title: 快速排序法(quick sort)
tags: 分治法(divide and conquer method)
grammar_cjkRuby: true
算法原理
分治法的基本思想：将原问题分解为若干个更小的与原问题相似的问题，然后递归解决各个子问题，最后再将各个子问题的解组合成原问题的解。
利用分治法可以将解决办法分为 “三步走” 战略：
(1) 在数据集中选定一个元素作为“基准”(pivot)
(2) 将所有数据集小于基准的元素放在基准左边，大于基准的元素放在基准右边，把原数据集分为两个数据集的操作叫做“分区”，分区结束后基准所在的位置也就是基准最后的位置
(3) 分别对基准左右两边的数据集进行前两个步骤，直至数据集只剩下一个数据为止
C语言实现
/***********************/
//章节：第四章
//内容：快速排序
/***********************/
#include
#include
#include
#include
void fastsort(int v[], int first, int last);
int main()
{
int i, v[10] = {1,243,43,5,6,634,434,23,12,7};
fastsort( v, 0, 9);
for(i = 0; i < 10; i++)
printf("%d ",v[i]);
return 0;
}
void fastsort(int v[], int first, int last){
int i, storeindex;
void swap(int v[], int i, int j);
if(first >= last)
return; //fewer than two ele
swap(v, last, (first + last)/2); //move partition elem
storeindex = first;
for(i = first; i <= last-1; i++)
if(v[i] <= v[last])
{
swap(v, storeindex, i);
storeindex += 1;
}
swap(v, last, storeindex);
fastsort(v, first, storeindex - 1);
fastsort(v, storeindex + 1, last);
}
/*swap:interchange v[i] and v[j]*/
void swap(int v[], int i, int j){
int temp;
temp = v[j];
v[j] = v[i];
v[i] = temp;
}
实例分析
(1)取5作为pivot，然后将其移动到最后一个位置
(2)从第一个数3到倒数第二个数5分别和pivot比较，如果小于等于pivot的数依次从前向后排
(4)将pivot 5移回两个分区中间
分治法——快速排序(quicksort)
先上代码 #include using namespace std; int partition(int a[],int low, int high) { int p ...
数据结构-栈(应用篇)之快速排序法-C和C++的实现
一.原理解析 快速排序法: 基本思路是,从第一个元素开始,把所有比它大的元素放在它后面,把所有比它小的元素放前面.然后划分它前面和后面的所有元素,分别再做快速排序,直到无法再划分为止. 在以下程序案例 ...
python 实现分治法的几个例子
分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子 ...
分治法及其python实现例子
在前面的排序算法学习中,归并排序和快速排序就是用的分治法,分治法作为三大算法之一的,有非常多的应用例子. 分治法概念 将一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题-- ...
Leetcode Lect4 二叉树中的分治法与遍历法
在这一章节的学习中,我们将要学习一个数据结构——二叉树(Binary Tree),和基于二叉树上的搜索算法. 在二叉树的搜索中,我们主要使用了分治法(Divide Conquer)来解决大部分的问题. ...
Java算法——分治法
一.基本概念 在计算机科学中,分治法是一种很重要的算法.字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简 ...
javascript的快速排序法
在排序方式中,快速是比较普遍使用的,因为其速度快. 因为其是不断的递归,而且是根据基准点的左右两边开始递归,直到数组只有一个值的时候才返回. 这个基准点是自己定的. 一般取中间,比较好理解. < ...
分治法(一)(zt)
这篇文章将讨论: 1) 分治策略的思想和理论 2) 几个分治策略的例子:合并排序,快速排序,折半查找,二叉遍历树及其相关特性. 说明:这几个例子在前面都写过了,这里又拿出来,从算法设计的策略的角度把它 ...
用分治法解决最近点对问题:python实现
最近点对问题:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小.需要说明的是理论上最近点对并不止一对,但是无论是寻找全部还是仅寻找其中之一,其原理没有区别,仅需略作改造即可 ...
随机推荐
[公告]Senparc.Weixin.MP v14.2.1 升级说明
在Senparc.Weixin.MP v14.2.1中,所有Senparc.Weixin.MP下的Container,命名空间已经从 Senparc.Weixin.MP.CommonAPIs 改为了 ...
ORA-27125: unable to create shared memory segment
平台环境 : Oracle Linux Server release 5.7 x86_64 数据库版本 : Oracle Database 10g Enterprise Edition Rel ...
Cordova webapp实战开发：(5)如何写一个Andorid下自动更新的插件？
在 中我们搭建好了开发环境,也给大家布置了调用插件的预习作业,做得如何了呢?今天我们来学一下如何自己从头建立一个And ...
UVA 753 UNIX 插头(EK网络流+Floyd传递闭包)
UNIX 插头 紫书P374 [题目链接]UNIX 插头 [题目类型]EK网络流+Floyd传递闭包 &题解: 看了书之后有那么一点懂了,但当看了刘汝佳代码后就完全明白了,感觉他代码写的好牛逼 ...
PHP爬虫抓取网页内容 (simple_html_dom.php)
使用simple_html_dom.php,下载|文档 因为抓取的只是一个网页,所以比较简单,整个网站的下次再研究,可能用Python来做爬虫会好些.
[Angular2 Router] Load Data Based on Angular 2 Route Params
You can load resource based on the url using the a combination of ActivatedRouteand Angular 2’s Http ...
java下tcp的socket连接案例
package cn.stat.p4.ipdemo; import java.io.BufferedReader; import java.io.IOException; import java.io ...
LPC2478的外部中断使用
LPC2478外部中断 2478的外部中断模型如下 也就是说,port0和2支持外部中断,EINT0-2是三个独立管脚的中断,而EINT3则是port0和2的所有中断共同拥有的向量 对于port0和2 ...
Spring中各jar包的作用
Spring AOP:Spring的面向切面编程,提供AOP(面向切面编程)的实现 Spring Aspects:Spring提供的对AspectJ框架的整合 Spring Beans:Spring ...
瞎捣鼓的code highlight
int a ; int b; public int a ;int b char c; h2 { text-align: left;}.postTitle{ background-color:#F ...
