46.冒泡排序

编程语言 > CPP > CPP基础 > CPP基础语法知识 排序 编程语言 CPP CPP基础 CPP基础语法知识
发布时间 :
字数:3k 阅读 : 评论:
  1. 46.排序-冒泡排序
    1. 46.1 知识点
      1. 排序的基本概念
      2. 冒泡排序基本原理
      3. 代码实现
        1. 比较两两相邻的数
        2. 换 m 轮
        3. 优化
      4. 总结
        1. 基本概念
        2. 套路写法
        3. 优化策略
    2. 46.2 知识点代码
      1. Lesson46_排序_冒泡排序.cpp
    3. 46.3 练习题
      1. 定义一个数组，长度为20，每个元素值随机0~100的数
      2. 写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序
    4. 46.4 练习题代码
      1. Lesson46_练习题.cpp

46.排序-冒泡排序

46.1 知识点

排序的基本概念

排序是计算机中经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。常见的排序例子包括：

无序序列：
8 7 1 5 4 2 6 3 9

排序后的有序序列（升序）：
1 2 3 4 5 6 7 8 9

排序后的有序序列（降序）：
9 8 7 6 5 4 3 2 1

在程序中，序列通常存储在数组中，所以排序往往是对数组进行排序。其目的是将数组里面的内容变为有序的。

冒泡排序基本原理

考虑以下无序序列：
8 7 1 5 4 2 6 3 9

冒泡排序通过不断比较相邻的元素来完成排序。具体流程如下：

  • 两两相邻元素进行比较。
  • 不停地交换相邻元素。
  • 比较 n 轮。

代码实现

假设我们有一个数组：

int arr[] = { 8, 7, 1, 5, 4, 2, 6, 3, 9 };

比较两两相邻的数

我们首先比较第 n 个和第 n+1 个数的大小。为了避免越界，我们需要将数组的长度减去 1。

for (int n = 0; n < sizeof(arr)/sizeof(int) - 1; n++)
{
    if (arr[n] > arr[n + 1])
    {
        // 交换两个数
        int temp = arr[n];
        arr[n] = arr[n + 1];
        arr[n + 1] = temp;
    }
}

换 m 轮

有几个数，就比较多少轮。

for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
{
    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1; n++)
    {
        if (arr[n] > arr[n + 1])
        {
            // 交换两个数
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
}

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
    cout << arr[i] << ",";
}
cout << endl;

优化

  1. 确定位置的数字不再参与比较。
    一轮排序后，极值（最大或最小值）已经放到了正确的位置上，因此不需要再比较。
for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
{
    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
    {
        if (arr[n] > arr[n + 1])
        {
            // 交换两个数
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
        }
    }
}

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
    cout << arr[i] << ",";
}
cout << endl;
  1. 特殊情况的优化
    如果已经提前完成排序，就不再进行比较，直接结束循环。如果一轮没有交换元素，说明序列已经是目标序列。
bool isSort = false;
for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
{
    isSort = false;  // 每一轮开始时，将标识设置为 false
    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
    {
        if (arr[n] > arr[n + 1])
        {
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;
            isSort = true;  // 如果进行了交换，标识设置为 true
        }
    }
    if (!isSort)  // 如果没有交换元素，说明已排序完成
        break;
}

for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
    cout << arr[i] << ",";
}
cout << endl;

总结

基本概念

  • 两两相邻元素进行比较。
  • 不停比较，不停交换。
  • 比较 m 轮。

套路写法

  • 外层循环控制轮数。
  • 内层循环进行元素比较和交换。

优化策略

  1. 已确定位置的数字不再参与比较。
  2. 使用 bool 变量标识是否进行了交换。

46.2 知识点代码

Lesson46_排序_冒泡排序.cpp

