数据结构与算法- 经典排序算法实现
一、排序算法
冒泡、选择、插入、希尔、快速、归并、堆和计数排序（省略了基数排序和桶排序）
以及C语言自带的排序函数
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
void Swap(ElementType *a, ElementType *b)
{
ElementType t = *a;
*a = *b;
*b = t;
}
void Bubble_sort(ElementType A[], int N)
{
int i, j, flag;
for ( i = N; i > 0; i-- ) {
flag = 0;
for ( j = 1; j < i; j++ ) {
// 冒泡排序将更大的值和更小值进行交换
if ( A[j-1] > A[j] ) {
Swap( &A[j-1], &A[j] );
flag = 1; // exchange occur
}
}
if ( flag == 0 ) break; // 若全程无交换，表明已排好序
}
}
void Select_sort(ElementType A[], int N)
{
int i, j, index; // 每一趟扫描选择最大（最小）值与初始位置进行交换
ElementType Max;
for ( i = N; i > 1; i-- ) {
Max = A[0]; // i : from N to 2
index = 0; // 初始化索引，第一位也可能为最大元素
for ( j = 1; j < i; j++ ) {
if ( A[j] > Max ) {
Max = A[j]; // 在当前循环内找到一个最大的元素
index = j;
}
}
Swap(&A[i-1], &A[index]);
}
}
void Insert_sort(ElementType A[], int N)
{
int i, j;
ElementType tmp;
for ( i = 1; i < N; i++ ) {
tmp = A[i];
// 每一趟反向遍历，将大于tmp的元素向后移动（等价于将tmp前插到合适的位置）
for ( j = i; j > 0 && A[j-1] > tmp; j-- ) {
A[j] = A[j-1];
}
A[j] = tmp;
}
}
void Shell_sort(ElementType A[], int N)
{
int i, j;
int increment;
ElementType Tmp; // increment sort
for ( increment=N/2; increment>0; increment/=2 ) {
// insertion sort
for ( i=increment; i<N; i++ ) {
Tmp = A[i];
for ( j=i; (j>=increment)&&(A[j-increment]>Tmp); j-=increment ) {
A[j] = A[j-increment];
}
A[j] = Tmp;
}
}
}
// Qucik Sort
#define Cutoff 20
ElementType Median3(ElementType A[], int Left, int Right)
{ // return median of Left, Center, 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] );
// A[Left] <= A[Cetner] <= A[Right]
Swap( &A[Center], &A[Right-1] );
// 将pivot隐藏在右边作为哨兵，并返回它
return A[Right-1];
}
void Q_sort(ElementType A[], int Left, int Right)
{
int i, j; // pointer
ElementType pivot;
if ( Left + Cutoff <= Right ) {
// large range Cutoff <= Right - Left = N - 1
pivot = Median3( A, Left, Right );
i = Left;
j = Right - 1;
for ( ; ; ) {
while( A[++i] < pivot ); // find a num large than pivot from left
while( A[--j] > pivot ); // find a num less than pivot from right
if ( i < j ) {
Swap( &A[i], &A[j] ); // pointer in range
}
else
break;
}
Swap( &A[i], &A[Right - 1] ); // restroe pivot
Q_sort( A, Left, i - 1 ); // from pivot to divid sort
Q_sort( A, i + 1, Right );
} else
Insert_sort( A, Right - Left + 1 );
}
void Quick_sort(ElementType A[], int N)
{
Q_sort( A, 0, N-1 ); // 递归式地划分，将小于pivot的划到左边，大于pivot划到右边
}
// Merge sort需要额外的内存空间
void Merge(ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int Rightend)
{
int i, Leftend, NumElements, Tmp;
Leftend = Rpos - 1;
Tmp = Lpos;
NumElements = Rightend - Lpos + 1;
// main loop
while ( Lpos <=Leftend && Rpos <= Rightend ) {
if ( A[Lpos] <= A[Rpos] )
TmpArray[Tmp++] = A[Lpos++];
else
TmpArray[Tmp++] = A[Rpos++];
}
while ( Lpos <=Leftend )
TmpArray[Tmp++] = A[Lpos++];
while ( Rpos <= Rightend )
TmpArray[Tmp++] = A[Rpos++];
for ( i = 0; i < NumElements; i++, Rightend-- ) {
A[Rightend] = TmpArray[Rightend]; // copy array back
}
}
void MSort(ElementType A[], ElementType 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_sort(ElementType A[], int N)
{
ElementType *TmpArray;
TmpArray = malloc( N * sizeof( ElementType ) );
if ( TmpArray != NULL ) {
MSort( A, TmpArray, 0, N-1 );
free(TmpArray);
} else {
printf("No space for tmp array!");
}
}
/* 堆排序 这里只插入了N个元素 */
void PercDown(ElementType A[], int p, int N)
{
int Parent, Child; // 将N个元素的数组中以A[p]为根的子堆调整为最大堆
ElementType X;
X = A[p]; // 取出根结点存放的值
for ( Parent=p; (Parent*2+1)<N; Parent=Child ) {
Child = Parent * 2 + 1;
if ( (Child!=N-1) && (A[Child]<A[Child+1]) )
Child++; // Child指向左右子结点的较大者
if ( X >= A[Child] )
break; // 找到了合适位置
else
A[Parent] = A[Child]; //下滤X
}
A[Parent] = X;
}
void Heap_sort(ElementType A[], int N)
{
int i;
for ( i = N/2 - 1; i >= 0; i-- ) // 建立最大堆
PercDown( A, i, N );
for ( i = N - 1; i > 0; i-- ) {
Swap(&A[0], &A[i]); // 删除最大堆顶
PercDown( A, 0, i);
}
}
void Count_sort(ElementType A[], int N)
{
int i, j, count;
int size = 101; //假设count size为100，对较小的数（如分数）进行排序
ElementType B[size];
for ( i = 0; i < size; i++ ) {
B[i] = 0;
}
for ( i = 0; i < N; i++ ) {
B[ A[i] ]++; // count the number
}
count = 0; // output, from 0 to N -1 in A[]
for ( i = 0; i < size; i++ ) {
// bucket not empty
if ( B[i] != 0 ) {
// B[i] is equal to frequency of i
for ( j = 0; j < B[i]; j++, count++) {
A[count] = i;
}
}
}
}
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main()
{
ElementType *A;
int i, N, flag;
N = 1;
printf("
array length? if length < 0 then quit
");
while ( N >= 1 ) {
scanf("%d", &N);
A = (ElementType*)malloc( N * sizeof(ElementType));
printf("
Array: ");
for ( i = 0; i < N; i++ ) {
A[i] = ( rand() % 100 );
printf("%d ", A[i]);
}
printf("
Choose sort:");
printf("0:default 1:bubble 2:select 3:insert 4:shell
");
printf(" 5:quick 6:merge 7:heap 8:count
");
scanf("%d", &flag);
switch( flag ) {
case 0: qsort(A, N, sizeof(ElementType), cmpfunc); break;
case 1: Bubble_sort(A, N); break;
case 2: Select_sort(A, N); break;
case 3: Insert_sort(A, N); break;
case 4: Shell_sort(A, N); break;
case 5: Quick_sort(A, N); break;
case 6: Merge_sort(A, N); break;
case 7: Heap_sort(A, N); break;
case 8: Count_sort(A, N); break;
default: break;
}
printf("
Array after sort: ");
for ( i = 0; i < N; i++ )
printf("%d ", A[i]);
printf("
");
}
return 0;
}