Manchester-排序问题<2>(选择，冒泡，合并排序，附带图解）

解题思路:
选择排序：（思路：先从下标为0的数开始遍历，找到下标从0到9的数中最大的数，与下标为0的数交换；然后从下标为1的数开始遍历，找到下标从1到9的数中最大的数，与下标为1的数交换；.......直到从下标为9的数开始遍历后结束；）
假设有5个数：3 2 5 4 1，其过程就是：

第一遍：5 1 2 4 3

第二遍：5 4 1 2 3

第三遍：5 4 3 1 2

第四遍：5 4 3 2 1

第五遍：5 4 3 2 1  （因为最后一遍只有1 这个数，这遍可以省去，循环控制中，即循环次数N-1）

参考代码：

#include <stdio.h>
int N = 10;

int main()
{
    int    maxi;
    int    A[10];
    int    term;
    for ( int i = 0; i < N; i++ )
        scanf( "%d", &A[i] );

    for ( int i = 0; i < N - 1; i++ )
    {
        maxi = i;
        for ( int j = i; j < N; j++ )
        {
            if ( A[j] > A[maxi] )
                maxi = j;
        }


        term    = A[i];
        A[i]    = A[maxi];
        A[maxi] = term;


        /*A[i]=A[i]+ A[maxi];
         * printf("A[%d] =%d\n",i,A[i]);
         *
         * A[maxi]=A[i]- A[maxi];
         * printf("Amax[%d] =%d\n",maxi,A[maxi]);
         *
         * A[i]=A[i]- A[maxi];
         * printf("A[%d] =%d\n",i,A[i]);
         *
         * printf("\n");*/
    }

    for ( int i = 0; i < N - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d", A[N - 1] );
}

注意程序中：最大数的交换时，若不判断maxi 是否等于 i 的话，不可以写为：
A[i]=A[i]+ A[maxi]
A[maxi]=A[i]- A[maxi]
A[i]=A[i]- A[maxi]

因为当maix==i时，就等于一个变量和它自身交换，自身交换是不可以用的；最后会使得A[maxi]=0；A[i]=0；

如图：

最后结果不正确：

所以最好加上个判断

if(i!=maxi)
        {
        term    = A[i];
        A[i]    = A[maxi];
        A[maxi] = term;
        }
        上面这个可以不加，加的话更好，减少不必要的判断；
        或者
        if(i!=maxi)
        {
         A[i]=A[i]+ A[maxi]；
         A[maxi]=A[i]- A[maxi]；
         A[i]=A[i]- A[maxi]；
        }
        这个必须要加判断；

冒泡排序：

先下标为0的数，与其后面一个数作比较，小于它后面的那个数则交换；然后比较下标为1的，一直比较下去，到最后一个数结束；

比如 ：5 4 3 2

第一次：4 3 2 5

第二次：3 2 4

第三次:   2 3

参考代码：

#include <stdio.h>
int N = 10;

int main()
{
    int    A[10];
    int    term;
    for ( int i = 0; i < N; i++ )
        scanf( "%d", &A[i] );

    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N - i - 1; j++ )
        {
            if ( A[j] < A[j + 1] )
            {
                term = A[j];
                /* printf("j=%d  \n",j); */
                A[j] = A[j + 1];
                /* printf("j+1=%d\n\n",j+1); */
                A[j + 1] = term;


                /*A[j]=A[j]+A[j + 1];
                *  A[j + 1]=A[j]-A[j + 1];
                *  A[j]=A[j]-A[j + 1];*/
            }
        }

    for ( int i = 0; i < N - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d", A[N - 1] );
}

注意：for ( int j = 0; j < N - i - 1; j++ )红色部分减去1很重要；因为c语言语法检测不严格，数组越界的问题有时候

是不会报告出来的，只有在多组数据检测出错后才会发现越界等错误：

如果不减去1：对于有的数据会：stack smashing detected：

原因看下图：当输入这样的数据时

这张图中：交换两个数过程中，j+1后=10，而我们数组的下标只到9，A[j+1]这时候发生越界，这里面存的是随机值；

所以结果会不正确；

思路三：合并排序法（其思想为分治法：把一组数分为多组数，然后分别对这几组数排序，最后把排序好

的多组数，合并起来）

#include<stdio.h>
int N=10;
int B[10];
void Mesort(int *A,int left,int right);
void Merge(int *A,int *B,int left,int middle,int right);
void copy(int *A,int left,int right);
/*--------------------------------------------------------*/
int main()
{
int A[10];


for(int i=0;i<N;i++)
 scanf("%d",&A[i]);

 Mesort(A,0,N-1);

 for(int i=0;i<N-1;i++)
 printf("%d ",B[i]);
 printf("%d",B[N-1]);


}
/*--------------------------------------------------------*/
void Mesort(int *A,int left,int right)
{
 if(left<right)
 {
 int i=(left+right)/2;
 Mesort(A,left,i);
 Mesort(A,i+1 ,right);
 Merge(A,B,left,i,right);
 copy(A,left,right);
 }
}
/*--------------------------------------------------------*/
void Merge(int *A,int *B,int left,int middle,int right)
{
int  i=left,j=middle+1,k=left;

while((i<=middle)&&(j<=right))
{
if(A[i]>=A[j])
B[k++]=A[i++];
else
B[k++]=A[j++];
}

if(i>middle)
for(int q=j;q<=right;q++)
 B[k++]=A[q];
else
for(int q=i;q<=middle;q++)
 B[k++]=A[q];

}
/*--------------------------------------------------------*/
void copy(int *A,int left,int right)
{
for(;left<=right;left++)
A[left]=B[left];
}

觉得不错点个赞哦^_^