选择排序，插入排序，冒泡排序，归并排序，堆排序，基数排序的稳定性分析以及c语言代码

本题目为沙特教材《算法设计与分析》第100页的5.14题

1.选择排序稳定性:不稳定

int SelectSort(int *A,int length)
{
    for(int i=1;i<=lenth-1;i++)
    {    int min=A[i];
        int k=i;
        for(int j=i+1;j<=length;j++)
        {
            if(A[j]<min)
            {
                min=A[j];
                k=j;
            }
        }
        if(k!=i)    
        {
            int temp=A[k];
            A[k]=A[i];
            A[i]=temp;
        }
    }
}

举例子：以A8    B8  C7为例 

第一步会把C和A交换  变成C B A 此时为 C7 B8 A8

第二步不做交换 

结束

对该例子的分析：   如当例子为8  9 8 7 时 最后一个元素与第一个元素就会发生交换，会忽视中间的元素，跳跃性交换，此时就会产生不稳定情况。

2.插入排序 

 1 int InsertSort(int *A,int length)
 2 {
 3     for(j=2;j<=length;j++)
 4     {    
 5         i=j;
 6         temp=A[j];
 7         for(i=j;i>=2;i--)
 8             {
 9                 if(temp1])  //不用交换 只要把A[j]=A[j-1]即可 
10                     A[i]=A[i-1]; //A[i-1]右移 让A[i-1]找到自己合适的位置 
11                 else
12                     break;
13             }
14         A[i]=temp;
15     }
16 }

插入排序是稳定的 因为是从第2个数开始，一一与前面的数比较，确定自己合适的位置。这种比较，属于是与相邻的数之间进行的比较、交换，而相邻的数之间的比较、交换，与相邻数之间的比较得出是否交换的结果，这种交换并非忽略了中间的元素，因此是稳定的。

3.冒泡排序 较简单 为稳定的排序 此处不再解释

4.归并排序

