c語言的歸並排序演算法
㈠ c語言歸並排序代碼
voidmergeSort(inta[],intleft,intright)
{
inti;
//保證至少有兩個元素
if(left<right)
{
i=(left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,left,right);
}
}
voidmerge(inta[],intleft,intright)
{
intbegin1=left;
intmid=(left+right)/2;
intbegin2=mid+1;
intk=0;
intnewArrayLen=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:目標數組起始位置
*
*/
voidArray(intsource[],intdest[],intlen,intfirst)
{
inti;
intj=first;
for(i=0;i<len;i++)
{
dest[j]=source[i];
j++;
}
}
voidmergeSortTest()
{
inta[]={5,18,151,138,160,63,174,169,79,200};
intlen=sizeof(a)/sizeof(int);
showArray(a,len);
mergeSort(a,0,len-1);
showArray(a,len);
}
㈡ 給定一個數列，如何用歸並排序演算法把它排成升序,用c語言實現。
void MergeSort(int x[],int n) { //非遞歸歸並排序
//元素數組為x，其長度為n
int i,j,k1,k2,l;
int *a;
for(i=1;i<=n-1;i=i*2)//i為插入排序的子段長度
{
for(j=1;j<=n-1;j=j+2*i)//j為進行插入排序的子段起始位置
{
a=(int *)malloc(2*i*sizeof(int));
l=0;k1=j;k2=j+i;
while((l<2*i)&&(k2<=n-1)&&(k2<j+2*i)&&(k1<j+i))
{//子段中，比較，移至輔助內存
if(x[k1]<x[k2])
{
a[l++]=x[k1];k1++;
}
else
{
a[l++]=x[k2];k2++;
}
}
if((k2>n-1)||(k2>=j+2*i))
{//子段的後一段超出數組范圍
for(;k1<j+i;k1++)
a[l++]=x[k1];
}
else//就只有第一段就超數組了
{
if(k1>=j+i)
{
for(;(k2<j+2*i)&&(k2<=n-1);k2++)
a[l++]=x[k2];
}
}
for(k1=0;k1<l;k1++)//最後移位
{
x[j+k1]=a[k1];
}free(a);
}
}
}
非遞歸的歸並排序，我以前寫的。
中間malloc與free的話，是為了方便管理不定大小的空間，這里需要malloc.h的頭文件
㈢ C語言歸並排序
/* 二路歸並排序演算法的源程序*/
#include<stdio.h>
#define MAXNUM 100
#define TRUE 1
#define FALSE 0
typedef int KeyType;
typedef int DataType;
typedef struct
{ KeyType key; /* 排序碼欄位 */
/*DataType info; 記錄的其它欄位 */ } RecordNode;
typedef struct
{ int n; /* n為文件中的記錄個數，n<MAXNUM */
RecordNode record[MAXNUM]; } SortObject;
/* r[low]到r[m]和r[m+1]到r[right]是兩個有序段 */
void merge(RecordNode r[], RecordNode r1[], int low, int m, int high)
{ int i=low, j=m+1, k=low;
while ( i<=m && j<=high ) /* 反復復制兩個段的第一個記錄中較小的 */
if (r[i].key<=r[j].key) r1[k++]=r[i++];
else r1[k++]=r[j++];
while (i<=m) r1[k++]=r[i++]; /* 復制第一個段的剩餘記錄 */
while (j<=high) r1[k++]=r[j++];/* 復制第二個段的剩餘記錄 */
}
/* 對 r 做一趟歸並，結果放到 r1 中 */
void mergePass(RecordNode r[], RecordNode r1[], int n, int length)
{ int i=0, j; /* length為本趟歸並的有序子段的長度 */
while (i+2*length-1<n)
{ merge(r,r1,i,i+length-1,i+2*length-1); /*歸並長length的兩個子段*/
i+=2*length; }
if(i+length-1<n-1) /* 剩下兩段，後一段長度小於length */
merge(r, r1, i, i+length-1, n-1);
else for(j=i; j<n; j++) r1[j]=r[j]; /* 將剩下的一段復制到數組r1 */
}
void mergeSort(SortObject * pvector)
{ RecordNode record[MAXNUM];
int length = 1;
while (length<pvector->n) /*一趟歸並，結果存放在數組record中*/
{ mergePass(pvector->record, record, pvector->n, length);
length*=2;
/* 一趟歸並，結果存回 */
mergePass(record, pvector->record, pvector->n, length);
length *= 2; }
}
SortObject vector = {8, 49,38,65,97,76,13,27,49};
main()
{ int i;
mergeSort(&vector);
for(i = 0; i < 8; i++) printf("%d ", vector.record[i]);
getchar();
}
㈣ c語言的歸並排序的完整程序
這個不難:
#include<stdio.h>
// 一個遞歸函數
void mergesort(int *num,int start,int end);
// 這個函數用來將兩個排好序的數組進行合並
void merge(int *num,int start,int middle,int end);
int main()
{
// 測試數組
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 進行合並排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之後
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}
//這個函數用來將問題細分
void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 歸並的基本思想
// 排左邊
mergesort(num,start,middle);
// 排右邊
mergesort(num,middle+1,end);
// 合並
merge(num,start,middle,end);
}
}
//這個函數用於將兩個已排好序的子序列合並
void merge(int *num,int start,int middle,int end)
{
int n1=middle-start+1;
int n2=end-middle;
// 動態分配內存，聲明兩個數組容納左右兩邊的數組
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;
//將新建的兩個數組賦值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 進行合並
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}
㈤ 高分送！！如何用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要改成你需要用的數~
㈥ 歸並排序演算法
兩種歸並排序演算法的實現：二路歸並排序和基本歸並排序（虛擬消除遞歸的二路歸並排序）
#define ARRAY_SIZE 1024
int B[1024]; //使用一個全局變數，避免歸並排序中每次都重新申請和釋放空間造成的開銷
template <typename T>
void Merge(T A[], int l, int m, int h)
{
int i = l;
int j = m+1;
int k = 0;
while(i<=m&&j<=h)
{
if(A[i]<A[j])
{
B[k++] = A[i];
i++;
}
else
{
B[k++] = A[j];
j++;
}
}
while(i<=m)
{
B[k++] = A[i++];
}
while(j<=h)
{
B[k++] = A[j++];
}
for(i=l; i<=h; i++)
{
A[i] = B[i-l];
}
}
//二路歸並排序的實現
template <typename T>
void MergeSort(T a[], int l, int h)
{
int m = (h+l)/2;
if(l>=h)
{
return;
}
if(l+1==h)
{
if(a[l]>a[h])
{
std::swap(a[l], a[h]);
}
return;
}
MergeSort(a, l, m);
MergeSort(a, m+1, h);
Merge(a, l, m, h);
}
//將a經過步長s歸並到b中，n表示數組的大小
template <typename T>
void Merge2(T a[], T b[], int s, int n)
{
int m = 0;
//從頭至尾按照步長s進行相鄰數據的合並
for(int i=0; i<n; i+=2*s)
{
int j = i; //合並的第一組數的起始位置
int k = i+s; //合並的第二組數的起始位置
int jE = i+s; //合並的第一組數的起始位置
int kE = i+2*s; //合並的第二組數的起始位置
while((j<jE)&&(k<kE)&&j<n && k<n)
{
if(a[j]<a[k])
{
b[m++] = a[j];
j++;
}
else
{
b[m++] = a[k];
k++;
}
}
while((j<jE)&&(j<n))
{
b[m++] = a[j++];
}
while((k<kE)&&(k<n))
{
b[m++] = a[k++];
}
}
}
//基本歸並排序，虛擬消除遞歸
template <typename T>
void MergeSort2(T a[], int n)
{
int s = 1; //merge 的步長
T* b = new T[n];
while(s<n)
{
Merge2(a, b, s, n); //由a合並到b
s += s;
Merge2(b, a, s, n); //由b合並到a
s += s;
}
delete[] b;
}
//使用如下代碼在VS2005中可以對兩種歸並排序進行性能比較，
//基本歸並排序的時間性能稍微好一點，基本歸並排序直接對數據按步長Merge，
//而二路歸並排序需要將數據先不斷的分層，到為一個或者兩個元素時再進行Merge
void main()
{
int * p = new int[ARRAY_SIZE];
int i = 0;
for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort(p, 0, ARRAY_SIZE-1);
for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort2(p, ARRAY_SIZE);
delete[] p;
}
㈦ 輸入一組整數對該序列進行簡單選擇和歸並排序（數據結構用c語言寫啊）
給你一個歸並排序的具體演算法和分析：
兩路歸並排序演算法思路:
①.
把n個記錄看成n個長度為l的有序子表
;
②.
進行兩兩歸並使記錄關鍵字有序,得到n/2個長度為2的有序子表;
③.
重復第②步直到所有記錄歸並成一個長度為n的有序表為止;
具體演算法:
//
歸並操作
template
static
void
merge
(typearray[],
int
p,
int
q,
int
r){
int
i
,
k
;
int
begin1
,
end1
,
begin2
,
end2
;
int*
temp
=
(int*)malloc((r-p)*sizeof(int))
;
begin1
=
p
;
end1
=
q
;
begin2
=
q+1
;
end2
=
r
;
k
=
0
;
while
(begin1
<=
end1
&&
begin2
<=
end2){
if
(array[begin1]
<
array[begin2]){
temp[k]
=
array[begin1]
;
begin1
++
;
}
else{
temp[k]
=
array[begin2]
;
begin2
++
;
}
k
++
;
}
while
(begin1
<
end1)
temp[k++]
=
array[begin1++]
;
while
(begin2
<
end2)
temp[k++]
=
array[begin2++]
;
for
(i
=
0
;
i
<
(r-p)
;
i
++)
array[p+i]
=
temp
;
free(temp)
;
}
//--------------------------------------------------------------------------------
template
void
mergesort(typearray[],
unsigned
int
first,
unsigned
int
last){
int
mid
=
0
;
if
(first
<
last)
{
mid
=
(first+last)/2
;
mergesort
(array,
first,
mid)
;
mergesort
(array,
mid+1,
last)
;
merge
(array,
first,
mid,
last)
;
}
}
㈧ c語言歸並排序
int merge(int *a, int begin, int end){
int n = end - begin +1;
int mid = (begin+end)/2;
int i = begin;
int j = mid+1;
int k = begin;
while(i<=mid&&j<=end){
if(a[i]<=a[j]){
c[k]=a[i];
k++;
i++;
}
else{
c[k]=a[j];
k++;
j++;
}
}
for(;i<=mid;i++,k++){
c[k]=a[i];
}
for(;j<=end;j++,k++){
c[k]=a[j];
}
for(i=begin;i<=end;i++){
a[i]=c[i];
}
return 1;
}
㈨ 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 Merger<T>::sub_Merger(T * array, size_t n)
{
if(n == 1) //~ 遞歸終止
return ;
else if(n == 2) //~ 遞歸終止
{
if( array[0] > array[1] )
{
T tmp = array[0];
array[0] = array[1];
array[1] = tmp;
}
}
else
{
/* 將數組均分為兩部分，分別排好，然後歸並*/
size_t m = n / 2;
//~ 分別排序
sub_Merger(array, m + 1);
sub_Merger(array + m + 1, n - m - 1);
//~ 歸並
size_t i = 0, j = m + 1, k = 0;
memcpy(extra, array, (m + 1)* sizeof(T));
while( i <= m && j < n)
{
array[k++] = extra[i] < array[j] ? extra[i++]:array[j++];
}
while(i <= m)
{
array[k++] = extra[i++];
}
}
}