数据结构——常见排序算法

一，选择排序

1,简单选择排序

  #include<iostream>
  using namespace std;
  void Swap(int *a,int *b)
  {
       int t;
       t = *a;
       *a = *b;
       *b = t;
  }
void Select_Sort(int *arr,int n)
{
      int  Min =0;
      for(int i = 0;i < n ;i++)
      {
          Min = i;
          for( int j = i+1;j < n;j++)    //选择未排序列中最小的放到前面
             if(arr[j] <arr[Min]) Min = j;
          Swap(&arr[i],&arr[j]);
     }
}

2, 堆排序

void Swap(int *a,int *b)
  {
       int t;
       t = *a;
       *a = *b;
       *b = t;
  }
void PercDown(int A[],int p,int N)
{
    int Parent,Child;
    int X;
    X = A[p];
    for(Parent = p;(Parent * 2+1) < n;Parent = Child
    {
        Child = Parent * 2 +1;
        if(Child != N-1)&&A[Chlild] < A[Child + 1];
        Child ++;
        if(X>=A[Child]) break;  //找到了合适的位置
        else
            A[Parent] = A[Child];
   }
   A[Parent] = X;
}
void Heap_Sort(int *A,int n)
{
    int i;
    for(i = n/2; i >=0; i--)
        PercDown(A,i,n);
    for(i = n-1;&A[i];i--)
    {
        Swap(&A[0],&A[i]);
        PercDown(A,0,i);
    }
}