C#排序算法的比较分析

} // 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

 

选择排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：不稳定
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

复制代码 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

 

堆排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间：O(1) 稳定性：不稳定