排序穩(wěn)定性和分類

穩(wěn)定性:

如果在元素序列中有兩個元素R[i]和R[j]爽室，他們的排序碼K[i]==K[j]汁讼，且在排序之前，R[i]在R[j]前面。若在排序后嘿架，R[i]仍然在R[j]前面瓶珊，則稱這個算法是穩(wěn)定的。否則耸彪，這個算法是不穩(wěn)定的伞芹。

怎么理解穩(wěn)定性？穩(wěn)定性是指相同元素在排序后相對位置保持不變蝉娜。舉個例子唱较，如果A和B的值相同，排序前B是在A的后面召川，那么按值排序后B仍然在A的后面南缓，這就叫穩(wěn)定。

分類

內(nèi)排序和外排序

內(nèi)排序是在排序的整個過程中荧呐，待排序的所有記錄全部被放置在內(nèi)存中汉形。
外排序是由于排序的記錄個數(shù)太多，不能同時放置在內(nèi)存倍阐，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進行获雕。

我們把內(nèi)排序分為插入排序、交換排序收捣、選擇排序和歸并排序

排序分類

交換排序

冒泡排序

最簡單的一種排序算法，小的往左移動庵楷，大的往右罢艾，整個過程就像是水中氣泡上浮。在相鄰兩個元素的比較中尽纽，如果相等咐蚯，則沒有必要交換。

  void BubbleSorting(int a[] , int n)
 {
     for(int i = 0; i < n-1; i++)
     {
         for(int j = 0; j < n-1-i; j++)
         {
             if(a[j] > a[j+1])
             {
                 int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }   
}

冒泡排序優(yōu)化

如果我們的待排序序列已經(jīng)是有序的弄贿，那么之后的大量比較就是多余的了春锋，所以我們設置標記flag，如果有數(shù)據(jù)交換差凹，則flag為true期奔，直到?jīng)]有數(shù)據(jù)交換的時候，退出最外層循環(huán)危尿。這樣可以避免因已經(jīng)有序的情況下的無意義循環(huán)判斷呐萌。

 void BubbleSorting(int a[] , int n)
 {
    Status flag=TRUE;
     for(int i = 0; i < n-1 && flag; i++)
     {
        flag = FALSE;
         for(int j = 0; j < n-1-i; j++)
         {
             if(a[j] > a[j+1])
             {
                 int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                flag=TRUE;  /*有數(shù)據(jù)交換*/
            }
        }
    }   
}

快速排序

快速排序（Quick Sort）的基本思想是：通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P鍵字均比另一部分記錄的關鍵字小谊娇，則可以分別對這兩部分記錄繼續(xù)進行排序肺孤，以達到整個序列有序的目的。

這里分享一篇介紹快排的文章，看了之后會更容易理解快排赠堵。
坐在馬桶上看算法：快速排序

從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”小渊。先從右往左找一個小于6的數(shù)，再從左往右找一個大于6的數(shù)茫叭，然后交換他們酬屉。

右邊的哨兵先出發(fā)

需要讓右邊的哨兵先出動，這一點非常重要杂靶。

第一次交換

左邊的哨兵找到了比6大的值梆惯，右邊的哨兵找到了比6小的值，交換吗垮。

交換結(jié)束

再次尋找

再次出發(fā)尋找

交換成功

然后哨兵們相遇了垛吗，停留在3這里

哨兵指針指向同一個數(shù)

我們將基準數(shù)6和3進行交換。

與基準數(shù)交換

到此第一輪“探測”真正結(jié)束烁登。此時以基準數(shù)6為分界點怯屉，6左邊的數(shù)都小于等于6，6右邊的數(shù)都大于等于6饵沧。

第一輪結(jié)束

先選取一個關鍵字锨络，然后想盡辦法將它放到一個位置，使得它的左邊的值都比它小狼牺，右邊的值都比它大羡儿，我們將這樣的關鍵字成為樞軸（pivot）。

最開始選取的6就是樞軸是钥，完成第一輪排序之后掠归，再對6兩邊的低子表和高子表進行同樣的操作，也就是遞歸操作悄泥。

void quicksort(int* a,int low,int high)
{   //注意參數(shù)虏冻，low指的是數(shù)組的最小下標，high指的是數(shù)組的最大下標
    int i,j,t,temp;
    if(low>high)
       return;  //遞歸出口

    temp=a[low]; //temp中存的就是基準數(shù)
    i=low;
    j=high;
    while(i!=j)
    {
             //順序很重要弹囚，要先從右邊開始找
              while(a[j]>=temp && i<j)
                       j--;
              //再找左邊的
              while(a[i]<=temp && i<j)
                       i++;
              //交換兩個數(shù)在數(shù)組中的位置
              if(i<j)
              {
                       t=a[i];
                       a[i]=a[j];
                       a[j]=t;
              }
    }
    //最終將基準數(shù)歸位
    a[low]=a[i];
    a[i]=temp;

    quicksort(a,low,i-1);//繼續(xù)處理左邊的厨相，這里是一個遞歸的過程
    quicksort(a,i+1,high);//繼續(xù)處理右邊的 ，這里是一個遞歸的過程

}

