❶ c语言问题
算法：分治法
数据结构：数组
步骤：
(1)把数组从中间分为两段；
(2)递归调用此算法，分别处理前半段和后半段，分别得出前 半段和后半段的捣乱个数，并排序前半段和后半段；
(3)再计算前半段大于后半段的次数；
(4)三个结果相加，得出捣乱总数。
伪代码：
Count_inver(L)
{
If (只有一个元素) return 0;
Else {
Devide L into two lists, A, B;/*A :0~n/2, B: 1＋n/2～n-1*/;
Ra = count_inver(A);
Rb = count_inver(B);
Rm = merge(A, B);
Return (Ra+Rb+Rm);
}
}
Merge的实现：
由于A，B已经升序排序完毕，可以这样计算出”AB之间”的的捣乱数目。仿照归并排序的merge过程，把AB归并为一个有序数组,供下一轮递归调用，在归并的过程中，每放入一个A元素，都统计这个元素大于B数组的个数，归并完毕后可得Rm。这个merge的过程可以在O(n)时间内完成。
算法复杂度分析：
T(n) = 2T(n/2)+O(n)，得O(n*logn)
//你的例子4,3,5,2中，(4,3)(4,2)(3,2)(5,2)都是
//需要代码的话，给我消息。
❷ c语言：采用分治法递归求含n个数的某个序列的最大元素和次大元素。
high -low 为奇数，这个mid是小数。
（1）数组个数为n，还用a[n]
（2）还不如直接用个for循环，将max=0
#include <stdio.h>
#define N 21
int max(int a,int b){
if(a>b)
return a;
return b;
}
int getM(int * a,int l,int u){
if(u==l)
return a[u];
else{
return max(getM(a,l,(u+l)/2),getM(a,(u+l)/2+1,u) );
}
}
int main()
{
int a[N]={1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17};
printf("max=%d",getM(a,0,N-1));
return 0;
}
(2)c语言分治法快速排序扩展阅读：
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可。
而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
❸ 分治法c语言求最大最小值
1、分治法不是用来求最大值最小值的。在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)。
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解。
2、求数组中的最大值和最小值，一般使用假设法，即假设数组的第1个元素为最大值，同时也是最小值，然后遍历数组，找到最大值和最小值。示例如下:
#include<stdio.h>
intmain()
{
inta[]={1,2,3,4,5,6,7,8,9,10};
intmax,min;
max=min=a[0];//假设第1个元素即是最大值也是最小值。
intmax_pos=0,min_pos=0;
//遍历数组，找出数组a中的最大数和最小数
for(intinx=0;inx!=sizeof(a)/sizeof(int);++inx){
if(a[inx]>max)max=a[inx],max_pos=inx;
elseif(a[inx]<min)min=a[inx],min_pos=inx;
}
printf("最大数:%d 最小数:%d ",max,min);
return0;
}
❹ C语言快速排序代码
采用快速排序，用递归实现
#include <stdio.h>
#define N 10 //定义排序数组元素个数
int Qsort(int start,int length,int a[])//start排序的起始，length是要排序序列长度
{
int x = a[start];
int i,j;
i = start;
j = length -1;
while(i < j)
{
if(x < a[j])
j--;
else if(x > a[j])
{
a[i] = a[j];
a[j] = x;
i++;
}
else if(x < a[i])
{
a[j] = a[i];
a[i] = x;
j--;
}
else
i++;
}
if(start < length-1)
{
Qsort(start,i,a);
Qsort(i+1,length,a);
}
}
void main()
{
int a[N] = {0};
int i;
for(i = 0;i < N;i++)
scanf("%d",&a[i]);
Qsort(0,N,a);
for(i = 0;i < N;i++)
printf("%d ",a[i]);
}
程序执行时输入N个数，对这N个数进行排序，可以预设N的长度
❺ 你的这个分治法的快速排序的程序是怎么修改的，我写了同样的代码问什么就是不行。C语言新手，请多多指教
你的n是未初始化的，而且你在后面的方法中也使用了n说明n是一个全局变量，所以直接放在main中有点不合适。若是对于需要使用长度的数组，一般上使用//#define N 10 来定义长度，就算以后数组长度变了，也方便修改,只要修改N就行了，你宏定义N，将你的n 修改成 N，程序就没有问题了。我建议你可以给你的全局变量t赋值为1
❻ 急寻一个用分治法实现合并排序的源程序,要求为C语言的.TRUBO2.0
#include<stdio.h>
#include<string.h>
#define N 100 //宏定义数组长度
void merge(int arrayc[],int arrayd[],int l,int m,int r){ //定义合并函数，合并arrayc[1:m]和arrayc[m+1:r]到arrayd[l:r]
int i=l;
int j=m+1;
int k=l;
while((i<=m)&&(j<=r))
if(arrayc[i]<=arrayc[j])
arrayd[k++]=arrayc[i++];
else
arrayd[k++]=arrayc[j++];
if(i>m)
for(int q=j;q<=r;q++)
arrayd[k++]=arrayc[q];
else
for(int q=i;q<=m;q++)
arrayd[k++]=arrayc[q];
}
void mergepass(int arrayx[],int arrayy[],int s){ //合并大小为s的相邻子数组
int i=0;
while(i<=N-2*s){
merge(arrayx,arrayy,i,i+s-1,i+2*s-1);
i=i+2*s; //合并大小为s的相邻2段子数组
}
if((i+s)<N)
merge(arrayx,arrayy,i,i+s-1,N-1);
else
for(int j=i;j<N;j++)
arrayy[j]=arrayx[j]; //else复制到arrayy数组中
}
void mergesort(int array1[]){
int array2[N];
int s=1;
while(s<N){
mergepass(array1,array2,s);//合并到数组array2中
s+=s;
mergepass(array2,array1,s);//合并到数组array1中
s+=s;
}
}
int main(){ //定义main()主函数
int a;
printf("请输入要合并排序的数组大小：(数组最大上限100)\n");
scanf("%d",&a);
int array[N];
printf("Please input shorted array:\n");
for(int i=0;i<a;i++) //a控制数组大小
scanf("%d",&array[i]);
mergesort(array);
printf("合并排序后的数组为:\n");
for( i=N-a;i<N;i++)
printf(" %d",array[i]);
return 0;
}
❼ 数据结构，c语言版，这个怎么写
看起来容易，写起来发现超级费劲的，写这个可累死我了，另外链表的排序你自己再找找吧。推荐你找快速排序，就是递归分治法排序，这个图片是动态规划递归分治法查找，道理是一样的
#include<stdio.h>
#include<stdlib.h>
#defineOK1
#defineTRUE1
#defineERROR-1
#defineFALSE-1
#defineOVERFLOW-2
typedefintStatus;
#defineLENsizeof(Node)
#defineMLC(Node*)malloc(sizeof(Node))
//-----链表表示的一元多项式--------------
typedefstructPNode{
floatcoef; //系数data域
intexpn; //指数data域
PNode*next; //引用ptr域
int(*Length)(PListL);//长度
PNode*(*MakeNode)(PNode*polyElem);//无参构造器,用函数指针实现成员函数
void(*CreatePloyn)(PListL,intlength);//建立链表
}PNode,*PList;
//无参构造器,在c语言里面实现构造器，赋值语句,
PNode*MakeNode(){
PNode*head=(PNode*)malloc(sizeof(PNode));
if(!head)/*存储分配失败*/
exit(OVERFLOW);
coef=0.0;//赋值语句默认值
expn=0;
next=NULL;
returnhead;
}
//有参构造器，建立有值的多项式链表
voidCreateValuePloyn(PListp,intlength){
PListe=PList.MakeNode();//无参构造器
for(inti=0;i<length;i++){
scanf("%i,%i",&e->coef,&e->expn);//赋值,系数,指数 //输入各项的系数和指数,建立一元多项式的有序链表p
}
}
/*将值为data的结点插入到head链表的最后*///AppendByInstanseNode
voidAppendNode(PNode*head,doublecoef,intexp){
PNode*pre=head->next;
PNode*temp;//tempNode*
temp=(PNode*)malloc(sizeof(PNode));
temp->coef=coef;
temp->exp=exp;
temp->next=NULL;
if(pre==NULL){
head->next=temp;
return;
}
for(;pre->next!=NULL;pre=pre->next);
pre->next=temp;
}
//多项式节点的加法
PNode*Add(PNode*headA,PNode*headB){
PNode*currA,*currB,*headC;
doublesum;
currA=headA->next;
currB=headB->next;
headC=Init();
while(currA!=NULL&&currB!=NULL){
if(currA->exp>currB->exp){
AppendNode(headC,currA->coef,currA->exp);
currA=currA->next;
}elseif(currA->exp<currB->exp){
AppendNode(headC,currB->coef,currB->exp);
currB=currB->next;
}else{
sum=currA->coef+currB->coef;
if(sum!=0){
AppendNode(headC,sum,currA->exp);
}
currA=currA->next;
currB=currB->next;
}
}
while(currA!=NULL){
AppendNode(headC,currA->coef,currA->exp);
currA=currA->next;
}
while(currB!=NULL){
AppendNode(headC,currB->coef,currB->exp);
currB=currB->next;
}
returnheadC;
}
/*返回head链表的所有结点的数量*/
intLength(PNode*head){
intlen=0;
PNode*curr;
for(curr=head->next;curr!=NULL;curr=curr->next,len++);
returnlen;
}
//访问结点输出
Statusvisit(PListp){
printf("(%lf,%d) ",p->coef,p->expn);
returnTRUE;
}
//遍历链表输出:依次对L的每个元素调用visit()
voidListTraverse(PListL,void(*visit)(PNode)){
/*依次对L的每个元素调用vi(),打印输出语句*/
PListp;//tempptr
p=L->next;//passtheheadnode
printf("Allnodes'svaluesare:");
while(p!=NULL){
visit(p);//visitandprint
p=p->next;
}
printf("
");
}
//主函数
voidmain(){
PNode*headA,*headB,*headC;
headA=Init();
headB=Init();
AppendNode(headA,1.0,5);
AppendNode(headA,-1.0,3);
AppendNode(headA,1,0);
AppendNode(headB,0.5,5);
AppendNode(headB,1.0,4);
AppendNode(headB,1.0,3);
ListTraverse(headA);
ListTraverse(headB);
headC=Add(headA,headB);
ListTraverse(headC);
}
❽ 快速排序特点
快速排序（Quicksort）是对冒泡排序的一种改进，由东尼·霍尔在1960年提出。 快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。
分类
排序算法
数据结构
不定
最坏空间复杂度
根据实现的方式不同而不同
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
从数列中挑出一个元素，称为“基准”（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
在简单的伪代码中，此算法可以被表示为：
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x<pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
原地（in-place）分区的版本
上面简单版本的缺点是，它需要的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分区算法的版本，且在好的基准选择上，平均可以达到空间的使用复杂度。
function partition(a, left, right, pivotIndex)
{
pivotValue = a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到结尾
storeIndex = left
for i from left to right-1
{
if a[i]<= pivotValue
{
swap(a[storeIndex], a[i])
storeIndex = storeIndex + 1
}
}
swap(a[right], a[storeIndex]) // 把pivot移到它最后的地方
return storeIndex
}
这是原地分区算法，它分区了标示为"左边（left）"和"右边（right）"的序列部分，借由移动小于的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。
一旦我们有了这个分区算法，要写快速排列本身就很容易：
procere quicksort(a, left, right)
if right>left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
这个版本经常会被使用在命令式语言中，像是C语言。
快速排序
快速排序是二叉查找树（二叉搜索树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。