数据结构与算法分析之---部分排序算法的实现

冒泡 选择 插入 归并 堆排 快排 希尔

/* Sort Rate Study*//* Author: ZZ_Inori_Evanescence/Elapsed_Hiyori *//* Home: /Elapsed_Hiyori *//* Date: /12/16 10:57 *//* ***********************************************/#include <stdio.h>#include <stdlib.h>#include <time.h>#include <malloc.h>#define FALSE0#define TRUE1#define ElementType int#define MAXNUM 100000/* ========================================= *//* Random Numbers;/* ========================================= */ElementType *GetRandomNumbers( void ){int i;ElementType *TempArray;TempArray = ( ElementType * )malloc( MAXNUM * sizeof( ElementType ) );for( i = 0; i < MAXNUM; i++ )TempArray[i] = rand() % 999999;return TempArray;}/* ========================================= *//* Swap;/* ========================================= */void Swap( int *a, int *b ){int TempCell;TempCell = *a;*a = *b;*b = TempCell;}/* ========================================= *//* Bubble Sort;/* ========================================= */void BubbleSort( ElementType *Array, int n ){int i, LastExchangeIndex,j;i = n-1;while( i > 0 ){LastExchangeIndex = 0;for( j = 0; j < i; j++ )if( Array[j+1] < Array[j] ){Swap( &Array[j+1], &Array[j] );LastExchangeIndex = j;}i = LastExchangeIndex;}}/* ========================================= *//* Select Sort;/* ========================================= */void SelectSort( ElementType *Array, int n ){int i,j,min;for( i = 0; i < n-1; i++ ){int Index = 0;min = Array[i];for( j = i+1; j < n; j++ ){if( Array[j] < min ){min = Array[j];Index = j;}}if( Index ){Swap( &Array[Index], &Array[i] );}}}/* ========================================= *//* Insertion Sort;/* ========================================= */void InsertionSort( ElementType *Array, int n ){int j,P;ElementType TempCell;for( P = 1; P < n; P++ ){TempCell = Array[P];for( j = P; j > 0 && Array[j-1] > TempCell; j-- )Array[j] = Array[j-1];Array[j] = TempCell;}}/* ========================================= *//* Shell Sort;/* Increment Sequence: Shell Sequence;/* ========================================= */void ShellSort( ElementType *Array, int n ){int i,j,Increment;ElementType TempCell;for( Increment = n/2; Increment > 0; Increment /= 2 )for( i = Increment; i < n; i++ ){TempCell = Array[i];for( j = i; j >= Increment; j -= Increment )if( TempCell < Array[j-Increment] )Array[j] = Array[j-Increment];elsebreak;Array[j] = TempCell;}}/* ========================================= *//* Heap Sort;/* ========================================= */#define LeftChild( i ) ( 2 * ( i ) + 1 )void PercDown( ElementType *Array, int i, int n ){int Child;ElementType TempCell;for( TempCell = Array[i]; LeftChild( i ) < n; i = Child ){Child = LeftChild( i );if( Child != n-1 && Array[Child+1] > Array[Child] )Child++;if( TempCell < Array[Child] )Array[i] = Array[Child];elsebreak;}Array[i] = TempCell;}void HeapSort( ElementType *Array, int n ){int i;for( i = n/2; i >= 0; i-- ) /* BuildHeap */PercDown( Array, i, n );for( i = n-1; i > 0; i-- ){Swap( &Array[0], &Array[i] );PercDown( Array, 0, i );}}/* ========================================= *//* Merge Sort;/* ========================================= */void Merge( ElementType *Array, ElementType *TempArray,int Lpos, int Rpos, int RightEnd ){int i, LeftEnd, NumElements, TempPos;LeftEnd = Rpos - 1;TempPos = Lpos;NumElements = RightEnd - Lpos + 1;while( Lpos <= LeftEnd && Rpos <= RightEnd )if( Array[Lpos] <= Array[Rpos] )TempArray[TempPos++] = Array[Lpos++];elseTempArray[TempPos++] = Array[Rpos++];while( Lpos <= LeftEnd )TempArray[TempPos++] = Array[Lpos++];while( Rpos <= RightEnd )TempArray[TempPos++] = Array[Rpos++];for( i = 0; i < NumElements; i++, RightEnd-- )Array[RightEnd] = TempArray[RightEnd];}void Msort( ElementType *Array, ElementType *TempArray, int Left, int Right ){int Center;if( Left < Right ){Center = ( Left + Right ) / 2;Msort( Array, TempArray, Left, Center );Msort( Array, TempArray, Center+1, Right );Merge( Array, TempArray, Left, Center+1, Right );}}void MergeSort( ElementType *Array, int n ){ElementType *TempArray;TempArray = ( ElementType * )malloc( n * sizeof( ElementType ) );if( TempArray != NULL ){Msort( Array, TempArray, 0, n-1 );free( TempArray );}elseprintf("No Space For Temp Array!!!\n");}/* ========================================= *//* Quick Sort;/* Partition: Median-of-Three Partitioning/* ========================================= */ElementType Median_Three( ElementType *Array, int Left, int Right ){int Center = ( Left + Right ) / 2;if( Array[Left] > Array[Center] )Swap( &Array[Left], &Array[Center] );if( Array[Left] > Array[Right] )Swap( &Array[Left], &Array[Right] );if( Array[Center] > Array[Right] )Swap( &Array[Center], &Array[Right] );Swap( &Array[Center], &Array[Right-1] );return Array[Right-1];}#define Cutoff ( 3 )void Qsort( ElementType *Array, int Left, int Right ){int i,j;ElementType Pivot;if( Left + Cutoff <= Right ){Pivot = Median_Three( Array, Left, Right );i = Left; j = Right - 1;for( ; ; ){while( Array[++i] < Pivot );while( Array[--j] > Pivot );if( i < j )Swap( &Array[i], &Array[j] );elsebreak;}Swap( &Array[i], &Array[Right-1] );Qsort( Array, Left, i-1 );Qsort( Array, i + 1, Right );}elseInsertionSort( Array+Left, Right-Left+1 );}void QuickSort( ElementType *Array, int n ){Qsort( Array, 0, n-1 );}/* ================================================ *//* END ! */