网硕互联帮助中心排序
排序 — 将数据按照 从大到小(降序) 或者 从小到大(升序) 排列
C语言中:
选择排序
冒泡排序
插入排序
//快速排序
统一规定: 升序
掌握的标准:
一.选择排序
思想
给合适的位置选择合适的数
for(i =0;i< n-1;++i)
{ //初始从0开始和后面对比，最后一位不需要交换
for(j =i+1;j<n;++j)
{ //依次拿后面的数来和第一位对比
if(a[j]<a[i])
{
c=a[i];
a[i] =a[j];
a[j]=c; //如果后面的值更小，就交换
}
} //循环过这个，就会确定i值的最小值。然后退出此循环，i++
}
二.冒泡排序
思想
相邻两个元素，两两比较
小的放前，大的放后
for(i=1;i<n;++i)
{ //循环的趟数，n-1趟
for(j=0;j<n-i;++j)
{ //对每个数字进行比较
if(a[j]>a[j+1] ) //与后面一位比较，如果后面的值更小，就交换，实现大数字的后移
{
c=a[j];
a[j]=a[j+1];
a[j+1]=c;
}
} //此循环结束，最后一位数字即为最大的数
} //n-1此循环完后，第一值肯定为最小值，所以不需循环
三.插入排序
//空间
插入排序:
基本思想
找到合适的位置 进行插入
原地插入
int key;
for(i=1;i<n;i++)
{ //从第二位数开始（第一位不用调整，直接给入）
key=a[i]; // 暂存为key
j=i-1; //j=i-1即为输入的数字的前一位的位置,a[j]为前一位，而a[j+]即a[i]才为目的位置
while(j>=0&&a[j]>key) //倘若j>=0，即前面还有数字，并且前一位数字大于输入数字
{ // 则将前一位的位置空出来，前一位数的数字后移一位
a[j+1]=a[j]; //j+1即为后一位
j–; //位置再次前移
} //此循环结束时，将会给输入数字找到适合的位置，即前面的都比输入数字小，而后面的都更大
a[j+1]=key; //此时即可赋值，完成输入数字的插入
}
非原地插入
int b[n];
for(i= 0;i<n;++i)
{
j=i;
while(j> 0 && a[i] < b[j-1])
{
b[j] = b[j-1];
–j;
}
b[j] = a[i];
}
四.排序算法性能
时间
for (i = 0; i < n-1; ++i)
{
for (j = i+1; j < n; ++j)
{
if (a[j] < a[i])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
i = 0 n-1
i = 1 n-2
i = 2 n-3
……
i = n-2 1
1 2 3 … n-1
n(n-1)/2
n^2/2 – n/2
O(n^2) //大O记法
for (i = n-1; i > 0; –i) //趟数
{
for (j = 0;j < i; ++j)//一趟过程
{
if (a[j] > a[j+1])
{
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
i = n-1 n-1
i = n-2 n-2
i = n-3 n-3
…
i = 1 1
1 2 3 4 … n-1
五.数组
1. 透视一维数组:
数据类型
int a[10]; //整型的一维数组
//数组也是一种数据类型
2. 数组的类型
方法:
去掉标识符 剩下就是对应的数据雷系
int [10] //数组类型 — 表示这是一个数组 —是一个能够存放10个int型数据的数组
int [20]
int[10] a; //理解的角度 这样没问题 —c语法不支持写成这样
3.数组名
数组名
printf ("sizeof(a) = %ld \\n", sizeof(a)); //
1.数组名 –代表数组 //从数据类型的角度看 –数组名 —代表数组这种类型
2.数组名 –代表数组首元素的地址 //从值的角度看 — 数组名 代表数组首元素的地址
3.数组名代表数组首元素的地址 参与到运算中 ，用的其实是这个值
数组名 是个常量
//可变长数组
int a[n]; //c99 标准后，数组长度可以是个变量
注意:
int a[n]; //要求: 不能初始化
六·.查找
查找的算法
二分查找
eg:
1 ~ 10
V
1 2 3 4 5 6 7 8 9 10
前提:
数据，必须是有序的
七.字符型一维数组
字符型一维数组 —- 处理 字符串 数据的
int a[10];
char s[10]; //字符这种数据
主要用途—用来存放字符串数据
"hello" //字符串常量
"hello" //整体的含义 — 字符串 — 一串字符
字符串 是一种特殊的字符型一维数组
char s[10] = {'h','e','l','l','o'};
char s[10] = {'h','e','l','l','o','\\0'};
数组特点:
1.连续性
2.单一性
3.有序性
字符串 特殊在 —它始终有一个 结束标志 '\\0'
"hello" —内存中示意–> 'h','e','l','l','o','\\0'
char s[10] = "hello";
puts();
int puts(const char *s);
功能:
输出一个字符串
参数:
@s — 需要的是一个字符串的首地址
//传 字符型数组的数组名 即可
// "hello"
返回值:
成功 非负数
失败 -1
输出效果默认 带有 换行
gets
char *gets(char *s);
功能:
从键盘标准输入获得字符串
参数:
@s 表示存放字符串数据的一块空间的起始地址
返回值:
成功 s
失败 NULL
注意:
gets 很容易导致数组越界 带来 栈奔溃
scanf 也可以输入字符串 ，但是不能输入带 空格字符串
scanf 也会导致数组越界 带来 栈奔溃
八.练习
1.输入一个字符串 计算字符串的长度
int a[10]; //数组长度 — 10
字符串长度
"hello" // 'h''e''l''l''o''\\0'
2.输入一个字符串, 实现字符串的逆序
char s[10] = "hello";
"hello"
"olleh"
评论前必须登录！
注册