一、排序的概念所谓排序，就是要让所有元素按递增或递减的顺序排列。二、排序的分类内部排序：只在主存中完成的排序(由于主存有限，所以内部排序的元素是有上限的)。外部排序：利用磁盘等外存进行排序。三、排序的稳定性在待排序的元素中，存在多个相同的元素，经过排序后，这些元素的相对位置不变，该排序法就为稳定排序，否则为不稳定排序。四、内部排序法-----------------------------------------------------------1.插入排序算法思想假设待排序的元素存放在数组A[N]中。初始时，A[0]自成1个有序区，无序区为A[1]~A[N-1]。从i=1起直至i=N-1为止，依次将A[i]插入当前的有序区A[0]~A[i-1]中。排序结束后为含N个元素的有序区。算法的平均时间复杂度为O(N^2)。程序实现 voidInsertionSort( ElementType A[], int N ){  int j, P;    ElementTyep 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;  }}--------------------------------------------------------2.希尔排序算法思想假设有N个待排序的元素，先取一个小于N的整数d1作为第一个增量，把所有距离为d1的倍数的元素放在同一个组中，在各组内进行插人排序；然后取第二个增量d2<d1，重复上述的分组和排序，直至所取的增量dx=1(增量d1~dx为递减关系)。算法的平均时间复杂度为O( n^(1+￡) ),0<￡<1。程序实现 voidShellsort( ElementType A[], int N ){  int i, j, Increment;  ElementType Tmp;  for( Increment = N / 2; Increment > 0; Increment /= 2 )    for( i = Icrement; i < N; i++ )    {      Tmp = A[ i ];      for( j = i; j >= Increment; j -= Increment )        if( Tmp < A[ j - Increment ] )          A[ j ] = A[ j -Increment ];        else          break;      A[ j ] = Tmp    }}注：程序实现中采用的是希尔增量，采用不同的增量会影响到希尔排序的时间复杂度。效率比较高的增量有Sedgewick增量。Sedgewick增量序列：9*4^i-9*2^i+1 或者 4^i-3*2^i+1--------------------------------------------------------3.堆排序算法思想将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(NlogN)。程序实现 #define LeftChild( i ) ( 2 * ( i ) + 1 )voidPrecDown( ElementType A[ ], int i, int N ){  int Child;  ElementType 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;}voidHeapsort( ElementType A[ ], int N ){  int i;    for( i = N / 2; i >= 0; i-- )    PrecDown( A, i, N )  for( i = N - 1; i > 0; i-- )  {    Swap( &A[ 0 ], &A[ i ] );    PercDown( A, 0, i )  }}--------------------------------------------------------------4.直接选择排序算法思想每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子元素集的最后，直到全部元素排序完毕。算法的平均时间复杂度为O(N^2)。程序实现 voidSelectSort( ElementType A[ ], int N ){  int i, j, k;  ElementType Tmp;  for( i = 0; i < N; i++ )  {    k = i;    for( j = i+1; j <= N; j++ )      if( A[j] < A[k] )        k = j;    if( k != i )    {      Tmp = R[i];      R[i] = R[k];      R[k] = Tmp;    }  }}----------------------------------------------------------------5.归并排序算法思想归并排序是将若干个已排序的表合并成一个有序的表。程序实现(递归历程) voidMSort( 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 );  }}voidMergesort( ElementType A[ ], int N ){  ElementType *TmpArray;  TmpArray = malloc( N * sizeof( ElementType ) );  if( TmpArray != NULL )  {    MSort( A, TmpArray, 0, N - 1 );    free( TmpArray );  }  else    FatalError( "No space for tmp array!!!" );}程序实现(Merge例程) /* Lpos = start of left half, Rpos = start of right half */voidMerge( ElementType A[], ElementType TmpArray[], int Lpos, int Rpos, int RightEnd ){  int i, LeftEnd, NumElements, TmpPos;    LeftEnd = Rpos - 1;  TmpPos = Lpos;  NumElements = RightEnd - Lpos + 1;  /* main loop */  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++ ];  /* Copy TmpArray back */  for( i = 0; i < NumElements; i++, RightEnd-- )    A[ RightEnd ] = TmpArray[ RightEnd ];}------------------------------------------------------------------6.冒泡排序算法思想两两比较待排序的元素，发现两个元素的次序相反时即进行交换。算法的平均时间复杂度为O(N^2)。程序实现 voidBubbleSort( ElementType A[], int N ){   int i, j;  ElementType Tmp;    for( i=0; i<N; i++)  {    for( j=N-1; j>i; j--)      if( A[j] < A[j-1] )      {        Tmp = A[j];        A[j] = A[j-1];        A[j] = Tmp;      }  }}------------------------------------------------------7.快速排序算法思想快速排序是是一种分治的递归算法。分治法的基本思想是：将元素集分解为若干个子集合。递归地解这些子集合，然后将这些子集合问题的解组合为原元素集。快速排序算法被认为是理论上高度优化的一种排序算法。平均时间复杂度为O(NlogN)。程序实现 /* Return median of Left, Center, and Right *//* Order these and hide the pivot */ElementTypeMedian3( ElementType 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 ] );  /* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */  Swap( &A[ Center ], &A[ Right - 1 ] );  /* Hide pivot */  return A[ Right - 1 ];  /* Return pivot */}#define Cutoff ( 3 )voidQsort( ElementType A[ ], int Left, int Right ){  int i, j;  ElementType 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 );}voidQuicksort( ElementType A[ ], int N ){  Qsort( A, 0 , N-1 );}-----------------------------------------------------------------8.其他排序还有一些，诸如快速选择排序,桶式排序,基数排序等等。---------------------------------------------------------------五、外部排序法基本的外部排序算法使用归并排序中的Merge例程。六、排序算法的上下界证明这个都是数学证明了，Job Hunting中应该不用写了^^。  Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1919227

评论