温习排序算法（基于C指针）

2022-10-28 14:11:58

以前学过的数据结构课，貌似已经忘得一干二净了，偶然又翻起，书中最后一章详细介绍了7种排序算法，现在对其中4种做个总结。（为啥只总结4种，当然是因为偷懒，只想总结简单又常用的！）

先贴一张排序分类图：

1.冒泡法：

主要思想：每次比较相邻的两个数，较小的数向上冒，较大的数向下沉。

演示效果：

C代码：（指针p指向待排序列的首地址，length是待排序列的总长度，下同）

swap(int *p1, int *p2)

{

    int tmp;

    tmp = *p1;

    *p1 = *p2;

    *p2 = tmp;

}

Msort(int *p, int length)

{

    BOOLEAN flag = TRUE;

    for (int i = ; i < length && flag; i++){

        flag = FALSE;

        for (int j = length - ; j > i; j--)

            if (*(p + j) < *(p + j - ))

            {

                swap(p + j, p + j - );

                flag = TRUE;

            }

    }

}

2.简单选择法：

主要思想：每轮循环找到一个最小数的标号，循环结束后进行一次交换。

演示效果：

C代码：

swap(int *p1, int *p2)

{

    int tmp;

    tmp = *p1;

    *p1 = *p2;

    *p2 = tmp;

}

Xsort(int *p, int length)

{

    for (int i = ; i < length - ; i++){

        int min = i;

        for (int j = i + ; j < length; j++){

            if (*(p + j) < *(p + min))

                min = j;

        }

        if (min != i)

            swap(p + i, p + min);

    }

}

3.直接插入法：

主要思想：每轮循环都是实现将一个新来的数插入到原有的一个有序子序列中。

演示效果：

C代码：

swap(int *p1, int *p2)

{

    int tmp;

    tmp = *p1;

    *p1 = *p2;

    *p2 = tmp;

}

Csort(int *p, int length)

{

    for (int i = ; i < length; i++){

        if (*(p + i) < *(p + i - )){

            int tmp = *(p + i);

            int j;

            for (j = i - ; j >=  && *(p + j) > tmp; j--)

                *(p + j + ) = *(p + j);

            *(p + j + ) = tmp;

        }

    }

}

4.快速排序法：

冒泡排序的升级版，同属于交换排序。

主要思想：通过递归，不断地二分序列，使相对较大的数位于一边，相对较小的数位于另一边。

演示效果：

C代码：

swap(int *p1, int *p2)

{

    int tmp;

    tmp = *p1;

    *p1 = *p2;

    *p2 = tmp;

}

int partition(int *p, int startIdx, int endIdx)

{

    int pivotkey;

    pivotkey = *(p + startIdx);

    while (startIdx < endIdx)

    {

        while (startIdx < endIdx && *(p + endIdx) >= pivotkey)

            endIdx--;

        swap(p + startIdx, p + endIdx);

        while (startIdx < endIdx && *(p + startIdx) <= pivotkey)

            startIdx++;

        swap(p + startIdx, p + endIdx);

    }

    return startIdx;

}

Ksort(int *p, int startIdx,int endIdx)

{

    int pivot;

    if (startIdx < endIdx)

    {

        pivot = partition(p,startIdx,endIdx);

        Ksort(p, startIdx, pivot - );

        Ksort(p, pivot + , endIdx);

    }

}

5.举例：

//2018-8-20

//by-lengwawa

#include<stdio.h>

#include<Windows.h>   //程序中的BOOLEAN在该头文件中定义

main()

{

    int n, i;

    int *p;

    p = NULL;

    printf("请输入需要排序的个数：");

    scanf_s("%d", &n);

    p = (int *)malloc(n*sizeof(int));

    printf("\n请输入%d个待排序的数：", n);

    for (int k = ; k < n; k++)

        scanf_s("%d", p + k);

    printf("\n你要使用哪种排序法(1——冒泡 2——选择 3——插入 4——快排)：");

    scanf_s("%d", &i);

    printf("\n");

    if (i == )

    {

        printf("使用冒泡排序法的结果是：");

        Msort(p, n);

        for (int j = ; j < n; j++)

            printf("%d ", *(p + j));

        printf("\n\n\n");

    }

    else if (i == )

    {

        printf("使用选择排序法的结果是：");

        Xsort(p, n);

        for (int j = ; j < n; j++)

            printf("%d ", *(p + j));

        printf("\n\n\n");

    }

    else if (i == )

    {

        printf("使用插入排序法的结果是：");

        Csort(p, n);

        for (int j = ; j < n; j++)

            printf("%d ", *(p + j));

        printf("\n\n\n");

    }

    else

    {

        printf("使用快速排序法的结果是：");

        Ksort(p, , n - );//这里是标号，所以是n-1

        for (int j = ; j < n; j++)

            printf("%d ", *(p + j));

        printf("\n\n\n");

    }

}