*************************************插入排序****************************************************************
/*算法導論p13
* sort from a[0] to a[n-1]
*/
void sort_insert(int *a, int n){
int key, i , j ;
for( i = 1 ; i < n ; i++ )
{
key = a[i] ;
for( j = i - 1 ; j >= 0 ; j -- )
{
if( key < a[j] )
{
a[j+1] = a[j] ;
}else break ;
}
a[j+1] = key ;
}
}
**********************************************歸並排序*************************************************************
#include "stddef.h"
/*p17
* 歸並排序
*/
void merge( int *a, int s, int m, int e ) ;
void sort_merge(int *a, int s, int e ){
if( s < e )
{
int m = ( s + e ) / 2 ;
sort_merge( a, s, m ) ;
sort_merge( a, m+1, e ) ;
merge( a, s, m, e );
}
}
void merge( int *a, int s, int m, int e ){
int num1 = m -s + 1 ;
int num2 = e - m ;
int i, flag1, flag2 ;
int *arr1 = (int *)calloc((size_t) num1+1, sizeof(int)) ;
int *arr2 = (int *)calloc( (size_t)num2+1, sizeof(int)) ;
for( i = 0 ; i < num1 ; i ++ )
{
arr1[i] = a[s+i] ;
}
arr1[num1] = 0x7fffffff ;
for( i = 0 ; i < num2 ; i ++ )
{
arr2[i] = a[m+1+i ] ;
}
arr2[num2] = 0x7fffffff ;
flag1 = flag2 = 0 ;
for( i = s ; i <= e ; i ++ )
{
if( arr1[flag1] <= arr2[flag2] )
{
a[i] = arr1[flag1++] ;
}else
a[i] = arr2[flag2++] ;
}
}
****************************************************堆排序**************************************************************
#include "stddef.h"
/*p73
* 排序函數為heap_sort(int *a, int n)
* a的數組的起始下標為1，結束下標為n，共有n個元素
*/
void max_heapify(int *a, int i, int size) {
int l = 2*i ;
int r = 2*i + 1 ;
int tmp, largest = i ;
if( l <= size && a[l] > a[largest] )
largest = l ;
if( r <= size && a[r] > a[largest] )
largest = r ;
if( largest != i )
{
tmp = a[i] ;
a[i] = a[largest] ;
a[largest] = tmp ;
max_heapify(a, largest, size) ;
}
}
void build_max_heap(int *a, int n){
int i ,j;
for( i = n/2 ; i >= 1 ; i-- )
{
max_heapify( a, i, n ) ;
}
}
/*
* a的數組的起始下標為1，結束下標為n，共有n個元素
*/
void heap_sort(int *a, int n){
int i ,size, tmp;
build_max_heap(a, n) ;
for( i = n ; i > 0 ; )
{
tmp = a[i] ;
a[i] = a[1] ;
a[1] = tmp ;
max_heapify(a , 1, --i) ;
}
}
**************************************************快速排序*********************************************************************
/*p85
* array :a, start : s開始位置下標, e : end 結束位置下標
*/
void quick_sort(int *a, int s, int e ){
int i ;
if( s < e )
{
i = partition(a, s, e ) ;
quick_sort(a, s, i-1 ) ;
quick_sort(a, i+1, e ) ;
}
}
int partition(int *a, int s, int e){
int i, j , tmp ;
j = s - 1 ;
for( i = s ; i < e ; i ++ )
{
if( a[i] < a[e] )
{
j ++ ;
swap(&a[i], &a[j]) ;
}
}
j ++ ;
swap(&a[j], &a[e]);
return j ;
}
void swap(int *x, int *y){
int tmp ;
tmp = *x ;
*x = *y ;
*y = tmp ;
}
***********************************************計數排序***********************************
/*p98
* 計數排序，本程序只適用於非負數。非比較排序算法，時間復雜度O(n)
* res返回排序結果
*/
void count_sort(int *a, int n, int *res ){
int i, j,largest = a[0] ;
int *count ;
for( i = 1 ; i < n ; i ++ )
{
if( a[i] > largest )
largest = a[i] ;
}
count = (int *)calloc( largest+1 , sizeof(int) ) ;
for( j = 0 ; j < (largest+1) ; j++ )
{
count[j ] = 0 ;
}
/*
* 計數對於count數組表示該下標出現的次數
*/
for( i = 0 ; i < n ; i ++ )
{
count[ a[i] ] ++ ;
}
/*
* count數組表示該下標的大小排序
*/
for( j = 1 ; j < (largest + 1) ; j++ )
{
count[j] = count[j] + count[j-1] ;
}
//for( i = 0 ; i < n ; i ++ )
for( i = (n-1) ; i >= 0 ; i -- )//這樣能穩定排序
{
res[ count[a[i]] - 1 ] = a[i] ;//因為數組下標從0開始，所以需要減去1，即排序第一的元素應該在下標0上
count[a[i]] -- ;
}
free(count) ;
}
###################################測試函數##############################################
#include "stdio.h"
int main(int argc, char *argv[])
{
int a[20] = {9, 10, 8, 11, 7, 12, 6, 13, 5, 14, 4, 15, 3, 16, 2, 18, 20, 1, 19, 17 } ;
int res[21] ;
int i , j;
//插入排序
for( i = 0 ; i < 20 ; i++ )
{
res[i] = a[i] ;
}
sort_insert( res, 20 ) ;
printf("After insert sort:\n") ;
for( j = 0 ; j < 20 ; j ++ )
{
printf("%d, ", res[j]) ;
}
printf("\n");
//合並排序
for( i = 0 ; i < 20 ; i++ )
{
res[i] = a[i] ;
}
sort_merge( res, 0, 19 ) ;//注意sort_merge傳入參數為要排序的下標0，19.第二個下標是參加排序的
printf("After merge sort: \n") ;
for( j = 0 ; j < 20 ; j ++ )
{
printf("%d, ", res[j]) ;
}
printf("\n");
//堆排序
for( i = 0 ; i < 20 ; i++ )
{
res[i+1] = a[i] ;
}
heap_sort( res, 20 ) ;
printf("After merge sort: \n") ;
for( j = 1 ; j < 21 ; j ++ )
{
printf("%d, ", res[j]) ;
}
printf("\n");
//快速排序
for( i = 0 ; i < 20 ; i++ )
{
res[i] = a[i] ;
}
quick_sort( res, 0, 19 ) ;
printf("After quick sort: \n") ;
for( j = 0 ; j < 20 ; j ++ )
{
printf("%d, ", res[j]) ;
}
printf("\n");
//計數排序
a[3] = a[4] = 10 ;
count_sort( a, 20, res ) ;
printf("After count sort: \n") ;
for( j = 0 ; j < 20 ; j ++ )
printf("%d, ", res[j]) ;
}
printf("\n");
return 0 ;
}
