本文主要是介绍【王道数据结构】【chapter8排序】【P391t3】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
设一个数组中存放了一个无序的关键序列K1,K2,……Kn，现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
#include <iostream>
#include <time.h>
#include <utility>
#include<algorithm>
int * buildarray(int size)
{int * tmp=(int *) malloc(sizeof(int)*size);for(int i=0;i<size;i++) tmp[i]=rand()%20;return tmp;
}
void print(int * tmp,int size)
{for(int i=0;i<size;i++) printf("%3d",tmp[i]);puts("");
}
int partition(int * tmp,int size)//将最后一个元素放到正确的位置上
{int record=tmp[size-1],l=0,r=size-1;while(l<r){while(l<r&&tmp[l]<=record) l++;tmp[r]=tmp[l];while(l<r&&tmp[r]>=record) r--;tmp[l]=tmp[r];}tmp[l]=record;return record;}
int main() {srand(time(nullptr));int * r1= buildarray(20);print(r1,20);partition(r1,20);print(r1,20);//这个sort只是用来看看我们之前的最后一个元素是不是已经在正确的位置上了，不是正式的代码std::sort(r1,r1+20);print(r1,20);return 0;
}
这篇关于【王道数据结构】【chapter8排序】【P391t3】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
