線性排序c語言,簡單排序C語言

本文目錄一覽：

• 1、c語言排序和查找？
• 2、C 語言編程 （順序線性表）
• 3、c語言 快速排序。。
• 4、二級C語言排序技術2

c語言排序和查找？

1）利用readData()函數從data1.txt中讀入不同規模的數據存入數組，

編寫基於數組的順序查找算法，測試數據量為1萬、5萬、10萬、20萬、

30萬、40萬和50萬時的數據查詢時間。

算法代碼如下：



1 int seqsearch(int a[],int n,int key)

2 {

3 int k=n-1;

4 while(k=0a[k]!=key)

5 k–;

6 return (k);

7 }



2）利用readData()函數從data2.txt中讀入不同規模的有序數據存入數組，

編寫基於數組的二分查找算法，測試數據量為1萬、5萬、10萬、20萬、30萬、

40萬和50萬時的數據查詢時間。

算法代碼如下：



1 int binSearch(int a[],int n,int key)

2 {

3 int low=0;

4 int high=n-1;

5 int mid;

6 while(low=high)

7 {

8 mid=(low+high)/2;

9 if(a[mid]==key) return mid;

10 if(a[mid]key)

11 high=mid-1;

12 else

13 low=mid+1;

14 }

15 return -1;

16 }



3）請設計冒泡排序算法函數void bubbleSort(int a[],int n)，對a[1]..a[n]進行升序排序。

並測試在不同數據規模下的排序效率。

算法代碼如下：



1 void bubbleSort(int a[],int n)

2 {

3 int i=1,j,flag=1;

4 while(i=n-1flag)

5 {

6 flag=0;

7 for(j=1;j=n-1-i;j++)

8 if(a[j+1]a[j])

9 {

10 a[0]=a[j];

11 a[j]=a[j+1];

12 a[j+1]=a[0];

13 flag=1;

14 }

15 i++;

16 }

17 }



C 語言編程 （順序線性表）

#ifndef FUNS_H

#define FUNS_H

void error( char *, … ); /* 輸出錯誤信息，退出程序 */

void flush_stdin( void ); /* 清空「輸入緩衝區」 */

#endif

#ifndef SQLIST_H

#define SQLIST_H

#define INITSIZE 100 /* 順序表初始空間分配量 */

#define INCREMENT 10 /* 順序表空間分配增量 */

typedef int ElemType; /* 聲明ElemType代表的數據類型 */

/* 定義順序表結構 */

typedef struct {

ElemType *elem; /* 存儲空間基址 */

unsigned length; /* 當前長度 */

unsigned listsize; /* 當前空間分配量 */

} Sqlist;

/* 函數聲明 */

int InitList(Sqlist *); /* 創建順序表 */

int InputList(Sqlist *); /* 輸入數據 */

int InsertList(Sqlist *, unsigned); /* 插入數據 */

void DelList(Sqlist *, unsigned, unsigned); /* 刪除數據 */

int Union(Sqlist *, Sqlist *); /* 求順序表並集 */

void Purge(Sqlist *); /* 刪除表中重複元素 */

void Purge2(Sqlist *); /* 刪除表中重複元素 */

void Bubble(Sqlist *, unsigned); /* 冒泡排序 */

int Compare(Sqlist *, Sqlist *); /* 比較兩個順序表的大小 */

void Exchange(Sqlist *, unsigned); /* 前N個元素和後M個元素互換 */

int Location(Sqlist *, ElemType); /* 求元素位置 */

void Disp(Sqlist *, unsigned); /* 顯示順序表信息 */

void Three(Sqlist *, unsigned, unsigned); /* 三次逆轉法 */

#endif /* end of sqlist.h */

#include stdio.h

#include stdarg.h

#include stdlib.h

#include “../header/funs.h”

/* begin of error 05-8-15 18:40 */

void error( char *fmt, … )

{ /* 輸出錯誤信息，退出程序 */

va_list args;

va_start( args, fmt );

fprintf( stderr, “error: ” );

vfprintf( stderr, fmt, args );

fprintf( stderr, “\n” );

va_end( args );

exit( -1 );

} /* end of error */

/* begin of flush_stdin 05-8-31 19:30 */

void flush_stdin( void ) /* 清空「輸入緩衝區」 */

{

int c;

if ( !feof(stdin) ) {

while( ( c=getchar() ) != ‘\n’ c != EOF )

;

}

} /* end of flush_stdin */

