冒泡排序、选择排序、插入排序实现

最近在忙着准备面试，，，压力贼大，头疼，脚疼，牙疼，反正哪都不舒服，可能因为是第一次吧，不过还是要认真复习一下三种基本的排序吧，这基本是每个程序员都应该掌握的一种算法！！

---

目录

 

选择排序：

插入排序：

冒泡排序：

整个源文件：

执行效果图：

---

• 选择排序：

void SelectSort(int array[],int size)
{
    int i,j,tmp,min;

    if(array == NULL || size <= 0)    /* 参数合法性检测 */
    {
        printf("error!");
        return;
    }

    for(i=0;i<size-1;i++)
    {
        min = i;    /* 每次开始都假设i为最小值下标 */
        for(j=i+1;j<size;j++)
        {
            if(array[min] > array[j])   /* 从小到大 */
            {
                min = j;
            }
        }
        if(min != i)    /* 如果不相等就说明min发生了变化且为最小值下标，所以要交换 */
        {
            tmp = array[min];
            array[min] = array[i];
            array[i] = tmp;
        }
    }
}

选择排序算法核心：双重for循环，每次在外循环中拟定一个最小值（最大值），然后再内循环中采用类似打擂台的方法找出最值，并记下最值的数组下标。每当当内循环结束之后，都去比较当初拟定的最值下标是否一致，如果不一致就交换数据内容。

程序执行图解：

 

• 插入排序：

void InsertSort(int array[],int size)
{
    int i,j=0,tmp;
    if(array == NULL || size <= 0)    /* 参数有效性检查 */
    {
        printf("error!");
        return;
    }

    for(i=1;i<size;i++)
    {
        tmp = array[i];
        j = i - 1;
        while(j>=0 && tmp>array[j])   /* 从大到小排序，循环，直到前部分为有序 */
            {
                array[j+1] = array[j];
                j--;
            }
        array[j+1] = tmp;
    }
}

插入排序算法核心：每次纳入一个数组元素进行小范围排序（纳入的元素不要求是最值，上程序中就每次在外循环中纳入array[ i ]），当排序到完最后一个的时候就变成整体有序了。

程序执行图解：

• 冒泡排序：

void BubSort(int array[],int size)
{
    int i,j,tmp;

    if(array == NULL || size <= 0)
    {
        printf("error!");
        return;
    }
    for(i=0;i<size-1;i++)
        for(j=0;j<size-1-i;j++)
        if(array[j] > array[j+1]) //从小到大
        {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
        }

}

冒泡排序算法核心：双重for循环，当排序要求为从小到大排，那么，每次执行完一次内循环，必将确定一个最大值并安置在数组的尾部。那么若数组元素为5个，则外循环只需要循环4次，因为最后一次循环已经没有数组元素比较了，仅剩它自己。至于内循环范围怎么确定？我有个小技巧：先不管，写出下面替换的等式，然后根据替换的数组下标，考虑极端情况反推出限制范围。

程序执行图解：

• 整个源文件：

#include <stdio.h>
#include <stdlib.h>

void InsertSort(int *,int );
void SelectSort(int *,int );
void BubSort(int *,int );
void print(int *,int );

int main()
{

    int array[] = {1,23,5,6,9,7};
    int size = sizeof(array)/4;

    printf("\nSelectSort befort\n");
    print(array,size);
    SelectSort(array,size);
    printf("\nSelectSort after\n");
    print(array,size);

    printf("\n\nInsertSort befort\n");
    print(array,size);
    InsertSort(array,size);
    printf("\nInsertSort after\n");
    print(array,size);

    printf("\n\nBubSort befort\n");
    print(array,size);
    BubSort(array,size);
    printf("\nBubSort after\n");
    print(array,size);

    return 0;
}

void InsertSort(int array[],int size)
{
    int i,j=0,tmp;
    if(array == NULL)
    {
        printf("error!");
        return;
    }

    for(i=1;i<size;i++)
    {
        tmp = array[i];
        j = i - 1;
        while(j>=0 && tmp>array[j])   /* 从大到小排序 */
            {
                array[j+1] = array[j];
                j--;
            }
        array[j+1] = tmp;
    }
}
void SelectSort(int array[],int size)
{
    int i,j,tmp,min;

    if(array == NULL)
    {
        printf("error!");
        return;
    }

    for(i=0;i<size-1;i++)
    {
        min = i;
        for(j=i+1;j<size;j++)
        {
            if(array[min] > array[j])   /* 从小到大 */
            {
                min = j;
            }
        }
        if(min != i)
        {
            tmp = array[min];
            array[min] = array[i];
            array[i] = tmp;
        }
    }
}
void BubSort(int array[],int size)
{
    int i,j,tmp;

    if(array == NULL)
    {
        printf("error!");
        return;
    }
    for(i=0;i<size-1;i++)
        for(j=0;j<size-1-i;j++)
        if(array[j] > array[j+1]) /* 从小到大 */
        {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
        }

}
void print(int array[],int size)
{
    int i;
    if(array == NULL)
    {
        printf("error!");
        return;
    }
    for(i=0;i<size;i++)
        printf("%d\t",array[i]);
}

• 执行效果图：