順序表排序演算法

⑴ 線性表的排序法有哪些

說一下我的見解：不一定對 僅供參考

首先 線性表分為順序表和鏈式表 其中後者又可分為動態鏈表和靜態鏈表

這兩種鏈表又可進一步分為：單向無循環 雙向無循環 單向有循環 雙向有循環

應該說一般的排序演算法在單鏈表都是可以的

插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序

只是在不同的線性表中不同的演算法會有效率上的不同
靜態鏈表是比較適合需要做排序的 因為它既具有順序表的順序存取功能 又具有鏈式表易於移動元素的功能

Best Wishes!

⑵ c語言中 順序表的選擇排序是什麼

選擇排序（Selection sort）是一種簡單直觀的排序演算法。工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
以下是一個實現選擇排序的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
//將list中的n個數據，通過選擇排序演算法排序。
void selete_sort(int list[], int n)
{
int i, j, min, temp;
for (i = 0; i < n - 1; i++){
min = i;
for (j = i + 1; j < n; j++)//找出最小元素的下標。
if (list[j] < list[min])
min = j;
SWAP(list[i], list[min], temp);//交換最小元素到當前起始位置。

⑶ 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；

學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。

排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。

2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。

排序的穩定性

當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。

排序方法的分類

1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。

2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

排序演算法分析

1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。

2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。

3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度

（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。

（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。

文件的順序存儲結構表示

#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時間將排序分為四類：

（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；

（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
如桶、箱和基數排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

影響排序效果的因素

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。

4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

⑷ 順序表的建立、合並、歸並演算法實現

#include <stdio.h>
#include <malloc.h>

void disp(int *a,int n);
int * create(int n);
int * merger_link(int *a,int *b,int n,int m);
void merge(int *a, int low, int m, int high);
void merge_sort(int *a,int low,int high);

int main()
{
int *a=NULL,*b=NULL,*c=NULL; //順序表
int n,m;

printf("輸入第一個順序表的大小:\n");
scanf("%d",&n);
a = create(n);

printf("輸入第二個順序表的大小:\n");
scanf("%d",&m);
b = create(m);

printf("合並:\n");
c = merger_link(a,b,n,m);
disp(c,n+m);

printf("歸並排序:\n");
merge_sort(c,0,n+m-1);
disp(c,n+m);

if(a) free(a);
if(b) free(b);
if(c) free(c);

return 0;
}

/*建立*/
int *create(int n)
{
int *p,i;
p = (int *)malloc(sizeof(int)*n);
printf("輸入順序表的各個數值(整數，以空格分開):\n");

for(i=0;i<n;i++)
scanf("%d",&p[i]);
return p;
}

/*合並,把兩個表連接起來*/
int *merger_link(int *a,int *b,int n,int m)
{
int *p,i=0,j=0;
p = (int *)malloc(sizeof(int)*(n+m));

while(n--)
p[i++] = a[j++];

j=0;

while(m--)
p[i++] = b[j++];

return p;
}

/*將兩個有序段合成一個有序段*/
void merge(int *a, int low, int m, int high)
{
int i=low, j=m+1 ,p=0;
int *t;
t = (int *)malloc((high-low+1)*sizeof(int));
while(i<=m && j<=high)
t[p++]=(a[i] <= a[j]) ? a[i++] :a[j++];
while(i <= m)
t[p++]=a[i++];
while(j <= high)
t[p++]=a[j++];
for(p=0, i=low; i<=high; p++,i++)
a[i]=t[p];
free(t);
}

/*歸並排序,二路歸並*/
void merge_sort(int *a,int low,int high)
{
int mid;
if(low<high)
{
mid = (low+high)/2;
merge_sort(a, low, mid);
merge_sort(a, mid+1, high);
merge(a, low, mid, high);
}
}

/*顯示*/
void disp(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

⑸ 排序有幾種方法

一. 冒泡排序

冒泡排序是是一種簡單的排序演算法。它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把它們交換過來。遍歷數列的工作是重復的進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端

1.冒泡排序演算法的運作如下：
（1）比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素還是最大的數
（3）針對所有的元素重復以上的步驟，除了最後一個
二. 選擇排序
選擇排序是一種簡單直觀的排序演算法。他的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置（末尾位置），然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢
選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，他們當中至少有一個將被移到最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動 元素的排序方法中，選擇排序屬於非常好的一種
三. 插入排序

插入排序是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在從後向前掃描的過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間
四. 快速排序
快速排序，又稱劃分交換排序。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都要小，然後再按此方法對兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
五 希爾排序過程

希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
六. 歸並排序

歸並排序是採用分治法（把復雜問題分解為相對簡單的子問題，分別求解，最後通過組合起子問題的解的方式得到原問題的解）的一個非常典型的應用。歸並排序的思想就是先遞歸分解數組，再合並數組

將數組分解最小之後，然後合並兩個有序數組，基本思路是比較兩個數組的最前面的數，水小九先取誰，取了後相應的指針就往後移一位。然後比較，直至一個數組為空，最後把另一個數組的剩餘部分復制過來即可

⑹ C語言順序表的基本操作

#include<stdio.h>
#include<stdlib.h>

typedefintDataType;//定義數據數據類型

typedefstruct{
	DataType*data;//data指向數據區的首個數據
	intlength;//數據長度
}SqList;

voidSort(SqList*L){
	inti,j,k;
	DataTypetmp;
	for(i=0;i<L->length-1;++i){
		k=i;
		for(j=i+1;j<L->length;++j)
			if(L->data[k]>L->data[j])
				k=j;
		if(k!=i){
			tmp=L->data[k];
			L->data[k]=L->data[i];
			L->data[i]=tmp;
		}
	}
}

SqList*CreateList(DataTypea[],intn){
	inti;
	SqList*L;
	L=(SqList*)malloc(sizeof(SqList));
	L->data=(DataType*)malloc(n*sizeof(DataType));
	L->length=n;
	for(i=0;i<n;++i)L->data[i]=a[i];
	Sort(L);
	returnL;
}

intInsertList(SqList*L,DataTypex){
	inti,j;
	for(i=0;i<L->length;i++){
		if(x<=L->data[i]){
			for(j=L->length;j>=i;j--)
				L->data[j+1]=L->data[j];//結點後移
			L->data[i]=x;
			L->length++;
			return1;
		}
	}
	L->data[L->length++]=x;
	return1;
}

intRemoveListElem(SqList*L,DataTyped){
	inti,j;
	for(i=0;i<L->length;++i){
		if(L->data[i]==d){
			for(j=i;j<L->length-1;++j)
				L->data[j]=L->data[j+1];
			L->length--;
			return1;
		}
	}
	return0;
}

SqList*AndList(SqList*A,SqList*B){/*A∩B*/
	inti,j,k=0;
	intlen=(A->length>B->length)?B->length:A->length;
	SqList*C=(SqList*)malloc(sizeof(SqList));
	C->length=len;
	C->data=(DataType*)malloc(len*sizeof(DataType));
	for(i=0;i<A->length;++i){
		for(j=0;j<B->length;++j){
			if(A->data[i]==B->data[j]){
				C->data[k++]=A->data[i];
				break;
			}
		}
	}
	C->length=k;
	returnC;
}

SqList*OrList(SqList*A,SqList*B){/*A∪B*/
	inti,j,flag;
	DataTypee;
	SqList*C=(SqList*)malloc(sizeof(SqList));
	C->length=A->length+B->length;
	C->data=(DataType*)malloc(C->length*sizeof(DataType));
	for(i=0;i<A->length;++i)C->data[i]=A->data[i];
	for(i=0;i<B->length;++i){
		e=B->data[i];
		flag=1;
		for(j=0;j<C->length;++j){
			if(e==C->data[j]){
				flag=0;
				break;
			}
		}
		if(flag)InsertList(C,e);
	}
	returnC;
}

voidPrintList(SqList*L){
	inti;
	for(i=0;i<L->length;++i)
		printf("%d",L->data[i]);
	printf("
");
}

voidFreeList(SqList*L){
	free(L->data);
	free(L);
}

voidmain(){
	DataTypex;
	DataTypearra[]={36,24,31,5,90,65,70,39,37};
	DataTypearrb[]={9,8,43,51,37,89,33,46,29,80,56};
	intalen=sizeof(arra)/sizeof(arra[0]);
	intblen=sizeof(arrb)/sizeof(arrb[0]);
	SqList*A=CreateList(arra,alen);
	printf("A線性表為:");
	PrintList(A);
	SqList*B=CreateList(arrb,blen);
	printf("B線性表為:");
	PrintList(B);
	SqList*C=AndList(A,B);
	SqList*D=OrList(A,B);
	printf("C=A∩B:");
	PrintList(C);
	printf("D=A∪B:");
	PrintList(D);

	printf("在D表中插入數據:");
	scanf("%d",&x);
	InsertList(D,x);
	printf("D表插入x後:");
	PrintList(D);
	
	printf("刪除D表中數據:");
	scanf("%d",&x);
	RemoveListElem(D,x);
	printf("刪除x後的D表為:");
	PrintList(D);
	FreeList(A);
	FreeList(B);
	FreeList(C);
	FreeList(D);
}

⑺ （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;
}

⑻ 1.求設計一個演算法（用遞歸實現），實現對一個順序表的數值排序。最好是用主流語言。謝謝

//歸並排序

#include<stdio.h>
#include<string.h>

int num[2000];
int temp[2000];

void merge(int left,int right)
{
int center=(left+right)/2;
int i=left,j=center+1,help=left;
while(i<=center&&j<=right)
{
if(num[i]>num[j])
{
temp[help++]=num[j++];
}
else
{
temp[help++]=num[i++];
}
}
while(i<=center)
{
temp[help++]=num[i++];
}
while(j<=right)
{
temp[help++]=num[j++];
}
for(i=left;i<=right;i++)
num[i]=temp[i];
}

void mergesort(int left,int right)
{
if(right<=left)
return ;
int center=(left+right)/2;
mergesort(left,center);
mergesort(center+1,right);
merge(left,right);
}

//
歸並排序演算法
合並排序（MERGE SORT）是又一類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成一個新的有序數據序列，因此它又叫歸並演算法。它的基本思想就是假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。
例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那麼採用歸並排序演算法的操作過程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長度為1的7個子序列組成
第一次合並之後 [38 49] [65 97] [13 76] [27]
看成由長度為1或2的4個子序列組成
第二次合並之後 [38 49 65 97] [13 27 76]
看成由長度為4或3的2個子序列組成
第三次合並之後 [13 27 38 49 65 76 97]
合並演算法的核心操作就是將一維數組中前後相鄰的兩個兩個有序序列合並成一個有序序列。合並演算法也可以採用遞歸演算法來實現，形式上較為簡單,但實用性很差。合並演算法的合並次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這一規律,當有N個子序列時可以推斷出合並的次數是X(2 >=N,符合此條件的最小那個X)。
其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)

⑼ 順序表的排序，二分法查找的c語言程序

#include<stdio.h>
int fun(int a[],int n,int key)
{i
nt low,mid,high;//low、mid、high是三個索引分別指向數組的下標low=0;//low指向數組a[]的第一個元素，即下表為0的元素
high=n-1;//lhigh指向數組a[]的最一個元素，即下表為n-1的元素，n為數組的長度
while(low<=high)//循環終止條件是low>high的時候
{
mid=(low+high)/2;//所謂二分查找就在這里，每次都讓mid指向數組下標等於low和high之和的一半的元素i
f(key<a[mid])//如果a【mid】大於要查找的元素，說明要查找的元素在low和mid之間，這是需要把high重新置為mid-1
(high=mid-1);//這里應該是{}，不能使（）吧
else if(key>a[mid])//這里同理，如果a【mid】小於要查找的元素，說明要查找的元素在mid和high之間，這是需要把low重新置為mid+1
(low=mid+1);
else
return mid;//剩下的就是相等的情況，直接返回mid就是查找到的結果
}
return -1;//執行到這一步就說明，low>high，沒有找到要查找的元素，返回-1表示沒有結果
}
main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int a,b,c;
b=4;
c=fun(a,10,b);
if(c==1)
printf("not found");
else
printf("psition %d\n",c);
}

⑽ 順序表的排序演算法

給你舉一些比較常用的排序法：

交換排序法
冒泡排序 | 雞尾酒排序 | 奇偶排序 | 梳排序 | 侏儒排序 | 快速排序 |臭皮匠演算法 | Bogo排序
選擇排序法
選擇排序 | 堆排序 | Smooth排序 | 笛卡爾樹排序 | 錦標賽排序 | 循環排序
插入排序法
插入排序 | 希爾排序 | 二叉查找樹排序 | 圖書館排序 | Patience排序
歸並排序法
歸並排序 | 多相歸並排序 | Strand排序
分布排序法
美國旗幟排序 | 珠排序 | 桶排序 | 爆炸排序 | 計數排序 | 鴿巢排序 | 相鄰圖排序 | 基數排序 | 閃電排序
混合排序法
Tim排序 | 內省排序 | Spread排序 | 反移排序 | J排序
其他
雙調排序器 | Batcher歸並網路 | 兩兩排序網路