#include stdio.h

#include stdlib.h

#include “../header/sqlist.h”

/* begin of InitList 05-8-13 0:30 */

int InitList( Sqlist *L ) /* 創建順序表 */

{

/* malloc 返回值為 void 類型，不需要顯式轉換 */

L-elem = malloc( INITSIZE * sizeof *L-elem ); /* 分配初始空間 */

if ( !L-elem ) {

return 0; /* 創建失敗返回 0 */

}

/* 創建成功，初始化字符串長度和順序表長度 */

L-length = 0;

L-listsize = INITSIZE;

return 1; /* 創建成功返回 1 */

} /* end of InitList */

/* begin of InputList 05-8-13 2:15 */

int InputList(Sqlist *L) /* 接受用戶輸入的字符串 */

{

unsigned i;

L-length = 0;

for ( i = 0; ( L-elem[i]=getchar() ) != ‘\n’ L-elem[i] != EOF ; ++i ) {

++L-length;

if ( L-length == L-listsize ) { /* 如果順序表已滿 */

ElemType *newbase = realloc( L-elem, /* 增加空間 */

( L-listsize + INCREMENT ) * sizeof *L-elem );

if ( newbase ) { /* 如果分配成功 */

L-elem = newbase; /* 將指針指向新分配好的空間 */

L-listsize += INCREMENT; /* 增大 listsize 的值 */

} else { /* 分配空間失敗 */

return 0; /* 增加空間失敗，返回 0 */

}

}

}

return 1;

} /* end of InputList */

/* begin of InsertList 05-8-13 5:00 */

int InsertList(Sqlist *L, unsigned pos) /* 插入數據 */

{

Sqlist tmp; /* 用於暫時存儲用戶輸入的字符 */

long i;

if ( !InitList( tmp ) ) {

return 0;

}

if ( InputList( tmp ) ) {

if ( !tmp.length ) {

free(tmp.elem);

return 1;

}

if ( L-listsize – L-length tmp.length ) {

ElemType *newbase = realloc( L-elem,

( L-listsize + tmp.length ) * sizeof *L-elem );

if ( newbase ) {

L-elem = newbase;

L-listsize += tmp.length;

} else {

free(tmp.elem);

return 0;

}

}

–pos;

/* 移動字符 */

for ( i = L-length – 1; i = (long)pos; –i ) {

L-elem[i + tmp.length] = L-elem[i];

}

i = 0;

while ( i (long)tmp.length ) {

L-elem[pos++] = tmp.elem[i++];

}

L-length += tmp.length; /* 更新字符串長度 */

free(tmp.elem);

return 1;

}

free(tmp.elem);

return 0;

} /* end of InsertList */

/* begin of DelList 05-8-13 12:00 */

void DelList(Sqlist *L, unsigned pos, unsigned size)

{

for ( –pos; pos + size L-length; ++pos ) {

L-elem[pos] = L-elem[pos + size];

}

L-length -= size;

} /* end of DelList */

/* begin of Union 05-8-13 12:30 */

int Union(Sqlist *L1, Sqlist *L2){ /* 求順序表並集 */

unsigned k;

/* 開始進行並集操作 */

if ( L1 == L2 ) { /* 如果 L1 和 L2 為同一順序表 */

return 1;

}

for ( k = 0; k L2-length; ++k ) {

/* 在順序表 L1 中找不到順序表 L2 中的第k+1個元素，將第k+1個元素插入順序表 L1 */

if ( !Location( L1, L2-elem[k]) ) {

if ( L1-length == L1-listsize ) { /* 如果順序表已滿 */

ElemType *newbase = realloc( L1-elem, /* 增加空間 */

( L1-listsize + INCREMENT ) * sizeof *L1-elem );

if ( newbase ) {

L1-elem = newbase;

L1-listsize += INCREMENT;

} else {

return 0; /* 增加空間失敗，返回 */

}

}

L1-elem[ L1-length ] = L2-elem[k]; /* 插入到表 L1 */

L1-length++; /* 表 L1 長度增加 */

}

}

return 1; /* 無誤返回 */

} /* end of Union */

/* begin of Purge 05-8-13 13:00 */

void Purge(Sqlist *L) /* 刪除表中重複元素 */