#include <iostream>
using namespace std;
int main()
{
    std::cout << "冒泡排序\n";

    #pragma region 知识点一 排序的基本概念

    //排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列
    //常用的排序例子
    // 8 7 1 5 4 2 6 3 9
    // 把上面的这个无序序列 变为 有序（升序或降序）序列的过程
    // 1 2 3 4 5 6 7 8 9 （升序）
    // 9 8 7 6 5 4 3 2 1 （降序）

    //在程序中 序列一般 存储在数组当中
    //所以 排序往往是对 数组进行排序
    
    //把数组里面的内容变为有序的

    #pragma endregion

    #pragma region 知识点二 冒泡排序基本原理

    // 8 7 1 5 4 2 6 3 9
    // 两两相邻
    // 不停比较
    // 不停交换
    // 比较n轮

    #pragma endregion

    #pragma region 知识点三 代码实现

    int arr[] = { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
    //第一步 如何比较数组中两两相邻的数
    //比较第n个和第n+1个数的大小
    //我们比较的是n 和 n+1 因此 长度应该-1 避免越界
    //for (int n = 0; n < sizeof(arr)/sizeof(int) - 1; n++)
    //{
    //    if (arr[n] > arr[n + 1])
    //    {
    //        //第二步 满足条件的话 就去交换两个数
    //        //中间商不赚差价
    //        int temp = arr[n];
    //        arr[n] = arr[n + 1];
    //        arr[n + 1] = temp;
    //    }
    //}

    //第三步 如何换m轮
    //有几个数 就比较多少轮
    //for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
    //{
    //    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1; n++)
    //    {
    //        if (arr[n] > arr[n + 1])
    //        {
    //            //第二步 满足条件的话 就去交换两个数
    //            //中间商不赚差价
    //            int temp = arr[n];
    //            arr[n] = arr[n + 1];
    //            arr[n + 1] = temp;
    //        }
    //    }
    //}

    //for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    //{
    //    cout << arr[i] << ",";
    //}
    //cout << endl;

    //第四步 优化
    //1.确定位置的数字 不用在比较了
    //  确定了一轮后 极值（最大或者最小值）已经放到了对应的位置上了（往后放）
    //  所以 没完成n轮后 后面位置的数 就没有必要再参与比较了
    //for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
    //{
    //    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
    //    {
    //        if (arr[n] > arr[n + 1])
    //        {
    //            //第二步 满足条件的话 就去交换两个数
    //            //中间商不赚差价
    //            int temp = arr[n];
    //            arr[n] = arr[n + 1];
    //            arr[n + 1] = temp;
    //        }
    //    }
    //}

    //for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    //{
    //    cout << arr[i] << ",";
    //}
    //cout << endl;

    //2.特殊情况的优化
    //如果已经提前完成排序了，就应该不比了，就直接结束即可
    //如果发现比较一轮下来，没有再次进行两个数的交换 那就证明已经是目标序列了

    //每一轮是否进行了排序的标识
    bool isSort = false;
    for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
    {
        //每一轮开始 就将标识改为false 表示没有进行交换
        isSort = false;
        for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
        {
            //如果for循环一轮 都没有进入两个值的交换  那就证明已经达到目的了
            if (arr[n] > arr[n + 1])
            {
                //第二步 满足条件的话 就去交换两个数
                //中间商不赚差价
                int temp = arr[n];
                arr[n] = arr[n + 1];
                arr[n + 1] = temp;
                //进行了两个值的交换
                isSort = true;
            }
        }
        //如果isSort是false 那就证明一轮结束后 没有数产生交换
        //意味着 序列已经是目标序列了 就不用再进行下一轮比较了
        //这时 就停止比较了 跳出循环
        if (!isSort)
            break;
    }

    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        cout << arr[i] << ",";
    }
    cout << endl;

    #pragma endregion

}

#pragma region 总结

//基本概念
//两两相邻
//不停比较
//不停交换
//比较m轮

//套路写法
//两层循环
//外层轮数
//内层比较
//满足交换

//如果优化
//1.比过不比
//2.加入bool

#pragma endregion

46.3 练习题

定义一个数组，长度为20，每个元素值随机0~100的数

使用冒泡排序进行升序排序并打印
使用冒泡排序进行降序排序并打印

int arr[20];
for (int i = 0; i < 20; i++)
{
    arr[i] = getRandom(0, 100);
    cout << arr[i] << " ";
}
cout << endl;

bool isSort = false;
for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
{
    isSort = false;
    // 每一轮
    for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
    {
        // 升序 判断 大的放后面
        if (arr[n] < arr[n + 1])
        {
            int temp = arr[n];
            arr[n] = arr[n + 1];
            arr[n + 1] = temp;

            isSort = true;
        }
    }
    // 如果一轮结束都没有进行值的交换 证明已经是目标序列了
    if (!isSort)
        break;
}

for (int i = 0; i < 20; i++)
{
    cout << arr[i] << " ";
}
cout << endl;

写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序

