C#排序算法的比擬剖析

O(n²)

O(n²)

O(n)

O(1)

O(n²)

O(n²)

O(n)

O(1)

O(n²)

O(n²)

O(n²)

O(1)

O(nlog₂n)~O(n²)

O(nlog₂n)~O(n²)

O(1)

O(nlog₂n)

O(n²)

O(nlog₂n)

O(log₂n)

O(nlog₂n)

O(nlog₂n)

O(nlog₂n)

O(1)

O(nlog₂n)

O(nlog₂n)

O(nlog₂n)

O(n)

1. 算法的時光龐雜度普通情形下指最壞情形下的漸近時光龐雜度。
2. 排序算法的穩固性會對多症結字排序發生影響。
 
上面經由過程C#代碼解釋分歧的排序算法
 
拔出排序

時光龐雜度：均勻情形—O(n2) 最壞情形—O(n2) 幫助空間：O(1) 穩固性：穩固
拔出排序是在一個曾經有序的弁言列的基本上，一次拔出一個元素。固然，剛開端這個有序的弁言列只要1個元素，就是第一個元素。比擬是從有序序列的末尾開端，也就是想要拔出的元素和曾經有序的最年夜者開端比起，假如比它年夜則直接拔出在厥後面，不然一向往前找直到找到它該拔出的地位。假如碰見一個和拔出元素相等的，那末拔出元素把想拔出的元素放在相等元素的前面。所以，相等元素的前後次序沒有轉變，從原無序序列出去的次序就是排好序後的次序，所以拔出排序是穩固的。
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

希爾排序(shell)

時光龐雜度：幻想情形—O(nlog2n) 最壞情形—O(n2) 穩固性：不穩固

希爾排序是依照分歧步長對元素停止拔出排序，當剛開端元素很無序的時刻，步長最年夜，所以拔出排序的元素個數很少，速度很快；當元素根本有序了，步長很小，拔出排序關於有序的序列效力很高。所以，希爾排序的時光龐雜度會比o(n^2)好一些。因為屢次拔出排序，我們曉得一次拔出排序是穩固的，不會轉變雷同元素的絕對次序，但在分歧的拔出排序進程中，雷同的元素能夠在各自的拔出排序中挪動，最初其穩固性就會被打亂，所以shell排序是不穩固的。
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

冒泡排序

時光龐雜度：均勻情形—O(n2) 最壞情形—O(n2) 幫助空間：O(1) 穩固性：穩固
冒泡排序就是把小的元素往前調或許把年夜的元素往後調。比擬是相鄰的兩個元素比擬，交流也產生在這兩個元素之間。所以，假如兩個元素相等，我想你是不會再無聊地把他們倆交流一下的；假如兩個相等的元素沒有相鄰，那末即便經由過程後面的兩兩交流把兩個相鄰起來，這時候候也不會交流，所以雷同元素的前後次序並沒有轉變，所以冒泡排序是一種穩固排序算法。
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(外輪回)
}

疾速排序

時光龐雜度：均勻情形—O(nlog2n) 最壞情形—O(n2) 幫助空間：O(log2n) 穩固性：不穩固
疾速排序有兩個偏向，右邊的i下標一向往右走，當a[i] <= a[center_index]，個中center_index是中樞元素的數組下標，普通取為數組第0個元素。而左邊的j下標一向往左走，當a[j] > a[center_index]。假如i和j都走不動了，i <= j, 交流a[i]和a[j],反復下面的進程，直到i>j。 交流a[j]和a[center_index]，完成一趟疾速排序。在中樞元素和a[j]交流的時刻，很有能夠把後面的元素的穩固性打亂，好比序列為 5 3 3 4 3 8 9 10 11， 如今中樞元素5和3(第5個元素，下標從1開端計)交流就會把元素3的穩固性打亂，所以疾速排序是一個不穩固的排序算法，不穩固產生在中樞元素和a[j]交流的時辰。
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

選擇排序

時光龐雜度：均勻情形—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) 穩固性：不穩固

