冒泡排序的英文Bubble Sort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位,第二趟只能将倒数第 2 位上的数归位,依次类推下去。如果有 n 个数进行排序,只需将 n-1 个数归位,也就是要进行 n-1 趟操作。
而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较,将较大的数放后面,比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系,重复此步骤,直到最后一个还没归位的数。
根据复杂度的规则,去掉低阶项(也就是 n/2),并去掉常数系数,那复杂度就是 O(n^2)了;(高)
冒泡排序也是一种稳定排序,因为在两个数交换的时候,如果两个数相同,那么它们并不会因为算法中哪条语句相互交换位置。
#include
using namespace std;
#include
int main()
{
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] << " ";
}
}
选择排序是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。
基本思想:每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止。
选择排序是不稳定的排序方法。
#include
using namespace std;
#include
int main()
{
int min,i,j;
string s1;
cin >> s1;
for ( i = 0; i < s1.length()-1; i++)
{
min = i; // 假如说最小值是i
for ( 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的全称是memory allocation,中文叫动态内存分配,用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址,当无法知道内存具体位置的时候,想要绑定真正的内存空间,就需要用到动态的分配内存,且分配的大小就是程序要求的大小。
其函数原型为void *malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的返回值是分配区域的起始地址,或者说,此函数是一个指针型函数,返回的指针指向该分配域的开头位置。
如果分配成功则返回指向被分配内存的指针(此存储区中的初始值不确定),否则返回空指针NULL。当内存不再使用时,应使用free()函数将内存块释放。函数返回的指针一定要适当对齐,使其可以用于任何数据对象。
在使用上,malloc 和 new 至少有两个不同: new 返回指定类型的指针,并且可以自动计算所需要大小。而 malloc 则必须要由我们计算字节数,并且在返回后强行转换为实际类型的指针。另外有一点不能直接看出的区别是,malloc 只管分配内存,并不能对所得的内存进行初始化,所以得到的一片新内存中,其值将是随机的。除了分配及最后释放的方法不一样以外,通过malloc或new得到指针,在其它操作上保持一致。
#include
using namespace std;
#include
#include
int main()
{
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); //进行释放
return 0;
}