void sort(int array[], int size, bool isAscendingOrder)
{
    bool order = false; // 满足条件才会去交换值
    int temp;
    for (int m = 0; m < size; m++)
    {
        for (int n = 0; n < size - 1 - m; n++)
        {
            // 根据传入的升序降序类型 决定使用什么规则 然后返回一个bool值 来决定是否交换位置
            order = isAscendingOrder ? array[n] > array[n + 1] : array[n] < array[n + 1];
            if (order)
            {
                temp = array[n];
                array[n] = array[n + 1];
                array[n + 1] = temp;
            }
        }
    }
}

// 利用函数指针来进行制作
void sort2(int array[], int size, bool (*func)(int,int))
{
    bool order = false; // 满足条件才会去交换值
    int temp;
    for (int m = 0; m < size; m++)
    {
        for (int n = 0; n < size - 1 - m; n++)
        {
            // 根据传入的升序降序类型 决定使用什么规则 然后返回一个bool值 来决定是否交换位置
            if (func(array[n], array[n + 1]))
            {
                temp = array[n];
                array[n] = array[n + 1];
                array[n + 1] = temp;
            }
        }
    }
}

bool maxSort(int a, int b)
{
    return a > b;
}

bool minSort(int a, int b)
{
    return a < b;
}

int arr2[] = {3,7,2,1,9,8,6,5,4};

// sort(arr2, 9, false);
sort2(arr2, 9, minSort);

for (int i = 0; i < 9; i++)
{
    cout << arr2[i] << " ";
}

46.4 练习题代码

Lesson46_练习题.cpp

#include <iostream>
#include "CustomConsole.h"
using namespace std;

void sort(int array[], int size, bool isAscendingOrder);
bool maxSort(int a, int b);
bool minSort(int a, int b);
void sort2(int array[], int size, bool (*func)(int, int));

int main()
{
    std::cout << "冒泡排序 练习题\n";

    #pragma region 练习题一

    /*定义一个数组，长度为20，每个元素值随机0~100的数
    使用冒泡排序进行升序排序并打印
    使用冒泡排序进行降序排序并打印*/

    int arr[20];
    for (int i = 0; i < 20; i++)
    {
        arr[i] = getRandom(0, 100);
        cout << arr[i] << " ";
    }
    cout << endl;

    bool isSort = false;
    for (int m = 0; m < sizeof(arr) / sizeof(int); m++)
    {
        isSort = false;
        //每一轮
        for (int n = 0; n < sizeof(arr) / sizeof(int) - 1 - m; n++)
        {
            //升序 判断 大的放后面
            if (arr[n] < arr[n + 1])
            {
                int temp = arr[n];
                arr[n] = arr[n + 1];
                arr[n + 1] = temp;

                isSort = true;
            }
        }
        //如果一轮结束都没有进行值的交换 证明已经是目标序列了
        if (!isSort)
            break;
    }

    for (int i = 0; i < 20; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    #pragma endregion

    #pragma region 练习题二

    //写一个函数，实现一个数组的排序，并返回结果。可以根据参数决定是升序还是降序

    int arr2[] = {3,7,2,1,9,8,6,5,4};

    //sort(arr2, 9, false);
    sort2(arr2, 9, minSort);

    for (int i = 0; i < 9; i++)
    {
        cout << arr2[i] << " ";
    }

    #pragma endregion

}

#pragma region 练习题二

void sort(int array[], int size, bool isAscendingOrder)
{
    bool order = false;//满足条件才会去交换值
    int temp;
    for (int m = 0; m < size; m++)
    {
        for (int n = 0; n < size - 1 - m; n++)
        {
            //根据传入的升序降序类型 决定使用什么规则 然后返回一个bool值 来决定是否交换位置
            order = isAscendingOrder ? array[n] > array[n + 1] : array[n] < array[n + 1];
            if (order)
            {
                temp = array[n];
                array[n] = array[n + 1];
                array[n + 1] = temp;
            }

        }
    }
}
//利用函数指针来进行制作
void sort2(int array[], int size, bool (*func)(int,int))
{
    bool order = false;//满足条件才会去交换值
    int temp;
    for (int m = 0; m < size; m++)
    {
        for (int n = 0; n < size - 1 - m; n++)
        {
            //根据传入的升序降序类型 决定使用什么规则 然后返回一个bool值 来决定是否交换位置
            if (func(array[n], array[n + 1]))
            {
                temp = array[n];
                array[n] = array[n + 1];
                array[n + 1] = temp;
            }
        }
    }
}

bool maxSort(int a, int b)
{
    return a > b;
}

bool minSort(int a, int b)
{
    return a < b;
}

#pragma endregion
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