我們曉得堆的構造是節點i的孩子為2*i和2*i+1節點，年夜頂堆請求父節點年夜於等於其2個子節點，小頂堆請求父節點小於等於其2個子節點。在一個長為n的序列，堆排序的進程是從第n/2開端和其子節點共3個值選擇最年夜(年夜頂堆)或許最小(小頂堆),這3個元素之間的選擇固然不會損壞穩固性。但當為n/2-1, n/2-2, ...1這些個父節點選擇元素時，就會損壞穩固性。有能夠第n/2個父節點交流把前面一個元故舊換曩昔了，而第n/2-1個父節點把前面一個雷同的元素沒有交流，那末這2個雷同的元素之間的穩固性就被損壞了。所以，堆排序不是穩固的排序算法
void HeapAdjust(HeapType &H, int s, int m) {
  // 已知H.r[s..m]中記載的症結字除H.r[s].key以外均知足堆的界說，
  // 本函數調劑H.r[s]的症結字，使H.r[s..m]成為一個年夜頂堆
  // （對個中記載的症結字而言）
  int j;
  RedType rc;
  rc = H.r[s];
  for (j=2*s; j < =m; j*=2) {   // 沿key較年夜的孩子結點向下挑選
    if (j < m && H.r[j].key < H.r[j+1].key) ++j; // j為key較年夜的記載的下標
    if (rc.key >= H.r[j].key) break;         // rc應拔出在地位s上
    H.r[s] = H.r[j];  s = j;
  }
  H.r[s] = rc;  // 拔出
} // HeapAdjust   
 
void HeapSort(HeapType &H) {
   // 對次序表H停止堆排序。
   int i;
   RedType temp;
   for (i=H.length/2; i>0; --i)  // 把H.r[1..H.length]建成年夜頂堆
      HeapAdjust ( H, i, H.length );
      for (i=H.length; i>1; --i) {
         temp=H.r[i];
         H.r[i]=H.r[1];
         H.r[1]=temp;  // 將堆頂記載和以後未經排序子序列Hr[1..i]中
                       // 最初一個記載互相交流
         HeapAdjust(H, 1, i-1);  // 將H.r[1..i-1] 從新調劑為年夜頂堆
      }
} // HeapSort

合並排序

時光龐雜度：均勻情形—O(nlog2n) 最壞情形—O(nlog2n) 幫助空間：O(n) 穩固性：穩固
合並排序是把序列遞歸地分紅短序列，遞歸出口是短序列只要1個元素(以為直接有序)或許2個序列(1次比擬和交流),然後把各個有序的段序列歸並成一個有序的長序列，赓續歸並直到原序列全體排好序。可以發明，在1個或2個元素時，1個元素不會交流，2個元素假如年夜小相等也沒有人有意交流，這不會損壞穩固性。那末，在短的有序序列歸並的進程中，穩固是能否遭到損壞？沒有，歸並進程中我們可以包管假如兩個以後元素相等時，我們把處在後面的序列的元素保留在成果序列的後面，如許就包管了穩固性。所以，合並排序也是穩固的排序算法。
void Merge (RedType SR[], RedType TR[], int i, int m, int n) {
   // 將有序的SR[i..m]和SR[m+1..n]合並為有序的TR[i..n]
   int j,k;
   for (j=m+1, k=i;  i < =m && j < =n;  ++k) {
      // 將SR中記載由小到年夜地並入TR
      if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];
      else TR[k] = SR[j++];
   }
   if (i < =m)  // TR[k..n] = SR[i..m];  將殘剩的SR[i..m]復制到TR
      while (k < =n && i < =m) TR[k++]=SR[i++];
   if (j < =n)  // 將殘剩的SR[j..n]復制到TR
      while (k < =n &&j  < =n) TR[k++]=SR[j++];
} // Merge   
 
void MSort(RedType SR[], RedType TR1[], int s, int t) {
   // 將SR[s..t]合並排序為TR1[s..t]。
   int m;
   RedType TR2[20];
   if (s==t) TR1[t] = SR[s];
   else {
      m=(s+t)/2;            // 將SR[s..t]等分為SR[s..m]和SR[m+1..t]
      MSort(SR,TR2,s,m);    // 遞歸地將SR[s..m]合並為有序的TR2[s..m]
      MSort(SR,TR2,m+1,t);  // 將SR[m+1..t]合並為有序的TR2[m+1..t]
      Merge(TR2,TR1,s,m,t); // 將TR2[s..m]和TR2[m+1..t]合並到TR1[s..t]
   }
} // MSort   
 
void MergeSort(SqList &L) {
  // 對次序表L作合並排序。
  MSort(L.r, L.r, 1, L.length);
} // MergeSort

願望本文所述對年夜家的C#法式設計有所贊助。