64.【冒泡排序与选择排序与malloc(）函数】

冒泡排序与选择排序

（一）、冒泡排序

1.什么是冒泡排序？

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

2.冒泡排序原理：

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。

而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

3.冒泡排序的优缺点

根据复杂度的规则，去掉低阶项（也就是 n/2）,并去掉常数系数，那复杂度就是 O(n^2)了；（高）

冒泡排序也是一种稳定排序，因为在两个数交换的时候，如果两个数相同，那么它们并不会因为算法中哪条语句相互交换位置。

4.实战项目：

代码展示：

#include<iostream>usingnamespace std;#include<string.h>intmain(){
    string s1;
    cin >> s1;for(int i =0; i < s1.length(); i++){for(int j =0; j < s1.length()- i -1; j++){if(s1[j]> s1[j +1]){int temp;
                temp = s1[j];
                s1[j]= s1[j +1];
                s1[j +1]= temp;}}}for(int i =0; i < s1.length(); i++){
        cout << s1[i]<<" ";}}

效果展示：

(二)、选择排序

1.什么是选择排序？

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

2.选择排序原理

基本思想：每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。

3.选择排序优缺点

选择排序是不稳定的排序方法。

4.实战项目：

代码展示：

#include<iostream>usingnamespace std;#include<string.h>intmain(){int min,i,j;
    string s1;
    cin >> s1;for( i =0; i < s1.length()-1; i++){
        min = i;//   假如说最小值是ifor( j = i +1; j < s1.length(); j++){if(s1[j]< s1[min])//目的为了寻找最小值{
                min = j;}}if(i != min)//   目的为了把最小值放在起始元素{int temp;
            temp = s1[i];
            s1[i]= s1[min];
            s1[min]= temp;}}for(int i =0; i < s1.length(); i++){
        cout << s1[i]<<" ";}}

效果展示：

(三)、malloc()函数

1.什么是malooc（）函数？

malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存，且分配的大小就是程序要求的大小。

2.malloc()函数的定义

其函数原型为*void *malloc(unsigned int size)；其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的返回值是分配区域的起始地址，或者说，此函数是一个指针型函数，返回的指针指向该分配域的开头位置。**
如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定)，否则返回空指针NULL。当内存不再使用时，*应使用free()函数将内存块释放**。函数返回的指针一定要适当对齐，使其可以用于任何数据对象。

3. malloc函数和new函数的区别

在使用上，malloc 和 new 至少有两个不同: new 返回指定类型的指针，并且可以自动计算所需要大小。而 malloc 则必须要由我们计算字节数，并且在返回后强行转换为实际类型的指针。另外有一点不能直接看出的区别是，malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。除了分配及最后释放的方法不一样以外，通过malloc或new得到指针，在其它操作上保持一致。

4.实战项目：

代码展示：

#include<iostream>usingnamespace std;#include<stdlib.h>#include<string.h>intmain(){int* p;
    cout <<"请输入你要输入的个数:"<< endl;int n;
    cin >> n;
    p =(int*)malloc(n*sizeof(int));//手动计算字节数if(p !=NULL)//必须要有，要不然会报警告{for(int i =0; i < n; i++){
            cout <<"请输入第"<< i +1<<"个数据"<< endl;
            cin >> p[i];}
        cout <<"您输入的数字为:"<< endl;for(int i =0; i < n; i++){
            cout << p[i]<<" "<< endl;}}free(p);//进行释放return0;}

效果展示：