{

unsigned i, j, k;

for ( i = 0; i L-length; i++ ) {

for ( j = i+1; j L-length; ) {

if ( L-elem[i] == L-elem[j] ) { /* 若找到重複元素 */

for ( k = j; k L-length; k++ ) { /* 刪除重複元素 */

L-elem[k] = L-elem[k+1];

}

L-length–; /* 順序表長度減1 */

}

else {

j++;

}

}

}

} /* end of Purge */

/* begin of Purge2 05-8-13 13:20 */

void Purge2(Sqlist *L) /* 刪除表中重複元素 */

{

Sqlist T = *L;

unsigned i;

T.length = 1;

for ( i = 1; i L-length; i++ ) {

if ( !Location( T, L-elem[i] ) ) { /* 若找不到重複元素 */

T.elem[T.length] = L-elem[i]; /* 插入 */

T.length++; /* 更新長度 */

}

}

L-length = T.length; /* 更新長度 */

} /* end of Purge2 */

/* begin of Bubble 05-8-13 14:10 */

void Bubble(Sqlist *L, unsigned ascend)

{

ElemType temp;

unsigned i, j, k = L-length – 1;

unsigned l;

if ( !L-length ) {

return;

}

for ( l = 1; l; k– ) {

l = 0;

for ( i = 0, j = 1; i k; i++, j++ ) {

/* 根據 ascend 的值進行升序或者降序排列 */

if ( ( L-elem[i] L-elem[j] ) ^ ascend ) {

temp = L-elem[i];

L-elem[i] = L-elem[j];

L-elem[j] = temp;

l = 1;

}

}

}

} /* end of Bubble */

/* begin of Compare 05-8-13 14:40 */

int Compare(Sqlist *L1, Sqlist *L2) /* 比較兩個順序表 */

{

unsigned k;

if ( L1 == L2 ) {

return 0;

}

for ( k = 0; k L1-length k L2-length; k++ ) {

if ( L1-elem[k] L2-elem[k] ) {

return 1;

}

if ( L1-elem[k] L2-elem[k] ) {

return -1;

}

}

return L1-length – L2-length;

} /* end of Compare */

/* begin of Exchange 05-8-13 15:10 */

void Exchange(Sqlist *L, unsigned i) /* 前N個元素和後M個元素互換 */

{

/* 三次逆轉 */

Three( L, 0, i-1 );

Three( L, i, L-length-1 );

Three( L, 0, L-length-1 );

} /* end of Exchange */

/* begin of Three 05-8-13 14:55 */

void Three(Sqlist *L, unsigned i, unsigned j) /* 三次逆轉法 */

{

ElemType temp;

for (; i j; i++, j– ) {

temp = L-elem[i];

L-elem[i] = L-elem[j];

L-elem[j] = temp;

}

} /* end of Three */

/* begin of Location 05-8-13 12:10 */

int Location(Sqlist *L, ElemType elem) /* 求元素位置 */

{

unsigned l;

for ( l=0; l L-length L-elem[l] != elem; l++ ) {

;

}

if ( l == L-length ) { /* 在順序表中找不到elem */

return 0; /* 返回0 */

}

return ++l; /* 找到則返回元素位置 */

} /* end of Location */

/* begin of Disp 05-8-13 15:20 */

void Disp( Sqlist *L, unsigned total_lists ) /* 顯示順序表信息 */

{

unsigned short i;

unsigned j;

printf( “\n當前一共有 %u 個順序表。每個表的數據如下：\n”, total_lists );

for ( i = 0; i total_lists; i++ ) {

printf( “\n順序表 %d ：”, i+1 );

for ( j = 0; j L[i].length; j++ ) {

printf( “%c”, L[i].elem[j] );

}

printf( “\n字符串長度：%u 順序表長度：%u\n”, L[i].length, L[i].listsize);

}

} /* end of Disp */

#include stdio.h

#include stdlib.h

#include “header/sqlist.h”

#include “header/funs.h”

#define MAX_LISTS 10 /* 最多可以建立的順序表個數 */

/* 函數聲明 */

char Menu( void ); /* 打印菜單，請用戶選擇 */

unsigned Choose( unsigned, unsigned, char ); /* 接收用戶輸入的選擇 */

static int tmp; /* tmp 用於清空輸入緩衝區 */