快排優(yōu)化

優(yōu)化選取樞軸

隨機選扰葛摹：如果首個關鍵字太大或者太小都會影響性能蛮穿，我們選取首個作為樞軸就變成了一種不合理的做法。所以隨機選取獲得一個low與high之間的數(shù)rnd有利于解決毁渗。
三數(shù)取中法：取三個關鍵字先進行排序绪撵，將中間數(shù)作為樞軸，一般是左祝蝠、右音诈、中間三個數(shù)幻碱。
九數(shù)取中：分三次取樣，每次取三個數(shù)细溅，三個樣品各取中數(shù)褥傍，再從中取中數(shù)。

優(yōu)化不必要的交換
優(yōu)化小數(shù)組時的排序方案
增加一個判斷喇聊，當high-low不大于某個常數(shù)時（7或者50或者其它的）就用直接插入排序恍风，保證最大化地利用兩種排序的優(yōu)勢來完成工作。
優(yōu)化遞歸操作
尾遞歸優(yōu)化誓篱，兩次遞歸變成迭代朋贬，縮減堆棧深度，提高整體性能窜骄。

選擇排序

直接選擇排序

通過遍歷比較锦募，記錄下最小值，然后和目標元素進行交換邻遏。

void selectSort(int* a,int n)
{
   int i,j,temp;
   for(i=0;i<n;i++)
   {
      int min=i;
      for(j=i+1;j<n;j++)   //遍歷完剩下的數(shù)字
      {                    //如果有比當前最小值小的數(shù)字府瞄，把下標賦給它
         if(a[j]<a[min])
         {
            min=j;
         }
      }
      if(i!=min){   //如果min不等于i涮帘，說明找到最小值，交換
         temp = a[i];
         a[i]=a[min];
         a[min]=temp;
      }
   }
}

推排序

直接選擇排序的升級版
分享一篇不錯的文章：圖解排序算法之堆排序

完全二叉樹

若設二叉樹的深度為h奠涌，除第 h 層外职辨，其它各層 (1～h-1) 的結(jié)點數(shù)都達到最大個數(shù)抬闷，第 h 層所有的結(jié)點都連續(xù)集中在最左邊魔市，這就是==完全二叉樹==督禽。

堆

堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為==大頂堆==（最大堆）另锋；或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值矫废，稱為==小頂堆==（最小堆）。如下圖：

用簡單的公式來描述一下堆的定義就是：

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本步驟

構造初始堆
將給定的無序序列依次存入數(shù)組砰蠢，該數(shù)組即為一顆完全二叉樹，將這棵二叉樹構造成堆（一般升序采用大頂堆唉铜，降序采用小頂堆）台舱。從最后一個非葉節(jié)點開始遞減，逐次將每個相應的二叉樹調(diào)整成大頂堆潭流，最后竞惋，整個二叉樹即為大頂堆。必須注意的是灰嫉，在交換之后拆宛，必須考量節(jié)點對其子節(jié)點是否有影響，判斷是否還滿足大頂堆（小頂堆）的原則讼撒，每一次交換都必須要循環(huán)把子樹部分判斷清楚浑厚。
將堆頂元素與末尾元素交換股耽，將最大元素"沉"到數(shù)組末端
重新調(diào)整結(jié)構，使其滿足堆定義钳幅，然后繼續(xù)交換堆頂元素與當前末尾元素物蝙，反復執(zhí)行調(diào)整+交換步驟。數(shù)組分為兩部分：堆與已排序列敢艰，直至最后一個堆元素诬乞，整個序列有序**

簡單點說就是：
1.存入數(shù)據(jù)（完全二叉樹）
2.將前n個元素調(diào)整為最大堆
3.交換堆頂和堆尾元素，n=n-1钠导，轉(zhuǎn)2

void swap(int* a,int i,int j){
   int temp=a[i];
   a[i]=a[j];
   a[j]=temp;
}
void HeapAdjust(int H[],int start,int end)//堆調(diào)整震嫉，將start和end之間的元素調(diào)整為最大堆
{
    //元素從數(shù)組下標1開始儲存，所以parent訪問二叉樹左右兒子分別為2*parent 和 2*parent+1牡属；
    int temp=H[start];
    int parent=start,child;
    while(2*parent<=end)
    {
        child=2*parent;
        if(child!=end&&H[child]<H[child+1])++child;
        if(temp>H[child])break;
        else H[parent]=H[child];
        parent=child;
    }
    H[parent]=temp;
}

void HeapSort(int H[],int L,int R)//堆排序
{
    for(int i=(R-L+1)/2;i>=L;--i)//調(diào)整整個二叉樹為最大堆
        HeapAdjust(H,i,R);
    for(int i=R;i>=L;--i)
    {
        swap(H,L,i);
        HeapAdjust(H,L,i-1);
    }
}

使用實例：

 int a[10]={0,50,10,90,30,70,40,80,60,20};
 HeapSort(a,1,9);

其實以上代碼還不算很好理解票堵，可以看看《大話數(shù)據(jù)結(jié)構》里面的代碼實例。

數(shù)據(jù)結(jié)構（三）：排序算法（上）