c语言 数组 算法,C语言--数组实现--各种排序算法

C语言--数组实现--各种排序算法

C语言--数组实现--排序算法：插入排序；希尔排序；冒泡排序；快速排序1；快速排序2；堆排序；归并排序；基数排序；选择排序；计数排序；

各种算法的相关分析如下：

排序法

最差时间分析

平均时间复杂度

稳定度

空间复杂度

冒泡排序

O(n2)

O(n2)

稳定

O(1)

快速排序

O(n2)

O(n*log2n)

不稳定

O(log2n)~O(n)

选择排序

O(n2)

O(n2)

稳定

O(1)

二叉树排序

O(n2)

O(n*log2n)

不一顶

O(n)

插入排序

O(n2)

O(n2)

稳定

O(1)

堆排序

O(n*log2n)

O(n*log2n)

不稳定

O(1)

希尔排序

O

O

不稳定

O(1)

各种排序算法，分享给初学者，欢迎指正批评！

// 用数组实现各种排序算法

#include

#include

#define LeftChild( i ) ( 2 * ( i ) +1

)//堆排序--由于数组和堆的序号的差别，数组表示时左孩子应这样表示

#define Cutoff ( 3

)//快速排序--截至范围

void InsertionSort( int *, int

);//插入排序// 第二个参数为数组的长度

void ShellSort( int *, int

);//希尔排序

void PercDown( int *, int i, int N

);//最大二叉堆建立

void HeapSort( int *, int N

);//堆排序

void Swap( int *, int *

);//元素互换

void MergeSort( int *, int

);//归并排序驱动程序

void MSort( int *, int *, int , int

);//归并排序递归例程

void Merge( int *, int *, int, int, int

);//归并排序合并例程

void QuickSort( int *, int

);//快速排序驱动程序--数据结构与算法书上

int Median3( int *, int, int

);//实现三数中值分割法的程序

void QSort( int *, int, int

);//快速排序主例程

void QuickSort2( int *, int, int

);//快速排序--郝斌视频

int FindPos(int *, int, int

);//找位置

void BubSort( int *, int

);//冒泡排序

void SelectionSort( int *, int

);//选择排序

void CountSort( int *, int

);//计数排序

int GetNumInPos( int, int );

void RadixSort( int *, int

);//基数排序

int main ( void )

{

int i;

int A[ 20 ] = {

23,56,15,48,12,26,45,23,45,17,3,6,5,48,59,65,47,15,35,64

};

//InsertionSort( A, 20 );//插入排序

//ShellSort( A, 20 );//希尔排序

//HeapSort( A, 20 );//堆排序

//MergeSort( A, 20 );//归并排序

//QuickSort( A, 20 );//快速排序

//QuickSort2( A, 0, 19 );//快速排序2

//BubSort( A, 20 );//冒泡排序

//SelectionSort( A, 20 );//选择排序

//CountSort( A, 20 );//计数排序

RadixSort( A, 20 );//基数排序

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

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

printf ( "n" );

return 0;

}

void InsertionSort( int A[ ], int N

)//插入排序

{

int j, P;

int Tmp;

for ( P = 1; P < N; P++ )

{

Tmp = A[ P ];

for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j--

)

A[ j ] = A[ j - 1 ];

A[ j ] = Tmp;

}

void ShellSort( int A[ ], int N

)//希尔排序

{

int i, j, Increament;

int Tmp;

for ( Increament = N / 2; Increament > 0; Increament /= 2

)

{

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

{

Tmp = A[ i

];

for ( j =

i; j >= Increament; j -= Increament )

if ( Tmp

< A[ j - Increament ] )

A[ j ] = A[

j - Increament ];

else

break;

A[ j ] = Tmp;

}

}}

void PercDown( int A[ ], int i, int N

)//最大二叉堆建立

{int

Child;

int Tmp;

for ( Tmp = A[ i ]; LeftChild( i ) < N; i = Child )

{

Child = LeftChild( i );

if ( Child != N - 1 && A[ Child + 1 ] > A[ Child ]

)

Child++;

if ( Tmp < A[ Child ] )

A[ i ] = A[ Child ];

else

break;

}

A[ i ] = Tmp;

}

