c語言種必須掌握的四種排序方法

    c語言中排序的方法有很多，就面試的可能性和使用的廣度來說下面4種排序方法必須掌握，給出源代碼：

1.冒泡排序:(前兩個直接在main()函數種實作)

/***********************************************

* 函數名稱: 冒泡排序

* 作 者: 程鳳明

* 時 間: 2009-7-20

************************************************/

#include <stdio.h>

#define N 10

main()

{

int i, j, temp;

int a[N];

printf("please input %d numbers:/n",N);

for(i = 0; i < N; i++)

{

scanf("%d",&a[i]);

}

for (i = 0; i < N-1; i++) //表示要比較N-1趟

{

for (j =0; j < N-i-1; j++) //表示每趟比較的次數

{

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

{

temp = a[j];

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

a[j+1] = temp;

}

}

}

for(i = 0; i < N; i++)

{

printf("%-5d",a[i]);

}

printf("/n");

}

2.選擇排序：

/***********************************************

* 函數名稱: 選擇排序

* 作 者: 程鳳明

* 時 間: 2009-7-20

************************************************/

#include <stdio.h>

#define N 10

int main()

{

int i, j, k,temp;

int a[N];

printf("please input %d numbers:/n",N);

for(i = 0; i < N; i++)

{

scanf("%d",&a[i]);

}

for (i = 0; i < N-1; i++)

{

k = i; //标記起始位置,不能少

for (j = i+1; j < N; j++)

{

if (a[i] > a[j])

{

k = j; //标記将要交換的位置

if (k != i)

{

temp = a[i];

a[i] = a[k];

a[k] = temp;

}

}

}

}

for(i = 0; i < N; i++)

{

printf("%-5d",a[i]);

}

printf("/n");

return 0;

}

3.快速排序：

/************************************************

*程式名稱：快速排序

*作 者: 程鳳明

*日 期：2009-7-20

************************************************/

#include <stdio.h>

//快速排序法的遞歸處理

void QuickSort( int list[15] , int left , int right , int index )

{

int i , j , k ;

int pivot ; //分割指針

int temp ; //資料交換時暫存變量

i = left ; //設定i為數組的左指針

j = right + 1 ; //設定j為數組的右指針

pivot = list[left] ; //取最左邊的元素

if( i < j )

{

do

{

do //從左往右找比pivot大的值

{

i++ ;

}while( list[i] <= pivot && i <= right ) ;

do //從右往左找比pivot小的值

{

j-- ;

}while( list[j] >= pivot && j > left ) ;

if( i < j )//交換list[i]和list[j]的值

{

temp = list[i] ;

list[i] = list[j] ;

list[j] = temp ;

printf("/n *Current sorting result:") ;

for( k = 0 ; k < index ; k++ )

{

printf("%d " , list[k] ) ;

}

}

}while( i < j ) ;

//交換list[left]和list[j]的值

temp = list[left] ;

list[left] = list[j] ;

list[j] = temp ;

//列印目前的排序結果

printf("/n #Current sorting result:") ;

for( k = 0 ; k < index ; k++)

{

printf("%d ",list[k] ) ;

}

QuickSort( list , left , j - 1 , index ) ; //排序左半邊

QuickSort( list , j+1 , right , index ) ; //排序右半邊

}

}

void main()

{

int list[20] ; //設定數組最大長度為20

int node ; //讀入輸入的值所使用的暫存變量

int i , index ;

printf("/n Please input the values you want to sort (Exit for 0) : /n") ;

index = 0 ;

scanf("%d" , &node) ; //讀取資料存到數組中

while( ( node != 0 ) && ( index < 20 ) ) //資料尚未結束

{

list[index] = node ;

index = index + 1 ;

scanf( "%d" , &node ) ;

}

QuickSort( list , 0 , index - 1 , index ) ; //進行快速排序

printf("/n Final sorting result :") ; //列印最終的排序結果

for( i = 0 ; i < index ; i++)

{

printf("%d " , list[i] ) ;

}

}

4堆排序：

 /***********************************************

* 函數名稱: 堆排序

* 作 者: 程鳳明

* 時 間: 2009-7-20

************************************************/

#include <stdio.h>

void createHeap(int *, int, int);

void HeapSort(int *, int);

int main()

{

int i , index ;

int list[20] ;

int node ;

printf("/nplease input the value you wait to sort(Exit for 0) : /n" ) ;

list[0] = 0 ;

index = 1 ;

scanf("%d" , &node) ;

while(node != 0)

{

list[index] = node ;

index++ ;

scanf("%d" , &node) ;

}

index-- ;

HeapSort(list , index) ;

printf("/nSorting result: ") ;

for(i = 1 ; i <= index ; i++)

printf("%d " , list[i]);

printf("/n") ;

return 0;

}

void createHeap(int *heap , int root , int index)

{

int j ;

int temp ;

int finish ;

j = 2 * root ;

temp = heap[root] ;

finish = 0 ;

while(j <= index && finish == 0)

{

if( j < index )

{

if(heap[j] < heap[j+1])

j++ ;

}

if(temp >= heap[j])

finish = 1 ;

else

{

heap[j/2] = heap[j] ;

j = 2 * j ;

}

}

heap[j/2] = temp ;

}

void HeapSort(int *heap , int index )

{

int i, temp ;

for( i = index / 2 ; i >= 1 ; i--)

createHeap( heap , i , index) ;

for( i = index - 1 ; i >= 1 ; i--)

{

temp = heap[i+1] ;

heap[i+1] = heap[1] ;

heap[1] = temp ;

createHeap(heap , 1 , i ) ;

}

}