int merge(int*A,int p,int q,int r) //合并A[p~q]和A[q+1~r]之间的元素
{    int B[100];
    int i,j,k;
    i=p;j=q+1;k=1;
    while(i<=q&&j<=r)
    {
        if(A[i]<=A[j])   
        {
            B[k++]=A[i++];
        }
        if(A[i]>A[j])
        {
            B[k++]=A[j++];
        }
    }    
    while(i<=q)
    {
        B[k++]=A[i++]; 
    }
    while(j<=r)
    {
        B[k++]=A[j++];
    }
    for(i=p,k=1;i<=r;)
    {
        A[i]=B[k];
        i++;
        k++;
    }
} 
int BottomupSort(int *A,int length)
{
    for(int i=1;i2)
    {    
        j=1;
        while(j+2*i-1<=length)
        {
            merge(A,j,j+i-1,j+2*i-1);
            j=j+2*i;
        }
        if(j+i-1//此处可加等号可不加等号  加等号那么当等号相等的时候 执行merge也直接退出了 
            merge(A,j,j+i-1,length);
    }
}
 

归并排序是稳定的。

其实归并排序的稳定与否，在于merge函数里面的if比较等号写到哪里。

if(A[i]<=A[j])   
        {
            B[k++]=A[i++];
        }
        if(A[i]>A[j])
        {
            B[k++]=A[j++];
        }

以A3 B3 C1 D3为例  最开始 A3和B3 比较进行归并（参考上面merge里面是A[i]<=A[j] 取A[i]放入辅助B数组中）得到A3 B3,  C1 和D3 比较归并得到C1 D3， 然后这两个再进行归并 辅助数组B中元素依次为C1  A3 B3 D3这里为什么A和B出现在D之前呢？ 因为我们在merge函数里 进行的是 判断A[i]<=A[j]的时候 将A[i]放入辅助数组中 ，即    if（A[1]<=A[4]） 和 if（A[2]<=A[4]） ，因为i的下标比j的小标小，所以我们优先取下标小的放在辅助数组中，这样就实现了稳定操作。    如果我们在merge函数里写的是   A[i]>=A[j]和A[i]

 5.堆排序

 堆排序是不稳定的，堆排序的算法过程可以在我的《堆排序常用函数》随笔中可见，此处不再写其代码。以A13 B10 C7 D9 E8 F8为例 算法过程步骤如下：

1.对初始混乱数据进行建堆：建堆结果为 A13 B10 F8 D9 E8 C7； 可以注意到 此时F8跑到了E8前面

2.首位元素和最后一个元素交换： 交换后的结果为 C7 B10 F8 D9 E8 A13 ，此时A13已经在正确的位置了

3.再对该数据建堆，此时不在用建堆函数，而只需要调整C7即可。  即调用Siftdown函数  新的堆为 B10 D9 F8 C7 E8

4。首位元素和最后一个元素再进行交换： E8  D9 F8 C7 B10，注意到此时E8又跑到了 F8前面 

5.建的新堆：D9 E8 F8 C7

6.交换 C7 E8 F8 D9

7.建新堆 E8 C7 F8

8.交换 F8 C7 E8

9.建新堆F8 C7

10.交换 C7 F8

11.结束

最终结果为 C7 F8 E8 D9 B10 A13  

这是因为，堆排序的两个元素比较时，这两个元素的位置之间隔了很多元素，并没有考虑这些元素中是否有与这两个元素相等的情况，因此会发生跳跃。

6.基数排序

#include
int getMaxdig(int* A,int length) //先找到数组A中的最大数，求出位数 
{    int max=A[1];
    for(int i=1;i<=length;i++)
    {
        if(A[i]>max)
            max=A[i];
    }
    int k=0;
    while(max>0)
    {
        max=max/10;
        k++;
    }
    return k;
}


void RadixSort(int* A,int length)
{    int i;
    int Output[100];//用来暂时存放每一次排序后的结果 
    int base=1;
    int dig=getMaxdig(A,length);
    for(int j=1;j<=dig;j++) //一共进行dig次的循环 0,13,3,542,748,14,214,18,63,616
    {        int Bucket[10]={0};
            for(i=1;i<=length;i++)
        {
            int t=(A[i]/base)%10;
            Bucket[t]++;        
        }    
        for(i=1;i<=9;i++)
        {
            Bucket[i]=Bucket[i]+Bucket[i-1]; //Bucket[i]内值表示 求余数后得i的元素集合中最后一个元素在Output中的位置 
        }
        for(i=length;i>=1;i--)
        {
            int t=(A[i]/base)%10; //这四行是核心代码  首先求的A[i]得第j位数字t 
            int locate=Bucket[t];//如果知道了A[i] 在output中的存储位置，那么A[i]即可放对位置 
            Bucket[t]=Bucket[t]-1;  //Bucket[t] 表示第j位小于等于t的数一共有Bucket[t]个，所以依次应该放的位置为locate，locate-1…… 
            Output[locate]=A[i];
        }
        for(i=1;i<=length;i++)
        {
            A[i]=Output[i]; 
        }
        base=10*base;
    }


}
int main()
{
    int A[100]={0,13,3,542};
    RadixSort(A,3);
    for(int i=1;i<=3;i++)
    {
        printf("%4d\n",A[i]);
    }

}

解释：1.找出最大的位数dig

2.用output临时存放每一次的结果，依次利用基数排序的第j位数字，确定该数应该放在output的哪一个位置上

 for(i=length;i>=1;i--)
        {
            int t=(A[i]/base)%10; //这四行是核心代码  首先求的A[i]得第j位数字t 
            int locate=Bucket[t];//如果知道了A[i] 在output中的存储位置，那么A[i]即可放对位置 
            Bucket[t]=Bucket[t]-1;  //Bucket[t] 表示第j位小于等于t的数一共有Bucket[t]个，所以依次应该放的位置为locate，locate-1…… 
            Output[locate]=A[i];
        }
这样从i=length开始写，是为了排序的稳定性。比如 A8  B8那么先把B8放在locate的位置，然后locate-1的位置放A8，保证A8仍旧在B8的前面，因此基数排序可以是稳定的。