穩(wěn)定性

假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

堆排序、快速排序、希爾排序、直接選擇排序不是穩(wěn)定的排序算法，而基數(shù)排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩(wěn)定的排序算法。

復雜度

復雜度

堆排序

小頂堆過程：

1. 自下往上， 調整父節(jié)點>=子節(jié)點, root節(jié)點得到最大值， 類似于一趟冒泡過程；
   2.把root值放到最后面， 剩下的重復第一步， 得到次最大值， 放到次后面 重復這個步驟, 熟悉的兩層循環(huán)， 注意了， 這里數(shù)組下標從1開始。

void HeapSort(SqList* L)
{
    for (i = L->length; i > 1; i--)
    {
        for (int j = i/2; j >= 1; j--) {  //找到前i個結點的最大值過程
            HeapAdjust(L, j, i);
        }
        
        swap(L,1,i); //把最大值放到最后
    }   
}

HeapAdjust(SqList* L, int s, int m)  //調整父節(jié)點的值大于等于子節(jié)點
{
    if (s*2 <= m && L->r[s * 2] > L->r[s] ) {    
       swap( L->r[s] , L->r[s * 2]);
    } 
  
   if (s *2 + 1 <= m && L->r[s *2 + 1] > L->r[s]) {
         swap(L->r[s], L->r[s *2+ 1]);
} 

下面是一個優(yōu)化版的, 優(yōu)化版優(yōu)化在于
1. 調整父節(jié)點比子節(jié)點要大時采用遞歸操作；
2.第二趟冒泡的時候， 不再是從下往上調整， 而是從上往下調整;
void HeapSort(SqList* L)
{
    int i;
    for (i = L->length/2; i >=1 ;i--)  //找到最大值；
    {
        HeapAdjust(L, i, L->length);
    }
    for (i = L->length;i >1; i--)
    {
        swap(L,1,i); 
        HeapAdjust(L, 1, i-1); //優(yōu)化了 
    }   
}

HeapAdjust(SqList* L, int s, int m)  //調整父節(jié)點的值大于等于子節(jié)點以及子節(jié)點
//大于等于子子節(jié)點
{
    int temp, j;
    temp = L->r[s];
    for(j = s*2; j<=m;  j = j*2)
    {
        if (j + 1<= m && L->r[j] < L->r[j+1])  子節(jié)點最大值, 如果沒有右節(jié)點，
//則左節(jié)點最大
            j++;
        if (temp >= L->r[j])
            break;

        swap(L->r[j/2] , L->r[j]);   //父節(jié)點小于子節(jié)點
    } 
}

快速排序

1.i =L; j = R; 將基準數(shù)挖出形成第一個坑a[i]。
2.j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。
3.i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。

int AdjustArray(int s[], int l, int r) {  //返回調整后基準數(shù)的位置 
    int i = l, j = r; 
    int x = s[l]; //s[l]即s[i]就是第一個坑 
    while (i < j) { 
        // 從右向左找小于x的數(shù)來填s[i] 
        while(i < j && s[j] >= x) j--;   
        if(i < j) { 
            s[i] = s[j]; //將s[j]填到s[i]中，s[j]就形成了一個新的坑 
            i++; 
        } 

        // 從左向右找大于或等于x的數(shù)來填s[j] 
        while(i < j && s[i] <= x) i++;   
        if(i < j) { 
            s[j] = s[i]; //將s[i]填到s[j]中，s[i]就形成了一個新的坑 
            j--; 
        } 
    } 
    //退出時，i等于j。將x填到這個坑中。 
    s[i] = x;   //補坑千萬不要忘記了

    return i; 
} 

void quick_sort1(int s[], int l, int r) 
{ 
    if (l < r) { 
        int i = AdjustArray(s, l, r);//先成挖坑填數(shù)法調整s[] 
        quick_sort1(s, l, i - 1); // 遞歸調用   
        quick_sort1(s, i + 1, r); 
    } 
}

歸并排序

1.先對半分， 兵分兩路
2.使用輔助數(shù)組把兩路合并起來

void mergearray(int a[], int first, int mid, int last, int temp[]) 
{ 
    int i = first, j = mid + 1; 
    int m = mid,   n = last; 
    int k = 0; 

    while (i <= m && j <= n) 
    { 
        if (a[i] <= a[j]) 
            temp[k++] = a[i++]; 
        else 
            temp[k++] = a[j++]; 
    } 

    while (i <= m) 
        temp[k++] = a[i++]; 

    while (j <= n) 
        temp[k++] = a[j++]; 

    for (i = 0; i < k; i++) 
        a[first + i] = temp[i]; 
} 
void mergesort(int a[], int first, int last, int temp[])  { 
    if (first < last)  { 
        int mid = (first + last) / 2; 
        mergesort(a, first, mid, temp);    //左邊有序 
        mergesort(a, mid + 1, last, temp); //右邊有序 
        mergearray(a, first, mid, last, temp); //再將二個有序數(shù)列合并 
    } 
}