const char *msg[] = { “\n請問您要對哪個順序表（%u — %u）進行操作：”,

“\n請輸入刪除數目（%u — %u）：”,

“\n請輸入字符串（原有數據會被覆蓋）：”,

“\n請輸入插入位置（%u — %u）：”,

“\n請輸入刪除位置（%u — %u）：”,

“\n此項操作至少要有兩個順序表才能進行。請再建立一個順序表。”,

“\n重複元素已被刪除。”,

“\n請問您要進行降序排序還是升序排序（%u 代表降序，%u 代表升序）：”,

“\n順序表 %u %c 順序表 %u”,

“\n請輸如互換點（%u — %u）：”,

“\n排序完成。” };

int main( void )

{

Sqlist L[ MAX_LISTS ]; /* 順序表數組 */

char choice; /* 記錄用戶選擇的操作 */

unsigned short total_lists = 0; /* 用於記錄目前一共有多少個順序表 */

char *init_msg[] = { “內存不足！創建失敗。”, /* 創建順序表的提示信息 */

“順序表創建成功！您可以開始對順序表進行操作了。” };

printf( “\n請先創建一個順序表。最多可以創建 %u 個順序表。\n”, MAX_LISTS );

while ( choice = Menu() ) { /* 根據用戶輸入選擇函數運行 */

if ( !total_lists choice != 1 ) {

printf( “\n請先創建一個順序表。最多可以創建 %u 個順序表。\n”, MAX_LISTS );

} else {

switch ( choice ) {

case 1 :

if ( total_lists == MAX_LISTS ) { /* 達到最大限制 */

printf( “\n最多只能建立 %u 個順序表。\n”, MAX_LISTS );

} else {

int i = InitList( L[total_lists] );

total_lists += i; /* 更新順序表數目 */

printf( “\n%s\n”, init_msg[i] );

}

break;

case 2 :

{

unsigned num = Choose( total_lists, 1, 0 );

printf( “%s”, msg[choice] );

InputList(L[num-1]);

break;

}

case 3 :

{

unsigned num, pos;

num = Choose( total_lists, 1, 0 );

pos = Choose( L[num-1].length + 1, 1, choice );

printf( “\n請輸入字符串：” );

/* 在第 num 個順序表的第 pos 個元素處開始插入 */

InsertList( L[num-1], pos );

break;

}

case 4 :

{

unsigned num, pos, size;

num = Choose( total_lists, 1, 0 );

if ( !L[num-1].length ) {

printf( “\n順序表為空，不能進行刪除操作。\n” );

break;

}

pos = Choose( L[num-1].length, 1, choice );

size = Choose( L[num-1].length – pos + 1, 1, 1 );

/* 從第 num 個順序表的第 pos 個位置開始，刪除 size 個元素 */

DelList( L[num-1], pos, size );

break;

}

case 5 :

{

unsigned num1, num2;

if ( total_lists 2 ) {

puts( msg[choice] );

break;

}

num1 = Choose( total_lists, 1, 0 );

num2 = Choose( total_lists, 1, 0 );

if ( Union( L[num1-1], L[num2-1] ) ) {

printf( “\n並集操作完成。操作結果保存於順序表 %u 。\n”, num1 );

} else {

printf( “\n並集操作失敗。\n” );

}

break;

}

case 6 :

{

unsigned num = Choose( total_lists, 1, 0 );

Purge( L[num-1] );

puts( msg[choice] );

break;

}

case 7 :

{

unsigned num = Choose( total_lists, 1, 0 );

unsigned ascend = Choose( 1, 0, choice );

Bubble( L[num – 1], ascend );

puts( msg[10] );

break;

}

case 8 :

{

unsigned num1, num2;

int flag;

if ( total_lists 2 ) {

puts( msg[5] );

break;

}

num1 = Choose( total_lists, 1, 0 );

num2 = Choose( total_lists, 1, 0 );

flag = Compare( L[num1-1], L[num2-1] );

if ( !flag ) {

flag = ‘=’;

} else if ( flag 0 ) {

flag = ”;

} else {

flag = ”;

}

printf( msg[choice], num1, flag, num2 );

break;

}

case 9 :

{

unsigned num = Choose( total_lists, 1, 0 ), point;

if ( L[num-1].length 2 ) {

puts(“\n元素太少，不能進行互換。”);

break;

}

point = Choose( L[num-1].length – 1, 1, choice );

Exchange( L[num-1], point );

puts( “\n互換完成。” );

break;

}

case 10 :

{

unsigned num = Choose( total_lists, 1, 0 );

Purge2( L[num-1] );

puts( msg[6] );

break;

}

break;

default:

break;

}

}

/* 打印順序表的內容 */

Disp( L, total_lists );

}

while ( total_lists ) {

free( L[ –total_lists ].elem ); /* 釋放內存 */

}

puts( “\n感謝您使用我們的產品！請按回車退出…” );

getchar();

return 0; /* 退出程序 */

} /* end of main */

