冒泡 選擇 插入 歸并 堆排 快排 希爾

/* Sort Rate Study */ /* Author: ZZ_Inori_Evanescence/Elapsed_Hiyori */ /* Home: http://blog.csdn.net/Elapsed_Hiyori */ /* Date: 2012/12/16 10:57 */ /* ***********************************************/#include <stdio.h> #include <stdlib.h> #include <time.h> #include <malloc.h>#define FALSE 0 #define TRUE 1 #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 ! */

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法分析之---部分排序算法的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。