void HeapSort( int A[ ], int N

)//堆排序

{

int i;

for ( i = N / 2; i >= 0; i-- )//BuildHeap

PercDown( A, i, N );

for ( i = N - 1; i > 0; i-- )

{

Swap( &A[ 0 ], &A[ i ] );//DeleteMax

PercDown( A, 0, i );

}

}

void Swap( int *a, int *b )

{

int t;

t = *a;

*a = *b;

*b = t;

}

void MergeSort( int A[ ], int N

)//归并排序驱动程序

{

int * TmpArray;

TmpArray = ( int * )malloc( N * sizeof( int ) );

if ( NULL != TmpArray )

{

MSort( A, TmpArray, 0, N - 1 );

free( TmpArray );

}

else

printf( "No space for tmp array!!!n" );

}

void MSort( int A[ ], int TmpArray[ ], int Left,

int Right )//归并排序递归例程

{

int Center;

if ( Left < Right )

{

Center = ( Left + Right ) / 2;

MSort( A, TmpArray, Left, Center );

MSort( A, TmpArray, Center + 1, Right );

Merge( A, TmpArray, Left, Center + 1, Right );

}

}

void Merge( int A[ ], int TmpArray[ ], int Lpos,

int Rpos, int RightEnd )//归并排序合并例程

{

int i, LeftEnd, NumElements, TmpPos;

LeftEnd = Rpos - 1;

TmpPos = Lpos;

NumElements = RightEnd - Lpos + 1;

while( Lpos <= LeftEnd && Rpos <= RightEnd

)

{

if( A[ Lpos ] <= A[ Rpos ] )

TmpArray[ TmpPos++ ] = A[ Lpos++ ];

else

TmpArray[ TmpPos++ ] = A[ Rpos++ ];

}

while( Lpos <= LeftEnd )//copy rest of first

half

TmpArray[ TmpPos++ ] = A[ Lpos++ ];

while( Rpos <= RightEnd )//copy rest of second

half

TmpArray[ TmpPos++ ] = A[ Rpos++ ];

for( i = 0; i < NumElements; i++, RightEnd-- )

A[ RightEnd ] = TmpArray[ RightEnd ];

}

void QuickSort( int A[ ], int N

)//快速排序驱动程序

{

QSort( A, 0, N - 1 );

}

int Median3( int A[ ], int Left, int Right

)//实现三数中值分割法的程序

{

int Center = ( Left + Right ) / 2;

if( A[ Left ] > A [ Center ] )

Swap( &A[ Left ], &A[ Center ] );

if( A[ Left ] > A[ Right ] )

Swap( &A[ Left ], &A[ Right ] );

if( A[ Center ] > A[ Right ] )

Swap( &A[ Center ], &A[ Right ] );

Swap( &A[ Center ], &A[ Right - 1 ] );//Hide

pivot

return A[ Right - 1 ];// Return pivot

}

void QSort( int A[ ], int Left, int Right

)//快速排序主例程

{

int i, j;

int Pivot;

if( Left + Cutoff <= Right )

{

Pivot = Median3( A, Left, Right );

i = Left;

j = Right - 1;

for( ; ; )

{

while( A[ ++i ] < Pivot ){ }

while( A[ --j ] > Pivot ){ }

if( i < j )

Swap( &A[ i ], &A[ j ] );

else

break;

}

Swap( &A[ i ], &A[ Right - 1 ] );//Restore

pivot

QSort( A, Left, i - 1 );

QSort( A, i + 1, Right );

}

else //Do an insertion sort on the subarray

InsertionSort( A + Left, Right - Left + 1 );

}

void QuickSort2( int A[ ], int low, int hight

)//快速排序2

{

int pos;

if( low < hight )

{

pos = FindPos( A, low, hight );

QuickSort2( A, low, pos - 1 );

QuickSort2( A, pos + 1, hight );

}

}

