穩(wěn)定性

假定在待排序的記錄序列中涡扼，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序盟庞，這些記錄的相對(duì)次序保持不變壳澳，即在原序列中，ri=rj茫经，且ri在rj之前，而在排序后的序列中萎津，ri仍在rj之前卸伞，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的锉屈。

堆排序荤傲、快速排序、希爾排序颈渊、直接選擇排序不是穩(wěn)定的排序算法遂黍，而基數(shù)排序、冒泡排序俊嗽、直接插入排序雾家、折半插入排序、歸并排序是穩(wěn)定的排序算法绍豁。

復(fù)雜度

復(fù)雜度

堆排序

小頂堆過程：

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

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

HeapAdjust(SqList* L, int s, int m)  //調(diào)整父節(jié)點(diǎn)的值大于等于子節(jié)點(diǎn)
{
    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]);
} 

下面是一個(gè)優(yōu)化版的, 優(yōu)化版優(yōu)化在于
1. 調(diào)整父節(jié)點(diǎn)比子節(jié)點(diǎn)要大時(shí)采用遞歸操作英染；
2.第二趟冒泡的時(shí)候揽惹， 不再是從下往上調(diào)整， 而是從上往下調(diào)整;
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)  //調(diào)整父節(jié)點(diǎn)的值大于等于子節(jié)點(diǎn)以及子節(jié)點(diǎn)
//大于等于子子節(jié)點(diǎn)
{
    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é)點(diǎn)最大值, 如果沒有右節(jié)點(diǎn)永丝，
//則左節(jié)點(diǎn)最大
            j++;
        if (temp >= L->r[j])
            break;

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

快速排序

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

int AdjustArray(int s[], int l, int r) {  //返回調(diào)整后基準(zhǔn)數(shù)的位置 
    int i = l, j = r; 
    int x = s[l]; //s[l]即s[i]就是第一個(gè)坑 
    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]就形成了一個(gè)新的坑 
            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]就形成了一個(gè)新的坑 
            j--; 
        } 
    } 
    //退出時(shí)撼泛，i等于j挠说。將x填到這個(gè)坑中。 
    s[i] = x;   //補(bǔ)坑千萬不要忘記了

    return i; 
} 

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

歸并排序

1.先對(duì)半分愿题， 兵分兩路
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); //再將二個(gè)有序數(shù)列合并 
    } 
}