C/C++常用算法系列一、排序算法

程序员小涛

发布于 2020-12-03 11:44:14

3120

发布于 2020-12-03 11:44:14

文章被收录于专栏：涛的程序人生

C/C++常用算法系列文章目录

一、排序算法.

排序算法

在各类算法问题中，排序算法是最基本的一个问题。现实生活中很多方面都需要将一些数据按照一定的顺序进行排列。对于一个排好序的序列来说，在进行查找最大值、最小值、遍历、计算和求解等各种操作时都很方便。

1.冒泡排序

冒泡排序（Bubble Sort）是所有排序算法中最简单、最基本的一种。其思路就是交换排序，通过相邻数据的比较交换来达到排序的目的。

1.1冒泡排序算法示例

代码如下（对包含10个数字的整型数组进行排序）：

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

#define SIZE 10

//冒泡排序算法
void BubbleSort(int *a, int length)
{
    int i, j, k, temp;

    for(i = 0; i < length - 1; i++)
    {
        for(j = length - 1; j > i; j--)
        {
            if(a[j-1] > a[j])
            {
                temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
        printf("第%d步排序结果:", i);
        for(k = 0; k < length; k++)
        {
            printf("%d ", a[k]);
        }
        printf("\n");
    }
}

int main()
{
    int array[SIZE], i;

    srand(time(NULL));    //随机数种子
    for(i = 0; i < SIZE; i++)
    {
        array[i] = rand() / 1000 + 100;   //初始化数组
    }

    printf("排序前的数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    BubbleSort(array, SIZE);

    printf("排序后的数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

1.2运行结果

2.选择排序

选择排序（Selection Sort）也是比较简单的排序算法。思路比较直观<选择排序算法在每一步中选取最小值来重新排序，从而达到排序的目的。

2.1选择排序算法示例

代码如下（对包含10个数字的整型数组进行排序）：

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

#define SIZE 10

void SelectionSort(int *a, int length)
{
    int i, j, k, h;
    int temp;

    for(i = 0; i < length - 1; i++)
    {
        k = i;
        for(j = i + 1; j < length; j++)
        {
            if(a[j] < a[k])
            {
                k = j;
            }
        }
        if(k != i)
        {
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }

        printf("第%d步排序结果: ", i);
        for(h = 0; h < length; h++)
        {
            printf("%d ", a[h]);
        }
        printf("\n");
    }
}

int main()
{
    int i;
    int arr[SIZE];

    srand(time(NULL));
    for(i = 0; i < SIZE; i++)
    {
        arr[i] = rand() / 1000 +100;
    }
    printf("排序前数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    SelectionSort(arr, SIZE);

    printf("排序后数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

2.2运行结果

3.插入排序

插入排序（Insertion Sort）通过对未排序的数据逐个插入合适的位置来完成排序工作。插入排序算法的思路也比较简单，使用的也比较多。

3.1插入排序算法示例

代码如下（对包含10个数字的整型数组进行排序）：

3.2运行结果

4.希尔排序

前面介绍的冒泡排序、选择排序和插入排序算法的思路都比较直观，但是排序的效率都比较低。对于遇到大量的数据需要排序时，往往需要寻求其他更为高效的排序算法，希尔排序（Shell Sort）便是其中一种。

4.1希尔排序算法示例

代码如下（对包含10个数字的整型数组进行排序）：

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

#define SIZE 10

void ShellSort(int *a, int length)
{
    int i, j, h;
    int r, temp;
    int x = 0;

    for(r = length/2; r >= 1; r /= 2)
    {
        for(i = r; i < length; i++)
        {
            temp = a[i];
            j = i - r;
            while(j >= 0 && temp < a[j])
            {
                a[j + r] = a[j];
                j -= r;
            }
            a[j + r] = temp;
        }
        x++;
        printf("第%d步排序结果: ", x);
        for(h = 0; h < length; h++)
        {
            printf("%d ", a[h]);
        }
        printf("\n");
    }
}

int main()
{
    int i;
    int arr[SIZE];

    srand(time(NULL));
    for(i = 0; i < SIZE; i++)
    {
        arr[i] = rand() / 1000 +100;
    }
    printf("排序前数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    ShellSort(arr, SIZE);

    printf("排序后数组为: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

4.2运行结果

5.堆排序

堆排序（Heap Sort）是基于选择排序思想，利用堆结构和二叉树的一些性质来完成数据的排序。堆排序算法在一些场合具有很广泛的应用。

5.1堆排序算法示例

代码如下（对包含10个数字的整型数组进行排序）：

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

#define SIZE 10

void HeapSort(int a[], int n)
{
    int i, j, h, k;
    int t;

    for(i = n / 2 - 1; i >= 0; i--)  //将a[0,n-1]建成大根堆
    {
        while(2 * i + 1 < n)  //第i个结点有右子树
        {
            j = 2 * i + 1;
            if((j + 1) < n){
                if(a[j] < a[j+1]){
                    j++;
                }
            }
            if(a[i] < a[j]){
                t = a[i];
                a[i] = a[j];
                a[j] = t;
                i = j;
            } else {
                break;
            }
        }
    }

    //输出构成的堆
    printf("原始数据构成的堆: \n");
    for(h = 0; h < n; h++)
    {
        printf("%d ", a[h]);
    }
    printf("\n");

    for(i = n - 1; i > 0; i--)
    {
        t = a[0];
        a[0] = a[i];
        a[i] = t;
        k = 0;
        while(2 * k + 1 < i)
        {
            j = 2 * k + 1;
            if((j + 1) < i)
            {
                if(a[j] < a[j+1])
                {
                    j++;
                }
            }
            if(a[k] < a[j])
            {
                t= a[k];
                a[k] = a[j];
                a[j] = t;
                k = j;
            } else {
                break;
            }
        }
        printf("第%d步排序结果: ", n - i);
        for(h = 0; h < n; h++)
        {
            printf("%d ", a[h]);
        }
        printf("\n");
    }
}

int main()
{
    int i;
    int arr[SIZE];

    srand(time(NULL));
    for(i = 0; i < SIZE; i++)
    {
        arr[i] = rand() / 1000 + 100;
    }

    printf("排序前: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    HeapSort(arr, SIZE);

    printf("排序后: \n");
    for(i = 0; i < SIZE; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

5.2运行结果

总结

提示：未完待续。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/11/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度