int FindPos(int A[ ], int low, int hight

)

{

int val = A[ low ];

while( low < hight )

{

while( low < hight && A[ hight ] >= val )

--hight;

A[ low ] = A[ hight ];

while( low < hight && A[ low ] <= val )

++low;

A[ hight ] = A[ low ];

}//终止while循环之后low和high一定是相等的

A[ low ] = val;

return hight;//或者low， low =

hight

}

void BubSort( int A[ ], int N

)//冒泡排序

{

int i, j, t;

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

{

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

{

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

{

t = A[ j ];

A[ j ] = A[ j + 1 ];

A[ j + 1 ] = t;

}

}

}

}

void SelectionSort( int A[ ], int N

)//选择排序

{

int i = 0;

int min = 0;

int j = 0;

int tmp = 0;

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

{

min = i;//每次将min置成无序组起始位置元素下标

for( j = i; j < N; j++ )//遍历无序组，找到最小元素

{

if( A[ min ] > A[ j ] )

min = j;

}

if( min != i )//若最小元素不是无序组起始位置元素，则与起始元素交换位置

{

tmp = A[ min ];

A[ min ] = A[ i ];

A[ i ] = tmp;

}

}

}

void CountSort( int A[ ], int N

)//计数排序

{

int i;

int *SortedArr = ( int * )malloc( sizeof( int ) * N );

int *CountArr = ( int * )malloc( sizeof( int ) * 100

);//0-99共100个数

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

CountArr[ i ] = 0;//初始化计数数组

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

CountArr[ A[ i ] ]++;//统计i的次数

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

CountArr[ i ] += CountArr[ i - 1 ];//对所有的计数累加

for( i = N; i > 0; i-- )//根据计数将A中的元素排序并放入SortArr中

{

SortedArr[ CountArr[ A[ i -1 ] ] -1 ] = A[ i - 1 ];

CountArr[ A[ i - 1 ] ]--;

}

for( i = 0; i < N; i++ )//将SortArr中的元素复制到A中

A[ i ] = SortedArr[ i ];

free( SortedArr );

free( CountArr );

}

int GetNumInPos( int num, int pos

)//找到num的从低到高的第pos位的数据

{

int temp = 1;

for( int i = 0; i < pos - 1; i++ )

temp *= 10;

return ( num / temp ) % 10;

}

void RadixSort( int pDataArray[], int iDataNum

)//基数排序

{

int *radixArrays[ 10 ];//分别为0-9的序列空间

for( int i =0; i < 10; i++ )

{

radixArrays[

i ] = ( int * )malloc( sizeof( int ) * ( iDataNum + 1 )

);

radixArrays[

i ][ 0 ] = 0;//index为0处记录这组数据的个数

//之前没有初始化为0，导致下面A处index的值非法，进而导致B赋值编译错误

}

for( int pos = 1; pos <= 31; pos++

)//从个位开始到第31位

{

for( int i = 0; i < iDataNum; i++

)//分配过程

{

int num =

GetNumInPos( pDataArray[ i ], pos );

int

index = ++radixArrays[ num ][ 0 ];//A

radixArrays[

num ][ index ] = pDataArray[ i ];//B

}

for( int i = 0, j = 0; i < 10; i++

)//收集

{

for( int k

= 1; k <= radixArrays[ i ][ 0 ]; k++ )

pDataArray[

j++ ] = radixArrays[ i ][ k ];

radixArrays[ i ][ 0 ] =

0;//复位

}

}

//free(

radixArrays );/加上这句会报错，报错信息为：data structure.exe

已触发了一个断点。

//原因：

内存越界，比如“数组越界”、“释放已经释放掉的内存”、

//“共享内存引发的问题”、“释放野指针的问题”等。

//此处的原因可能为：释放已经释放掉的内存。

//更新纠正：真正原因为free的参数错误；free(radixArrays)但，radixArrays是一个数组，不是指针。

for ( int i = 0; i < 10; i++)

{

free( radixArrays[ i ] );

radixArrays[ i ] = NULL;

}

}