排序

排序+查找
void X_Sort(ElelmentType A[], int N)

简单排序
1：冒泡排序（每次最大的到最后)
 void Bubble_Sort(ElementType A[],int N)
 {
  for(P = N-1; P >= 0;P--)
  {
   flag = 0;
   for(i = 0; i < P; i++)
   {
    if(A[i] > A[i+1])
    {
     Swap(A[i],A[i+1]);
     flag = 1;
    }
   }
   
   if(flag == 0) break;
  }
 }
 
 O(N)~O(N*N)
 
2:插入排序(扑克牌)
 void Insertion_Sort(ElelmentType A[], int N)
 {
  for(P = 1; P < N; P++)
  {
   Tmp = A[P];
   for(i = P; i > 0 && A[i-1] > Tmp;i--)
    A[i] = A[i-1];
   A[i] = Tmp;
  }
 }
 
 O(N)~O(N*N)
 
3：希尔排序
 间隔排序
 定义增量序列D=[N / 2]
 
 void Shell_Sort(ElementType A[], int N)
 {
  for(D = N/2; D > 0; D/=2) //增量序列
  {
   for(P=D; P<N;P++) //插入排序
   {
    Tmp = A[P];
    for(i=P; i>=D&&A[i-D]>Tmp;i-=D)
     A[i] = A[i-D];
    A[i] = Tmp;
   }
  }
 }

 
4:堆排序

 选择排序
 void Selection_Sort(ElementType A[],int N)
 {
  for(i=0; i<N;i++)
  {
   MinPostion = ScanForMin(A,i,N-1);
   Swap(A[i],A[minPositon]);
  }
 }

5:归并排序
 核心：有序子序列的归并
 void Merge(ElementType A[], ElementType TmpA[],int L, int R, int RightEnd)
 {
  LeftEnd = R-1;
  Tmp = L;
  NumElemets = RightEnd -L + 1;
  while(L <= LeftEnd && R <= RightEnd)
  {
   if(A[L] <= A[R])
    TmpA[Tmp++] = A[L++];
   else
    TmpA[Tmp++] = A[R++];
  }
  while(L <= LeftEnd)
   TmpA[Tmp++] = A[L++];
  while(R <= RightEnd)
   TmpA[Tmp++] = A[R++];
   
  for(i=0;i<NumElemets;i++,RightEnd--)
   A[RightEnd] = TmpA[RightEnd];
 }

 递归算法：
  分而治之