『壹』 誰能給個簡單的C語言歸並排序演算法的例子啊謝謝
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#define M 11
typedef int KeyType;
typedef int ElemType;
struct rec
{
KeyType key;ElemType data;
};
typedef rec sqlist[M];
void output( sqlist r, int n )
{
for ( int i = 0; i < n; i++ )
{
cout << setw( 4 ) << r[i].key;
}
cout << endl;
}
void xuanze( sqlist b, int m, int n )
{
int i, j, k;
for ( i = m; i < n - 1; i++ )
{
k = i;
for ( j = i; j < n; j++ )
{
if ( b[k].key > b[j].key )
{
k = j;
}
}
if ( k != i )
{
rec temp = b[k];
b[k] = b[i];b[i] = temp;
}
}
}
void merge( sqlist r, int l, int m, int h, sqlist r2 )
{
xuanze( r, l, m );
xuanze( r, m, h );
output( r, M );
int i, j, k;
k = i = l;
for ( j = m; i < m && j < h; k++ )
{
if ( r[i].key <= r[j].key )
{
r2[k] = r[i];i++;
}
else
{
r2[k] = r[j];j++;
}
output( r2, M );
}
while ( j < h )
{
r2[k] = r[j];j++;k++;
}
while ( i <= m )
{
r2[k] = r[i];i++;k++;
}
output( r2, M );
}
void main()
{
cout << "guibingfa2.cpp運行結果:\n";
sqlist a, b;int i, j = 0, k = M / 2, n = M;
srand( time( 0 ) );
for ( i = 0; i < M; i++ )
{
a[i].key = rand() % 80;b[i].key = 0;
}
cout << "排序前數組:\n";
output( a, M );
cout << "數組排序的過程演示:\n";
merge( a, j, k, n, b );
cout << "排序後數組:\n";
output( b, M );cin.get();
}
『貳』 c語言的歸並排序
、歸並簡單點說就是2分法 一直除以2 然後把從0到N/2的下標 ， 和 N/2+1 到N的地址傳送到合並函數裡面，遞歸調用
『叄』 用C語言編寫演算法實現將兩個遞增順序表合並為一個遞增順序表
1.最容易的辦法就是把兩個表保存在一個新的表裡，然後冒泡排序（就是這么暴力。）
2.不過這個問題用指針實現最方便了。
兩個指針分別指著兩個遞增表：比較指針所指的值大小，將小的那個保存在新的表裡，然後將小的那個指針往前走一步。再比較，再保存，再走....直到其中一個表走完，把另一個表剩下的數接在後面。
這樣做的好處是原有的兩個表的內容不會被修改。因為結果是保存在新的表裡的，但是消耗內存。
3.插入排序，同樣使用指針比較，把一個表裡的數據插到另一個表裡。這樣省內存，但是被插入的這個表原有的數據就沒咯。
『肆』 （C語言數據結構） 設計兩個有序順序表的合並排序演算法。
#include
#include
typedef
struct
node//定義結構體
{
int
score;
struct
node
*next;
}node;
node
*create(int
n)//創建鏈表
{
node
*head,*tail,*p;
head=tail=null;
int
i;
for(i=1;i<=n;i++)
{
p=(node
*)malloc(sizeof(node));
p->next=null;
printf("please
input
%d
score:",i);
scanf("%d",&p->score);
if(head==null)
head=tail=p;
else
{
tail->next=p;
tail=p;
}
}
return
head;
}
node
*range(node
*head)//排序
{
node
*p,*q;
int
score,i,n=0;
p=head;
while(p)
{
n++;
p=p->next;
}
for
(i=0;i
next!=null)//內循環
{
q=p->next;
if
(p->score>q->score)//值交換
{
score=p->score;
p->score=q->score;
q->score=score;
}
p=q;
}
}
return
head;
}
node
*connect(node
*head1,node
*head2)//合並
{
node
*p;
p=head1;
while(p->next!=null)
p=p->next;
p->next=head2;
return
head1;
}
void
output(node
*head)//輸出
{
node
*p;
p=head;
while(p)
{
printf("%d
",p->score);
p=p->next;
}
printf("\n");
}
int
main()
{
node
*head,*hea1,*head2;
int
n1,n2;
printf("please
input
a
n1:");//第一個鏈表的成績個數
scanf("%d",&n1);
hea1=create(n1);
printf("第一個鏈表的成績:");
output(hea1);
printf("please
input
a
n2:");//第二個鏈表的成績個數
scanf("%d",&n2);
head2=create(n2);
printf("第二個鏈表的成績:");
output(head2);
head=connect(hea1,head2);
head=range(head);
printf("合並後，並排好序:");
output(head);
return
0;
}
『伍』 C語言排序演算法一共多少種
選擇排序
#include<iostream>
usingnamespacestd;
voidselect_sort(intarr[],intnum);
voidoutput_array(intarr[],intnum);
intmain()
{
inta[10];
for(inti=0;i<10;i++)
{
cin>>a[i];
}
select_sort(a,10);
output_array(a,10);
return0;
}
voidselect_sort(intarray[],intn)//形參array是數組名
{
inti,j,k,t;
for(i=0;i<n-1;i++)
{
k=i;//先設第i個就為最小
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;//通過循環，得到k為最小
t=array[k];//交換a[i]和a[k]
array[k]=array[i];
array[i]=t;
}
return;
}
voidoutput_array(intarr[],intnum)
{
inti;
for(i=0;i<num;i++)
{
cout<<arr[i];
cout<<endl;
}
return;
}
2.冒泡排序
#include<stdio.h>
intmain()
{
inti,j,a[10],t;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
for(i=0;i<10;i++)
printf("%d",a[i]);
return0;
}
3.堆排序
#include<iostream>
usingnamespacestd;
voidpaii(inta[20],inti,intm)
{
intk,t;
t=a[i];
k=2*i+1;
while(k<m)
{
if((k<m-1)&&(a[k]<a[k+1]))
k++;
if(t<a[k])
{
a[i]=a[k];
i=k;
k=2*i+1;
}
elsebreak;
}
a[i]=t;
}
voidipai(inta[20],intn)
{
inti,k;
for(i=n/2-1;i>=0;i--)
paii(a,i,n);
for(i=n-1;i>=1;i--)
{
k=a[0];
a[0]=a[i];
a[i]=k;
paii(a,0,i);
}}
intmain()
{
inta[10],i;
for(i=0;i<10;i++)
cin>>a[i];
ipai(a,10);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
}
4.快速排序
#include<iostream>
usingnamespacestd;
voidQuicksort(inta[],intlow,inthigh)
{
if(low>=high)
{
return;
}
intfirst=low;
intlast=high;
intkey=a[first];
while(first<last)
{
while(first<last&&a[last]>=key)
--last;
a[first]=a[last];
while(first<last&&a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}
intmain()
{
inti,a[100],x,n=0;
while(cin>>x)
{
a[n]=x;
n++;
}
n--;
Quicksort(a,0,n);
for(i=0;i<=n;i++)
cout<<a[i]<<"";
cout<<endl;
return0;
}
5. 基數排序
#include<stdio.h>
#include<stdlib.h>
intmain(){
intdata[10]={73,22,93,43,55,14,82,65,39,81};//對十個數進行排序
inttemp[10][10]={0};//構造一個臨時二維數組，其值為0
intorder[10]={0};//構造一維數組，其值為0
inti,j,k,n,lsd;
k=0;n=1;
for(i=0;i<10;i++)printf("%d",data[i]);//在排序前，對這10個數列印一遍
putchar(' ');
while(n<=10){
for(i=0;i<10;i++){
lsd=((data[i]/n)%10);//lsd先對個位取余，然後再對十位取余，注意循環
temp[lsd][order[lsd]]=data[i];//temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯
order[lsd]++;//需要區分的是lsd和order[lsd]，這兩個不是一樣的概念嗷
}
printf(" 重新排列:");
for(i=0;i<10;i++){
if(order[i]!=0)
for(j=0;j<order[i];j++){
data[k]=temp[i][j];
printf("%d",data[k]);
k++;
}
order[i]=0;
}
n*=10;//第二次用十位
k=0;
}
putchar(' ');
printf(" 排序後:");
for(i=0;i<10;i++)printf("%d",data[i]);
return0;
}
6.希爾排序
#include<iostream>
usingnamespacestd;
voidshell_sort(inta[],intn);
intmain()
{
intn,a[10000];
cin>>n;
for(inty=0;y<n;y++)
cin>>a[y];
shell_sort(a,n);
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<endl;
}
voidshell_sort(inta[],intn)
{
intgap,k,temp;//定義增量；
for(gap=3;gap>0;gap--)//設置初始增量，遞減；
{
for(inti=0;i<gap;i++)//按增量分組；
{
for(intj=i+gap;j<n;j=j+gap)//每組分別比較大小；
{
if(a[j]<a[j-gap])
{
temp=a[j];
k=j-gap;
while(k>=0&&a[k]>temp)
{
a[k+gap]=a[k];
k=k-gap;
}
a[k+gap]=temp;
}
}
}
}
}
7.歸並排序
#include<iostream>
usingnamespacestd;
voidMergeSort(intp[],ints,intm,intt)
{
intq[100];//q[100]用來存放排好的序列
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t)
{
if(p[i]<=p[j])
q[k++]=p[i++];
else
q[k++]=p[j++];
}
if(i<=m)
while(i<=m)
q[k++]=p[i++];
elsewhile(j<=t)
q[k++]=p[j++];
for(intn=s;n<=t;n++)
p[n]=q[n];
}
voidMerge(intp[],ints,intt)
{
if(s<t)
{
intm=(s+t)/2;//將數組分成兩半
Merge(p,s,m);//遞歸拆分左數組
Merge(p,m+1,t);//遞歸拆分右數組
MergeSort(p,s,m,t);//合並數組
}
}
intmain()
{
intn;
intp[100];
cin>>n;
for(inti=0;i<n;i++)
cin>>p[i];
Merge(p,0,n-1);
for(intj=0;j<n;j++)
cout<<p[j]<<"";
cout<<endl;
return0;
}
排序方法基本就這些，還有雙向冒泡這種拓展的排序方法，還有直接排序如桶排序
『陸』 C語言歸並排序代碼
void mergeSort(int a[],int left,int right)
{
int i;
// 保證至少有兩個元素
if(left < right)
{
i = (left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,left,right);
}
}
void merge(int a[],int left,int right)
{
int begin1 = left;
int mid = (left+right)/2 ;
int begin2 = mid+1;
int k=0;
int newArrayLen = right-left+1;
int *b = (int*)malloc(newArrayLen*sizeof(int));
while(begin1<=mid && begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
while(begin1<=mid)
b[k++] = a[begin1++];
while(begin2<=right)
b[k++] = a[begin2++];
Array(b,a,newArrayLen,left);
free(b);
}
/**
* 復制數組
* source:源數組
* dest:目標數組
* len:源數組長度
* first:目標數組起始位置
*
*/
void Array(int source[], int dest[],int len,int first)
{
int i;
int j=first;
for(i=0;i<len;i++)
{
dest[j] = source[i];
j++;
}
}
void mergeSortTest()
{
int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
int len = sizeof(a)/sizeof(int);
showArray(a,len);
mergeSort(a,0,len-1);
showArray(a,len);
}
『柒』 高分送！！如何用C語言實現歸並排序演算法！！！
#include <iostream>
using namespace std;
void merge(int array[],int left,int right)
{
int temparray[right];
for(int j=left;j<=right;j++)
{
temparray[j]=array[j];
}
int middle=(left+right)/2;
int index1=left;
int index2=middle+1;
int i=left;
while((index1<=middle)&&(index2<=right))
{
if(temparray[index1]<temparray[index2]) array[i++]=temparray[index1++];
else array[i++]=temparray[index2++];
}
while(index1<=middle) array[i++]=temparray[index1++];
while(index2<=right) array[i++]=temparray[index2++];
}
void sort(int array[],int left,int right)
{
if(left<right)
{
int middle=(left+right)/2;
sort(array,left,middle);
sort(array,middle+1,right);
merge(array,left,right);
}
}
這個不是特別的完美，但是大體上就是這么個思路啦~而且因為語法不嚴謹，貌似只能在c++下運行~建議看看youku上的數據結構課，然後你就會發現全明白了~
如果在c語言下運行，int temparray[right];這句話裡面的right要改成你需要用的數~
『捌』 c語言歸並排序簡單問題
當調用Merge_SortDC(1,8);時，
Merge_SortDC(1,4); 與Merge_SortDC(4+1,8); 都執行成功返回以後
兩邊的數組都是有序的了，這時候，執行Merge(low,mid,high)，也就是Merge(1,4,8）。
至於Merge_SortDC(1,4); 與Merge_SortDC(4+1,8)各自的執行順序，也跟Merge_SortDC(1,8);是類似的，可以類推。
遞歸就是先遞推調用到最後，然後再一層層返回來。
『玖』 求C或C++編程：有兩組無序數字 arr1， arr2，將它們合並為一個從小到大排列的數字。
演算法1。先排序，再合並；
演算法2。先合並為一組，再排序。
『拾』 十大經典排序演算法 C 語言實現[上]冒泡選擇插入希爾歸並
期中已到，期末將至。《演算法設計與分析》的「預習」階段藉此開始~。在眾多的演算法思想中，如果你沒有扎實的數據結構的功底，不知道棧與隊列，哈希表與二叉樹，不妨可以從排序演算法開始練手。縱觀各類排序演算法，常見的、經典的排序演算法將由此篇引出。
排序演算法的輸出必須遵守的下列兩個原則：
十大經典的排序演算法及其時間復雜度和穩定性如上表所示。判斷一個排序演算法是否穩定是看在相等的兩個數據排序演算法執行完成後是否會前後關系顛倒，如若顛倒，則稱該排序演算法為不穩定，例如選擇排序和快速排序。
接下來十個經典排序演算法的詳細探討缺少不了交換兩個整數值的掌握，這里回顧一下其中三種方交換法：用臨時變數交換兩個整數的值(SwapTwo_1)、不用第三方變數交換兩個整數的值(SwapTwo_2)、使用位運算交換兩個整數的值(SwapTwo_3)。其中用臨時變數交換兩個整數的值效率最高，後倆者只適用於內置整型數據類型的交換，並不高效。
先不說公司面試筆試，大學實驗室的納新題里最常有的就是冒泡排序。冒泡排序重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。由於它的簡潔，冒泡排序通常被用來對於程序設計入門的學生介紹演算法的概念。
[圖片上傳失敗...(image-93185f-1513765803581)]]( http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip )
上圖可見，冒泡排序演算法的運作如下：
通俗來講，整個冒泡排序就是通過兩次循環，外層循環將此輪最大(小)值固定到此輪尾部，內層循環「冒泡」比較相鄰的兩個元素並決定是否交換位置。
從上圖也可理解冒泡排序如何將每一輪最大（小）值固定到此輪尾部：尾部總為有序狀態，前面無序狀態區根據大小規則冒泡向後方傳遞最值。
選擇排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。
上圖左下角和右上角可以分別看做排序序列起始位置(已排序區)和排序序列末尾(未排序區)，左下角一直穩定更新，但選擇排序不穩定，即排序後曾經相同的兩個元素的前後位置關系可能會發生顛倒。
插入排序的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用 in-place
排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。
一般來說，插入排序都採用 in-place 在數組上實現。具體演算法描述如下：
如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找插入排序。這里先不做涉及。
希爾排序按其設計者希爾（Donald Shell）的名字命名，該演算法由1959年公布。希爾排序也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。
步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。演算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序，最終演算法以步長為1進行排序。當步長為1時，演算法變為插入排序，這就保證了數據一定會被排序。
已知的最好步長序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，這項研究也表明「比較在希爾排序中是最主要的操作，而不是交換。」用這樣步長序列的希爾排序比插入排序要快，甚至在小數組中比快速排序和堆排序還快，但是在涉及大量數據時希爾排序還是比快速排序慢。
歸並排序是創建在歸並操作上的一種有效的排序演算法，效率為 O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
歸並操作（merge），也叫歸並演算法，指的是將兩個已經排序的序列合並成一個序列的操作。歸並排序演算法依賴歸並操作。
歸並排序用迭代法和遞歸法都可以實現，迭代法的演算法步驟為：
遞歸法的演算法步驟為：
這篇文章「十大經典排序演算法及其 C 語言實現【上】」引出了十大經典演算法的前五個並用 C 語言實踐：冒泡排序、選擇排序、插入排序、希爾排序和歸並排序，並作出了充足的圖文解釋。即將推出的「十大經典排序演算法及其 C 語言實現【下】」將對剩下五個經典演算法快速排序、堆排序、計數排序、桶排序、基數排序作出完善，盡請期待~。