❶ 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語言。
快速排序
快速排序是二叉查找樹（二叉搜索樹）的一個空間最優化版本。不是循序地把數據項插入到一個明確的樹中，而是由快速排序組織這些數據項到一個由遞歸調用所隱含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。對於排序演算法的穩定性指標，原地分區版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲性能和空間來維護穩定性的。