教你几种排序的基本算法

现有基本的数据输出：

void OutPutSortResult(int num[],int length_num,int index)
{
    printf("this is %03d-th!\t",index);
    for(int i=0;i<length_num;i++)
        printf("%d ",num[i]);
    printf("\n");
}

写出最基本的main函数体：

int main()
{
    int num[] = {2,1,3,4,6,5,9,8,7,10,-1,20,300,0,79,81,45,99,103,46};
    int len = sizeof(num)/sizeof(int),i=0;

    printf("原始数据\t");
    for(i=0; i<len-1; i++)
        printf("%d ",num[i]);
    printf("%d\n\n",num[len-1]);

    MyBubbleMoreAdvanceSort(num,len,0);

    printf("\n排序之后的数据\t");
    for(i=0; i<len-1; i++)
        printf("%d ",num[i]);
    printf("%d\n",num[len-1]);

    return 0;
}

之后进行我们的基本的排序算法：

/*
插入排序：
该算法对较小的数据量的排序作用还是很不错的
该算法的执行过程与我们在打牌的过程挺像的，在打牌时
我们左手是空的，所有的牌都面朝下放在桌面上，
然后，一张一张的拿来插到指定的位置
*/
void MyInsertSort(int num[],int length_num,
                  int sort_type/*0:small to big ;>=1:big to small*/)
{
    for(int i=0; i<length_num; i++)
    {
        int j = 0;
        for(j=0; j<i; j++)
        {
            if(sort_type == 0)
            {
                if(num[j]>num[i])
                    break;
            }
            else
            {
                if(num[j]<=num[i])
                    break;
            }
        }

        if(j<i)
        {
            int temp = num[j];
            num[j++] = num[i];
            for(; j<=i; j++)
            {
                num[i] = num[j];
                num[j] = temp;
                temp = num[i];
            }
        }
        OutPutSortResult(num,length_num,i);
    }
}

运行结果如下：

/*
冒泡排序：
*/
void MyBubbleSort(int num[],int length_num,int sort_type)
{
    int i=0,j=0,k=0,flag = 1;
    for(i=0; i<length_num-1&&flag==1; i++)
    {
        flag = 0;
        for(j=0; j<length_num-1-i; j++)
        {
            if(num[j+1]<num[j] && sort_type == 0)
            {
                int temp = num[j+1];
                num[j+1] = num[j];
                num[j] =  temp;
                flag = 1;
            }
            else
            {
                if(num[j+1]>num[j] && sort_type != 0)
                {
                    int temp = num[j+1];
                    num[j+1] = num[j];
                    num[j] =  temp;
                    flag = 1;
                }
            }
        }
        OutPutSortResult(num,length_num,i);
    }
}

运行结果如下：

/*
改进的冒泡排序，对左右进行双向排序
*/
void MyBubbleMoreAdvanceSort(int num[],int length_num,int sort_type)
{
    int i=0,j=0,k=0;
    int left = 0,right = length_num-1;
    bool left_flag = true,right_flag = true;

    for(i=left; i<=right && (left_flag == true || right_flag == true); i++)
    {
        left_flag = false;
        right_flag = false;

        for(j=left,k=right; j<right || k>left; j++,k--)
        {
            /*大数沉底*/
            if(num[j] > num[j+1] && sort_type == 0)
            {
                int temp = num[j+1];
                num[j+1] = num[j];
                num[j] =  temp;
                right_flag = true;
            }
            else
            {
                if(num[j] < num[j+1] && sort_type != 0)
                {
                    int temp = num[j+1];
                    num[j+1] = num[j];
                    num[j] =  temp;
                    right_flag = true;
                }
            }

            /*小数上升*/
            if(num[k] < num[k-1] && sort_type == 0)
            {
                int temp = num[k];
                num[k] = num[k-1];
                num[k-1] = temp;
                left_flag = true;
            }
            else
            {
                if(num[k] > num[k-1] && sort_type != 0)
                {
                    int temp = num[k];
                    num[k] = num[k-1];
                    num[k-1] = temp;
                    left_flag = true;
                }
            }
        }
        right--;
        left++;
        OutPutSortResult(num,length_num,i);
    }
}

运行结果如下：

/*
选择排序：
*/
void MySelectSort(int num[],int length_num,int sort_type)
{
    int i=0,j=0,k=0,cur_index=0;
    for(i=0; i<length_num-1; i++)
    {
        cur_index = i;
        for(j=i+1; j<length_num; j++)
        {
            if(num[j]<num[cur_index] && sort_type == 0)
                cur_index = j;
            else
            {
                if(num[j]>num[cur_index] && sort_type != 0)
                    cur_index = j;
            }
        }


        if(i != cur_index)
        {
            int temp = num[i];
            num[i] = num[cur_index];
            num[cur_index] = temp;
        }
        OutPutSortResult(num,length_num,i);
    }
}

运行结果如下：

/*
希尔(shell)排序：
*/
void MyShellSort(int num[],int length_num,int sort_type)
{
    int i=0,j=0,k=0,index = 0;
    int gap = length_num/2;
    while(gap>0)
    {
        for(k=0; k<gap; k++)
        {
            for(i=k+gap; i<length_num; i+=gap)
            {
                for(j=i-gap; j>=k; j-=gap)
                {
                    if(num[j]>num[j+gap] && sort_type == 0)
                    {
                        int temp = num[j];
                        num[j] = num[j+gap];
                        num[j+gap] = temp;
                    }
                    else
                    {
                        if(num[j]<num[j+gap] && sort_type != 0)
                        {
                            int temp = num[j];
                            num[j] = num[j+gap];
                            num[j+gap] = temp;
                        }
                    }
                }
                OutPutSortResult(num,length_num,++index);
            }
        }
        gap /= 2;
    }
}

运行结果如下：

未完！待续！！！！