一.计算两个点的最小路径(Dijkstra算法)
二.计算图上任意点到其他点的最小路径(Floyd算法)
三.最小生成树算法
四.贪心算法
五.排序算法
六.查找算法
一.计算两个点的最小路径(Dijkstra算法)
1.png
预备知识：
- 图在数据结构中的一种表示方法：
使用两个数组表示。一个一维数组表示节点，一个二维数组表示节点之间的直接权重，如果没有直接权重可以使用♾表示。
eg:上图的数据结构表示为
#define MaxPath 65535
int point[9]={0,1,2,3,4,5,6,7,8};
int path[9][9]={
{0,1,5,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath},
{1,0,3,7,5,MaxPath,MaxPath,MaxPath,MaxPath},
{5,3,0,MaxPath,1,7,MaxPath,MaxPath,MaxPath},
{MaxPath,7,MaxPath,0,2,MaxPath,3,MaxPath,MaxPath},
{MaxPath,5,1,2,0,3,6,9,MaxPath},
{MaxPath,MaxPath,7,MaxPath,3,0,MaxPath,5,MaxPath},
{MaxPath,MaxPath,MaxPath,3,6,MaxPath,0,2,7},
{MaxPath,MaxPath,MaxPath,MaxPath,9,5,2,0,4},
{MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,7,4,0},
};
- 无向图中，每个点的相邻路径覆盖所有路径的2倍(一来一回相同)。
具体思路：
Dijkstra算法计算两个点的最短距离其实是计算出这个点到每个点的最短距离。
然后通过既定的最短距离点再去计算未定的最短距离点，直到所有点都既定。
那么怎么求得既定点最短距离呢？
比如下图：
2.png
同1相邻的点是2和3，如果1-2的权值小于1-3的权值，那么1-2的最短路径就是1-2，权值就是1-2的权值，因为1如果通过其他路径到2必须经过3，就一定比1-2的路径长。
所以，1-2就是被既定下来的最短路径和点。同理，1,2相邻的所有路径最短权值的点就是下一个最短路径的既定点，比如1-3=5，1-2-3=4，1-2-4=6，1-2-5=7，那么1-2-3=4就是1-3的最短路径，3就是既定点。然后把1，2，3作为既定点再去寻找其他未既定点。
其中有个细节就是，不断寻找新的路径的时候，更新最短路径数组。
比如v0到各个顶点的最短路径初始 {0,1,5,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath}，没有相邻用MaxPath表示。
1-2既定后，更新数组为{0,1,4,6,7,MaxPath,MaxPath,MaxPath,MaxPath}。
//定义该图
int point[9]={0,1,2,3,4,5,6,7,8};
int path[9][9]={
{0,1,5,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath},
{1,0,3,7,5,MaxPath,MaxPath,MaxPath,MaxPath},
{5,3,0,MaxPath,1,7,MaxPath,MaxPath,MaxPath},
{MaxPath,7,MaxPath,0,2,MaxPath,3,MaxPath,MaxPath},
{MaxPath,5,1,2,0,3,6,9,MaxPath},
{MaxPath,MaxPath,7,MaxPath,3,0,MaxPath,5,MaxPath},
{MaxPath,MaxPath,MaxPath,3,6,MaxPath,0,2,7},
{MaxPath,MaxPath,MaxPath,MaxPath,9,5,2,0,4},
{MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,7,4,0},
};
//表示是否是既定点，1表示既定 0 表示未既定，默认都未既定
int final[9]={0};
//v0到每个点的最短距离数组，默认都是最大值
int minDis[9]={MaxPath};
//每个点最短距离的前驱节点数组
int minDisPath[9]={0};
//初始化最短距离
for(int i=0;i<9;i++)
{
minDis[i]=path[0][i];
}
//v0-v0=0，v0本身就是既定点
final[0]=1;
for (int i=0;i<9;i++) {
//确定既定点
int minPath=MaxPath;
int index=0;
for (int j=0;j<9;j++) {
if(!final[j]&&minDis[j]<minPath)
{
minPath=minDis[j];
index=j;
}
}
final[index]=1;
//更新最短路径
for (int k=0;k<9;k++) {
if(!final[k]&&path[index][k]+minPath<minDis[k])
{
minDis[k]=path[index][k]+minPath;
minDisPath[k]=index;
}
}
}
for (int i=0;i<9;i++) {
printf("v0到v%d最短距离是%d\n",i,minDis[i]);
}
printf("每个节点的前驱路径:");
for (int i=0;i<9;i++) {
printf("%d",minDisPath[i]);
}
/*
每个节点的前驱路径:001424367
eg:v0-v8最短路径 v8前驱节点是 minDisPath[8]->7 也就是v8前驱是v7
v7前驱节点是 minDisPath[7]->6 也就是v7前驱是v6
v6前驱节点是 minDisPath[6]->3 也就是v7前驱是v3
v3前驱节点是 minDisPath[3]->4 也就是v3前驱是v4
v4前驱节点是 minDisPath[4]->2 也就是v4前驱是v2
v2前驱节点是 minDisPath[2]->1 也就是v2前驱是v1
v1前驱节点是 minDisPath[1]->0 也就是v1前驱是v0
最短路径：v0-v1-v2-v4-v3-v6-v7
*/
二.计算图上任意点到其他点的最小路径(Floyd算法)
使用Dijkstra算法解决该问题就是执行N次该算法。
解决该问题的办法还可以使用Floyd算法，优雅的一批。
算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
//定义该图
int point[9]={0,1,2,3,4,5,6,7,8};
int path[9][9]={
{0,1,5,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath},
{1,0,3,7,5,MaxPath,MaxPath,MaxPath,MaxPath},
{5,3,0,MaxPath,1,7,MaxPath,MaxPath,MaxPath},
{MaxPath,7,MaxPath,0,2,MaxPath,3,MaxPath,MaxPath},
{MaxPath,5,1,2,0,3,6,9,MaxPath},
{MaxPath,MaxPath,7,MaxPath,3,0,MaxPath,5,MaxPath},
{MaxPath,MaxPath,MaxPath,3,6,MaxPath,0,2,7},
{MaxPath,MaxPath,MaxPath,MaxPath,9,5,2,0,4},
{MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,7,4,0},
};
//三层循环不断更新点对点最短距离
for(int k=0;k<9;k++)
{
for(int v=0;v<9;v++)
{
for(int m=0;m<9;m++)
{
if(path[v][m]>path[v][k]+path[k][m])
{
path[v][m]=path[v][k]+path[k][m];
}
}
}
}
//打印最短距离二维数组
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
printf("%d ",path[i][j]);
}
printf("\n");
}
三.最小生成树算法
N个节点的连通图中，通过N-1条边连接贯穿每个节点的最小权值子图，就是最小生成树。
算法思路：
1.取图中任意一个节点，把这个节点放入集合A中；
2.然后在那些一个端点在A集合中，另一个端点不在A集合中的边，找到权值最小的，并把这条边和不在A的端点包含进入A集合中；
3.如此继续下去，每次把一条边和一个节点放入A集合中，直到把所有节点都放入A集合中。
4.这样A集合的节点和边就构成了最小生成树。
eg：
之前这个图最小生成树就是红色路径。
1.png
//定义该图
int point[9]={0,1,2,3,4,5,6,7,8};
int path[9][9]={
{0,1,5,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath},
{1,0,3,7,5,MaxPath,MaxPath,MaxPath,MaxPath},
{5,3,0,MaxPath,1,7,MaxPath,MaxPath,MaxPath},
{MaxPath,7,MaxPath,0,2,MaxPath,3,MaxPath,MaxPath},
{MaxPath,5,1,2,0,3,6,9,MaxPath},
{MaxPath,MaxPath,7,MaxPath,3,0,MaxPath,5,MaxPath},
{MaxPath,MaxPath,MaxPath,3,6,MaxPath,0,2,7},
{MaxPath,MaxPath,MaxPath,MaxPath,9,5,2,0,4},
{MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,MaxPath,7,4,0},
};
//final[w]=1代表这个点在A集合中;final[w]=0代表这个点不在A集合中
int final[9]={0};
//默认从v0开始,v0包含在集合中
final[0]=1;
//最小生成树路径总长度
int sumline=0;
int min=MaxPath;
//初始化最短路径为第一个离v0最近的边的权值
for(int i=0;i<9;i++)
{
if(!final[i]&&min>path[0][i])
{
min=path[0][i];
final[i]=1;
}
}
sumline+=min;
//如果final[0-9]之和==9，那么每个点都在集合中，退出循环。
int sumfinal=0;
while(sumfinal!=9)
{
min=MaxPath;
int index=0;
//找一端在A集合中，另一端不在A集合中的边并比较出最小值
for(int i=1;i<9;i++)
{
if(final[i]==1)
{
for(int j=0;j<9;j++)
{
if(!final[j]&&min>path[i][j])
{
min=path[i][j];
index=j;
}
}
}
}
sumline+=min;
final[index]=1;
sumfinal=0;
for (int k=0;k<9;k++) {
sumfinal+=final[k];
}
}
printf("sumline=%d",sumline);
四.贪心算法
1.活动选择规划算法
有且只有一个活动室且一个活动室同时只能排练一个节目，但是有N个团队要进行排练节目，排练时间不固定，如何能让最多的团队进行排练呢？
思路：
我们利用贪心算法(贪婪算法)-在对[问题求解]总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部[最优解]。
在活动选择问题上，按照结束时间升序排序，每次选择最早结束时间的活动，给后面的活动留出更多的时间做选择总是当前最正确的选择。
1.png
先按照结束时间升序排序之后：
2.png
@interface Activity : NSObject
@property(nonatomic,assign)int index;
@property(nonatomic,assign)int beginTime;
@property(nonatomic,assign)int endTime;
-(instancetype)initRandomActivity;
-(void)activityPath
{
int actNum=10;
//创建10个团体，随机初始化活动时间
NSMutableArray * acts=[NSMutableArray array];
for (int i=0;i<actNum;i++) {
Activity * act=[[Activity alloc]initRandomActivity];
act.index=i;
[acts addObject:act];
}
for (int i=0; i<actNum;i++) {
Activity * act=acts[i];
NSLog(@"Pre:%d:%d-%d",act.index,act.beginTime,act.endTime);
}
//先按照结束时间升序排序
[acts sortUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
Activity *act1=(Activity*)obj1;
Activity *act2=(Activity*)obj2;
return act1.endTime>act2.endTime;
}];
for (int i=0; i<actNum;i++) {
Activity * act=acts[i];
NSLog(@"Sort:%d:%d-%d",act.index,act.beginTime,act.endTime);
}
//根据贪婪规则，不断寻找满足条件，结束时间最快的活动。
Activity * firstAct=acts[0];
int index=0;
NSLog(@"index:%d",firstAct.index);
for (int j=index+1;j<actNum;j++) {
Activity * actPre=acts[index];
Activity * actLast=acts[j];
if(actPre.endTime<=actLast.beginTime)
{
index=j;
NSLog(@"-%d",actLast.index);
}
}
}
@end
@implementation Activity
-(instancetype)initRandomActivity
{
if(self=[super init])
{
self.beginTime=[self getRandomNumber:1 to:24];
self.endTime=[self getRandomNumber:self.beginTime to:24];
}
return self;
}
-(int)getRandomNumber:(int)from to:(int)to
{
return (int)(from + (arc4random() % (to - from + 1)));
}
2.最小雷达算法
类似可以用贪心算法解决的问题是最小雷达问题：
x轴上方有n个目标点，坐标全为整数，为了扫描到他们，在x轴上安放雷达，每一个雷达扫描区域是圆形，半径为d，问至少安放多少雷达可以扫描到所有目标点。
算法分析：
最大可能节省雷达的方式就是一个雷达尽可能多的扫描目标点，首先不考虑目标点y值>d的情况，因为无法被扫描到，那么在其他情况下，我们以目标点为圆心,d为半径做圆，同x轴的交点为1个或者2个。比如两个目标点，在同x轴构成的2个区间间隔中，如果存在交集，那么说明在交集中可以放置一个雷达，该雷达可以扫描到这两个目标点，如果没有交集，说明需要2个雷达扫描。
所以问题转化成，在每个目标点按照d半径构成的圆形与x轴相交形成的区间中，找到更多间隔的区间。
3.png
图中粉色和黑色中间可以放置一个雷达，再向后找，黄色和黑色之间可以放置一个雷达，红色本身区间再放一个雷达，最小值为3。
具体算法过程是，先按照每个区间最小右端点升序排序，把第一个区间作为基准，循环找接下来满足条件(基准区间右端点<下一个区间左端点)的区间，再把该区间作为基准，继续找。
int spNum=5;
NSMutableArray * points=[NSMutableArray array];
for (int i=0;i<spNum;i++) {
SeaPoint * sp=[[SeaPoint alloc]initRandomPoint];
NSLog(@"%d:%d-%d",i,sp.beginPoint,sp.endPoint);
[points addObject:sp];
}
//先按照间距右侧端点升序排序
[points sortUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
SeaPoint *sp1=(SeaPoint*)obj1;
SeaPoint *sp2=(SeaPoint*)obj2;
return sp1.endPoint>sp2.endPoint;
}];
for (int i=0; i<spNum;i++) {
SeaPoint * sp=points[i];
NSLog(@"Sorted:%d:%d-%d",i,sp.beginPoint,sp.endPoint);
}
//根据贪婪规则，不断寻找满足条件，后一个间距端点左侧大于前一个间距端点右侧的间距。
int sum=1;
int index=0;
for (int j=1;j<spNum;j++) {
SeaPoint * spLeft=points[index];
SeaPoint * spRight=points[j];
if(spLeft.endPoint<=spRight.beginPoint)
{
index=j;
sum++;
}
}
NSLog(@"最小雷达数:%d",sum);
五.排序
- 预备知识：
//两个数据交换
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
1. 冒泡排序
- 算法思想：
通过相邻两个数进行比较，如果前一个数大于后一个数，那么交换顺序，再继续相邻数比较下去，一趟完成后，最后一个数就是最大的；接着把其他数据继续按照这种方式进行寻找最大值。
/*
冒泡排序，核心思想是相邻的两个数比较，交换，再比较，一趟下来，最小/最大数在最边上
*/
-(void)bubbingsort
{
int arr[]={32,14,7,9,5,27,56,18};
for(int i=0;i<8;i++)
{
for(int j=0;j<8-i-1;j++)
{
if(arr[j]>arr[j+1])
{
swap(&arr[j],&arr[j+1]);
}
}
}
printf("冒泡排序:");
for (int i=0; i<8;i++) {
printf("%d ",arr[i]);
}
}
2. 简单选择排序
- 算法思想：
每次拿第一个数和其他数进行比较，找出最大/最小值；把其他数按照同样的思路，继续寻找最大值。
/*
简单选择排序，核心思想就是每次遍历待排序的数字，比较出最小的数，然后放到前面，
再从其他数字继续下一次遍历...
对比冒泡排序，优点是减少交换次数
*/
-(void)selectsort
{
int arr[]={32,14,7,9,5,27,56,18};
for(int i=0;i<8;i++)
{
int minIndex=i;
for (int j=i+1;j<8;j++) {
if(arr[minIndex]>arr[j])
{
minIndex=j;
}
}
if(minIndex!=i)
{
swap(&arr[minIndex],&arr[i]);
}
}
printf("简单选择排序:");
for (int i=0; i<8;i++) {
printf("%d ",arr[i]);
}
}
3. 插入排序
- 算法思想：
默认第一个数据是已经排好顺序的序列，每次取出下一个数据插入到正确位置，因为插入后的新序列都是有序序列，所以新数据只需要插入到第一个比自己大的数据前面，其他数据向后移动位置。
/*
插入排序，核心思想就是拿一个新数据往排序好的列表中正确位置不断插入，
构成新的排序好的列表
*/
-(void)insertsort
{
int arr[]={32,14,7,9,5,27,56,18};
//定义一个变量保存将要进行插入的数字
int temp=arr[0];
for(int i=1;i<8;i++)
{
if(arr[i]<arr[i-1])
{
temp=arr[i];
int j;
//向后移动大于temp的数字，腾出插入空间
for(j=i-1;j>=0&&arr[j]>temp;j--)
{
arr[j+1]=arr[j];
}
//插入到正确位置
arr[j+1]=temp;
}
}
printf("插入排序:");
for (int i=0; i<8;i++) {
printf("%d ",arr[i]);
}
}
4. 希尔排序(升级版插入排序)
- 算法思想：
把数据按照一定间隔进行插入排序，然后不断减小数据间隔插入排序直到间隔等于1，目的是把数据分组，尽量减少待排序的数据。
/*
希尔排序(插入排序升级版)，核心思想就是把大序列按照增量N分成若干小序列分别进行插入排序，
然后再不断减小N直到1，对已知排序好的序列继续进行插入排序
*/
-(void)shellsort
{
int arr[]={32,14,7,9,5,27,56,18};
int increment=8;
int temp=arr[0];
do{
//指定增量数(间隔)的递减方式
increment=increment/3+1;
for(int i=increment;i<8;i++)
{
//对间隔increment的数字进行插入排序
if(arr[i]<arr[i-increment])
{
temp=arr[i];
int j;
for (j=i-increment;j>=0&&arr[j]>temp;j=j-increment){
arr[j+increment]=arr[j];
}
arr[j+increment]=temp;
}
}
}while(increment>1);
printf("希尔排序:");
for (int i=0; i<8;i++) {
printf("%d ",arr[i]);
}
}
5. 堆排序(升级版选择排序)
- 预备知识：
大顶堆/小顶堆：是一种特殊的完全二叉树，每个节点的值都比左右孩子的值大(小)。
ki>=k2i，ki>=k2i+1且 1<=i<=n/2 或者
ki<=k2i，ki<=k2i+1且 1<=i<=n/2
当前节点为i，那么左孩子节点是2i，右孩子节点是2i+1 - 算法思想：
利用大顶堆/小顶堆的结构进行排序，把数据构造成一个大顶堆，此时最大数据就是根节点，把根节点移除(和最后一个叶子节点交换)，再次构造大顶堆，然后继续交换，直到所有元素都比较完成。
/*
堆排序，核心思想是把数字构成大顶堆，此时大顶堆根节点为最大数，然后把该节点和最后一个子节点交换(相当于移走)
再继续把剩余数字构成大顶堆...直到所有所有数字排序完成
*/
-(void)heapsort
{
int arr[]={32,14,7,9,5,27,56,18};
//构建一个临时0开始的数组，保证第一个数据从1开始(符合树的结构)
int temparr[]={0,32,14,7,9,5,27,56,18};
int length=8;
//初始化一个大顶堆
for (int i=length/2;i>0;i--) {
//从最后一个非叶子节点开始调整堆
[self heapcreate:temparr andBegin:i andLen:length];
}
//交换堆顶最大节点和最后一个节点，把待排序的数据重新调整为大顶堆
for (int i=length;i>1;i--) {
swap(&temparr[1],&temparr[i]);
//因为此时只有堆顶元素不满足大顶堆，只需要从堆顶元素开始调整就行
[self heapcreate:temparr andBegin:1 andLen:i-1];
}
printf("堆排序:");
for (int i=1; i<=length;i++) {
printf("%d ",temparr[i]);
}
}
/*
构建堆：从begin节点位置开始，调整左右孩子和自己的位置，如果左右孩子被交换到根节点，那么以被调整的左右孩子为根节点
继续调整。
*/
-(void)heapcreate:(int[])arr andBegin:(int)begin andLen:(int)length
{
int temp=arr[begin];
//i记录左孩子和右孩子较大的位置
for (int i=begin*2;i<=length;i*=2){
if(i+1<=length&&arr[i]<arr[i+1])
i++;
if(arr[i]<temp)
break;
arr[begin]=arr[i];
begin=i;
}
arr[begin]=temp;
}
6. 归并排序
- 预备知识：
对两个有序数组进行有序合并，借助一个临时数组(长度是两个数组的和)，不断向后移动两个数组的游标位置，把最小的数据添加到临时数组中，如果某一个游标移动到末尾，那么把剩余数据追加到临时数组后。再把临时数据重新赋值给原数组。 - 算法思想：
不断递归把数据进行二分，直到被分成一个数据，进行有序合并。
/*归并排序*/
-(void)mergesort
{
int arr[]={32,14,7,9,5,27,56,18};
int length=8;
int begin=0;
int end=length-1;
[self part:arr andBegin:begin andEnd:end];
printf("归并排序:");
for (int i=0; i<length;i++) {
printf("%d ",arr[i]);
}
}
/*把数组不断进行递归二分，直到分成一个数据*/
-(void)part:(int[])arr andBegin:(int)begin andEnd:(int)end
{
if(arr==NULL||begin>=end)
return;
int mid=(begin+end)/2;
[self part:arr andBegin:begin andEnd:mid];
[self part:arr andBegin:mid+1 andEnd:end];
[self merge:arr andBegin:begin andMid:mid andEnd:end];
}
/*把二分后的数组进行合并排序调整*/
-(void)merge:(int[])arr andBegin:(int)begin andMid:(int)mid andEnd:(int)end
{
int *temp = (int *)malloc((end-begin+1)*sizeof(int));
//记录拆分第一个数组的起点
int i=begin;
//记录拆分第二个数组的起点
int j=mid+1;
//记录temp数组移动游标位置
int biao=0;
//不断比较并把较小的数据插入到temp中
while(i<=mid&&j<=end)
{
if(arr[i]<arr[j])
{
temp[biao]=arr[i];
i++;
}else
{
temp[biao]=arr[j];
j++;
}
biao++;
}
//把剩余未比较的数据(大数)插入到temp后
if(i>mid)
{
for(int k=j;k<=end;k++)
{
temp[biao++]=arr[k];
}
}
if(j>end)
{
for(int k=i;k<=mid;k++)
{
temp[biao++]=arr[k];
}
}
//把排序好的temp数值赋值到arr中正确的位置上去
for(int i=0;i<biao;i++)
{
arr[begin+i]=temp[i];
}
}
递归的流程：
4.png
7. 快速排序
- 算法思想：
找一个基准数据，遍历一趟，把比基准数据小的放到左边，大的放到右边，以基准数据为中心分开，继续之前的调整步骤。
/*快速排序*/
-(void)quicksort
{
int arr[]={32,14,7,9,5,27,56,18};
int length=8;
[self qsort:arr andLow:0 andHigh:length-1];
printf("快速排序:");
for (int i=0; i<length;i++) {
printf("%d ",arr[i]);
}
}
/*不断递归调整基准数的位置*/
-(void)qsort:(int[])arr andLow:(int)low andHigh:(int)high
{
int pivot;
if(low<high)
{
pivot=[self adjustPosition:arr andLow:low andHigh:high];
[self qsort:arr andLow:low andHigh:pivot];
[self qsort:arr andLow:pivot+1 andHigh:high];
}
}
/*以基准数为标准，调整小于基准数的在左边，大于基准数的在右边*/
-(int)adjustPosition:(int [])arr andLow:(int)low andHigh:(int)high
{
int temp=arr[low];
int pivot=low;
//左右游标重合说明调整结束
while(low<high)
{
while(arr[high]>=temp&&low<high)
high--;
swap(&arr[low],&arr[high]);
while (arr[low]<=temp&&low<high)
low++;
swap(&arr[high],&arr[low]);
pivot=low;
}
return pivot;
}
- 优化思路：
1.基准数如果取的太小或者太大，都会影响效率，可以使用三数比较法，就是取第一个，最后一个和中间的数比较大小，取中间大小的数为基准数。
2.数据交换改成数据记录，因为来回交换，目的也是找到基准点的最终位置。
8. 总结：
5.png
网友评论