C#排序算法的比较

void InsertSort(SqList &L) ...{

  // 对顺序表L作直接插入排序。

  int i,j;

  for (i=2; i<=L.length; ++i)

    if (LT(L.r[i].key, L.r[i-1].key)) ...{

      // "<"时，需将L.r[i]插入有序子表

      L.r[0] = L.r[i];                 // 复制为哨兵

      for (j=i-1;  LT(L.r[0].key, L.r[j].key);  --j)

        L.r[j+1] = L.r[j];             // 记录后移

      L.r[j+1] = L.r[0];               // 插入到正确位置

    }

} // InsertSort   
		

void ShellInsert(SqList &L, int dk) ...{

  // 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：

  //     1. 前后记录位置的增量是dk，而不是1；

  //     2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。

  int i,j;

  for (i=dk+1; i<=L.length; ++i)

    if (LT(L.r[i].key, L.r[i-dk].key)) ...{ // 需将L.r[i]插入有序增量子表

      L.r[0] = L.r[i];                   // 暂存在L.r[0]

      for (j=i-dk; j>0 && LT(L.r[0].key, L.r[j].key); j-=dk)

        L.r[j+dk] = L.r[j];              // 记录后移，查找插入位置

      L.r[j+dk] = L.r[0];                // 插入

    }

} // ShellInsert  

  

void ShellSort(SqList &L, int dlta[], int t) ...{

   // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。

   for (int k=0;k<t;k++)

      ShellInsert(L, dlta[k]);  // 一趟增量为dlta[k]的插入排序

} // ShellSort  
		

void BubbleSort(SeqList R) ...{

　　int i，j;

　　Boolean exchange; //交换标志

　　for(i=1;i<n;i++)...{ exchange="FALSE;" j="n-1;j">=i;j--) //对当前无序区R[i..n]自下向上扫描

　　          if(R[j+1].key< R[j].key)...{//交换记录

　　              R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元

　　              R[j+1]=R[j];

              　　R[j]=R[0];

　　              exchange=TRUE; //发生了交换，故将交换标志置为真

　　          }

　　          if(!exchange) //本趟排序未发生交换，提前终止算法

　　          return;

　　} //endfor(外循环)

} 
		

int Partition(SqList &L, int low, int high) ...{

 // 交换顺序表L中子序列L.r[low..high]的记录，使枢轴记录到位，

   // 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它

   KeyType pivotkey;

   RedType temp;

   pivotkey = L.r[low].key;     // 用子表的第一个记录作枢轴记录

   while (low < high) ...{           // 从表的两端交替地向中间扫描

      while (low < high && L.r[high].key>=pivotkey) --high;

      temp=L.r[low];

      L.r[low]=L.r[high];

      L.r[high]=temp;           // 将比枢轴记录小的记录交换到低端

      while (low  < high && L.r[low].key < =pivotkey) ++low;

      temp=L.r[low];

      L.r[low]=L.r[high];

      L.r[high]=temp;           // 将比枢轴记录大的记录交换到高端

   }

   return low;                  // 返回枢轴所在位置

} // Partition        


void QSort(SqList &L, int low, int high) ...{

  // 对顺序表L中的子序列L.r[low..high]进行快速排序

  int pivotloc;

  if (low  <  high) ...{                      // 长度大于1

    pivotloc = Partition(L, low, high);  // 将L.r[low..high]一分为二

    QSort(L, low, pivotloc-1); // 对低子表递归排序，pivotloc是枢轴位置

    QSort(L, pivotloc+1, high);          // 对高子表递归排序

  }

} // QSort     

  

void QuickSort(SqList &L) ...{

   // 对顺序表L进行快速排序

   QSort(L, 1, L.length);

} // QuickSort 
		

void SelectSort(SqList &L) ...{

  // 对顺序表L作简单选择排序。

  int i,j;

  for (i=1; i < L.length; ++i) ...{ // 选择第i小的记录，并交换到位

    j = SelectMinKey(L, i);  // 在L.r[i..L.length]中选择key最小的记录

    if (i!=j) ...{                // L.r[i]←→L.r[j];   与第i个记录交换

      RedType temp;

      temp=L.r[i];

      L.r[i]=L.r[j];

      L.r[j]=temp;

    }

  }

} // SelectSort