冒泡排序
一趟冒泡排序：
#include<bits/stdc++.h>
using namespace std;
int n , a[109];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n - 1; i++) //相邻的数进行比较
{
if(a[i] > a[i + 1])
swap(a[i] , a[i + 1]);
}
}
完整的冒泡排序分析过程：
一趟冒泡排序,只能确定最大值在合适的位置
第一趟： n-1
56 78 59 99 100
第二趟：n-2
56 78 59 99 100
56 59 78 99 100
下标n-1和n这个位置 还用不用比较？
完成的目标:又能确定一个数 在合适的位置
第三趟： n-3
56 59 78 99 100
....
一趟能够确定一个数，完成n个数的排序
需要几趟？n-1
可能提前完成排序，实际的趟数小于n-1趟
优化的点：bool 本次的交换swap没有进行
冒泡排序的代码1：
#include<bits/stdc++.h>
using namespace std;
int n , score[109];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> score[i];
//排序
for(int k = 1; k <= n - 1; k++) //趟数 n个数要进行n-1趟
{
for(int i = 1; i <= n - k; i++) //比较到n-k即可
{
if(score[i] > score[i + 1]) //升序 如果左边的大于右边的进行交换
swap(score[i] , score[i + 1]);
}
}
for(int i = 1; i <= n; i++)
cout << score[i] << " ";
}
冒泡排序的代码2(优化：提前退出循环)：
#include<bits/stdc++.h>
using namespace std;
int n , score[109];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> score[i];
//排序
for(int k = 1; k <= n - 1; k++) //趟数 n个数要进行n-1趟
{
bool check = false;
for(int i = 1; i <= n - k; i++) //比较到n-k即可
{
if(score[i] > score[i + 1]) //升序 如果左边的大于右边的进行交换
{
swap(score[i] , score[i + 1]);
check = true; //本趟 有交换
}
}
if(!check)
break;
}
for(int i = 1; i <= n; i++)
cout << score[i] << " ";
}
一趟选择排序：
#include<bits/stdc++.h>
using namespace std;
int n , score[109];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> score[i];
int mi = 1; //下标 假设最小值为score[1]
for(int i = 1; i <= n; i++)
{
if(score[mi] > score[i])
mi = i; //更新最小值的下标
}
swap(score[1] , score[mi]);
for(int i = 1; i <= n; i++)
cout << score[i] << " ";
return 0;
}
选择排序分析的过程：
第一趟结束：
最小值保留在：下标为1
1 5 6 3 2
第二趟：
最小值保留在：下标为2
1 2 6 3 5
第三趟：
最小值保留在：下标为3
1 2 3 6 5
...
一共需要n-1趟即可。
完整的选择排序的过程：
#include<bits/stdc++.h>
using namespace std;
int n , score[109];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> score[i];
for(int k = 1; k <= n - 1; k++) //n-1趟选择排序
{
int mi = k; //下标 假设最小值为score[k]
for(int j = k; j <= n; j++)
{
if(score[j] < score[mi])
mi = j;
}
swap(score[mi] , score[k]);
for(int i = 1; i <= n; i++)
cout << score[i] << " ";
cout << endl;
}
return 0;
}
sort排序
sort排序：
#include<algorithm>
int a[100];//下标从0开始
sort(a, a + n); //实现从小到大排序
//数组的名字+第一个数的下标 数组的名字+最后一个数的下标 + 1
int a[100]; //下标从1开始
sort(a + 1 , a + n + 1);
sort(a + 1 , a + n + 1 , greater<int>()); //从大到小
插入排序
【1】【3】【5】【6】 x =【2】
1】2【3】【5】【6】
把2插入到有序序列 {1 3 5 6}中：
【1】【2】【3】【5】【6】
把x插入序列a中：
cin >> x;
int j = n;
while(j >= 1 && a[j] > x)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
插入排序：n-1次(把剩余的n-1个数a2~an插入到序列中)
a1 | a2 .....an
每一次插入x，都是插入到有序序列中
插入前和插入后，序列都是有序的。
[a1] -> [a1 a2] -> [a1 a2 a3]....
34 | 2 1 100 0
[34] => [2 34] => [1 2 34] => [1 2 34 100] => [0 1 2 34 100]
int j = n;
while(j >= 1 && a[j] > x) //x待插入的数
{
a[j + 1] = a[j];
j--;
}
//结束条件 j==0 a[j] <=x
a[j + 1] = x;
for(int i = 2; i <= n; i++) //执行n-1次 表示插入排序的n-1趟
{
//a[1]~a[i-1]已经是有序的，现在要把a[i]插入到里面
int x = a[i] , j = i - 1;
while(j >= 1 && a[j] > x) //x待插入的数
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