/* begin of Choose 05-8-13 3:00 */

unsigned Choose( unsigned up, unsigned low, char c )

{

unsigned num = 0;

do {

printf( msg[c], low, up );

scanf( “%u”, num );

flush_stdin(); /* 清空輸入緩衝區 */

} while ( num up || num low );

return num;

} /* end of Choose */

/* begin of Menu 05-8-12 23:20 */

char Menu( void ) /* 打印菜單，並且接受用戶輸入 */

{

int ch = -1; /* ch 用於接收用戶輸入 */

for (;;) {

printf( “\n********************************\n”

“* 1. 創建順序表 *\n”

“* 2. 輸入數據 *\n”

“* 3. 插入數據 *\n”

“* 4. 刪除數據 *\n”

“* 5. 求順序表並集 *\n”

“* 6. 刪除重複元素 *\n”

“* 7. 冒泡排序 *\n”

“* 8. 比較順序表大小 *\n”

“* 9. 前N個元素和後M個元素互換 *\n”

“*10. 刪除重複元素(2) *\n”

“* 0. 退出 *\n”

“********************************\n\n”

“請輸入您要執行的操作（按回車確定）：”);

scanf( “%d”, ch );

flush_stdin(); /* 清空輸入緩衝區 */

if ( ch 11 ch -1 ) {

break; /* 輸入合法，退出循環 */

}

/* 非法輸入，請用戶重新輸入 */

puts(“\n請輸入 0 到 10 之間的數字。\n”);

} /* end of for */

return ch; /* 返回操作號 */

} /* end of Menu */

給你的郵箱，發，，百度難編輯

已經發到你的郵箱了,請注意查收.

c語言 快速排序。。

int quickSortpx(SqList list,int first,int end)

{int compare;

compare=list.elem[first];

for(;firstend;)

{while(firstend list.elem=compare)

{

end–;

}

if(firstendlist.elemcompare)

{

list.elem[first]=list.elem;

first++;

}

while(firstend list.elem[first]=compare)

{

first++;

}

if(firstendlist.elem[first]compare)

{

list.elem=list.elem[first];

end–;

}}

/*你沒有把取出的第一個元素放回鏈表，請在這裡添加*/

list.elem=compare; /*或list.elem[first]=compare;*/

return(first);}

二級C語言排序技術2

（1）交換類排序法

交換類排序法是指藉助數據元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬於交換類排序方法。

冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描，需要的比較次數為n(n–1)/2。但這個工作量不是必需的，一般情況下要小於這個工作量。

快速排序法也是一種交換類的排序方法，但由於它比冒泡排序法的速度快，因此稱之為快速排序法。其關鍵是對線性表進行分割，以及對各分割出的子表再進行分割。

（2）插入類排序法

插入類排序法主要有簡單插入排序法和希爾排序法。

簡單插入排序法，是指將無序序列中的各元素依次插入到已經有序的線性表中。在這種排序方法中，每一次比較後最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n–1)/2次比較。

希爾排序法對簡單插入排序做了較大的改進。它是將整個無序序列分割成若干小的子序列分別進行插入排序。希爾排序的效率與所選取的增量序列有關。在最壞情況下，希爾排序所需要的比較次數為O(n

1.5

)。

（3）選擇類排序

選擇類排序主要有簡單選擇類排序法和堆排序法。

簡單選擇排序法的基本思想是：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）；然後對剩下的子表採用同樣的方法，直到子表空為止。對於長度為n的線性表，在最壞情況下需要比較n(n–1)/2次。

堆排序法也屬於選擇類排序法。具有n個元素的序列（h

1

,

h

2

,

…,

h

n

），當且僅當滿足條件：

或

(i=1,

2,

…,

n/2）時稱之為堆。可見，堆頂元素（即第一個元素）必為最大項。

堆排序的方法對於規模較小的線性表並不適合，但對於較大規模的線性表來說是很有效的。在最壞情況下，堆排序需要比較的次數為O(nlog

2

n

)。