杰人编程网

• 以下排序算法默认从小到大的升序排序。

冒泡排序

• 思路从数组的第一个数a[0]开始，向后遍历，每次比较a[i]和a[i+1]的值若a[i]大于a[i+1]，就交换两个位置的数的值。重复上述1和2的操作至a[n-2]。
• 优化第三部改为重复上述操作直至不再出现值的交换。（若一次遍历没有值得交换，说明该数组从左到右是升序）
• 代码

void bubbleSort(int a[],int n)
{
    if(n <= 1)
        return;
    for(int i = 0; i < n; i++)
    {
        int flag = 0;
        for(int j = 0; j < n - 1 - i j ifaj> a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;  
            }
        }
        if(!flag)
            break;
    }
}

插入排序

• 思路讲解所谓插入排序，就是把a[1]值插入到a[0]中，然后a[2]插入到a[0]--a[1]的数组中，依次向后遍历，直至将a[n-1]插入到a[0] -- a[n-2]的数组中。保存a[i]的值，因为a[0]到a[i-1]已经使用插入排序排好序了，此时从后往前数值依次变小，判断a[i-1],a[i-2]...等等数中，小于a[i]的值，将a[i]插入该数位置之后。
• 思路先用num保存a[i]的值，每次执行插入操作时，判断a[i]与a[i-k]的值的大小，（k从1到i）若a[i]小于a[i-1]，将a[i]的值后移一位到a[i+1]的位置，然后继续比较a[i]与a[i-2]的值.若a[i]大于a[i-k]，则直接退出循环2和3步骤将a[i]的值插入a[i+1]的位置
• 图解

• 代码

void bubbleSort(int a[],int n)
{
    if(n <= 1)
        return;
    for(int i = 0; i < n; i++)
    {
        int flag = 0;
        for(int j = 0; j < n - 1 - i j ifaj> a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;  
            }
        }
        if(!flag)
            break;
    }
}

选择排序

• 思路选择排序最好理解将数组的第一个数a[0]与其他数a[1]到a[n-1]做比较如果小于a[0]就和a[0]交换。这样，一次的循环就可以把数组最小的数放在a[0].再一次遍历a[1]到a[n-1]。
• 代码// 插入排序，a 表示数组，n 表示数组大小

// 插入排序，a 表示数组，n 表示数组大小
void insertionSort(int a[], int n) 
{
    if(n <= 1)
        return;
    for(int i = 1; i < n i int value='a[i];' int j forj='i' - 1 j>= 0; j--)
        {
            if(value < a[j])
                a[j + 1] = a[j];
            else
                break;
        }
        a[j + 1] = value;
    }
}

总代码

#include 
#include 

//函数声明
void initArray(int a[],int n);
void printArray(int a[],int n);
void bubbleSort(int a[],int n);
void insertionSort(int a[], int n);
void choose(int a[], int n);

int main()
{
    int a[5];
    //冒泡排序
    initArray(a,5);
    printf("原数组：");
    printArray(a,5);
    bubbleSort(a,5);
    printf("冒泡排序后数组：");
    printArray(a,5);
    //插入排序
    initArray(a,5);
    printf("原数组：");
    printArray(a,5);
    insertionSort(a,5);
    printf("插入排序后数组：");
    printArray(a,5);
    //选择排序
    initArray(a,5);
    printf("原数组：");
    printArray(a,5);
    choose(a,5);
    printf("选择排序后数组：");
    printArray(a,5);

    return 0;
}

void initArray(int a[],int n)
{
    for(int i = 0; i < n; i++)
        a[i] = rand()%100 + 10;
}

//数组输出函数
void printArray(int a[],int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

// 冒泡排序，a 表示数组，n 表示数组大小
void bubbleSort(int a[],int n)
{
    if(n <= 1)
        return;
    for(int i = 0; i < n; i++)
    {
        int flag = 0;
        for(int j = 0; j < n - 1 - i j ifaj> a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;  
            }
        }
        if(!flag)
            break;
    }
}


// 插入排序，a 表示数组，n 表示数组大小
void insertionSort(int a[], int n) 
{
    if(n <= 1)
        return;
    for(int i = 1; i < n i int value='a[i];' int j forj='i' - 1 j>= 0; j--)
        {
            if(value < a[j])
                a[j + 1] = a[j];
            else
                break;
        }
        a[j + 1] = value;
    }
}

// 选择排序，a 表示数组，n 表示数组大小
void choose(int a[], int n) 
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n j ifai> a[j])
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp; 
            }
        }
    }
}