冒泡排序
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字
的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的
顶端，所以这个算法才被称为“冒泡排序”。
- 比较相邻元素， 如果第一个比第二个大， 就交换他们两个
- 对每一对相邻的元素做同样的工作， 执行完毕后， 找到第一个最大值
- 重复以上步骤， 每次比较 次数 - 1， 直到不需要比较
image
image
image
image
image
image
image
image
一层循环
#include <iostream>
using namespace std;
int main(){
int arr[] = {5,9,3,1,2,8,4,7,6};
int len = sizeof(arr)/sizeof(arr[0]);
for (int j = len-1 ; j > 0 ; --j) {
if (arr[j-1] > arr[j]){
// 交换
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 1 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 2 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 3 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 4 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 5 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 7 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
for (int j = len-1 ; j > 7 ; --j) {
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
}
右侧开始两层循环版本
#include <iostream>
using namespace std;
int main(){
int arr[] = {5,9,3,1,2,8,4,7,6};
int len = sizeof(arr)/sizeof(arr[0]);
int count =0;
for (int i = 0; i < len-1; ++i) {
for (int j = len-1 ; j > i ; --j) {
count++;
if (arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<count<<endl;
}
左侧开始版本
#include <iostream>
using namespace std;
int main(){
int arr[] = {5,9,3,1,2,8,4,7,6};
int len = sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i < len-1; ++i) {
for (int j = 0; j < len -1 ; ++j) {
if (arr[j] > arr[j+1]){
int temp = arr[j]; arr[j] = arr[j+1];arr[j+1]=temp;
}
}
}
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
}
选择排序（Selection-Sort）
先把最小的拿出来
剩下的， 再把最小的拿出来
剩下的， 再把最小的拿出来
。。。
每次选择还没处理的元素里最小的元素
选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。
比如: 对数字1~9进行排序。 使用线性查找在数据中寻找最小值，于是我们找到了最小值 1
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
一层版
#include <iostream>
using namespace std;
int main(){
int arr[] = {6, 1, 7, 8, 9, 3, 5, 4, 2};
int len = sizeof(arr)/sizeof(arr[0]);
int minIndex = 0;
for (int j = 0; j < len; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
cout<<"minIndex = "<< minIndex <<endl;
// 交换
int temp = arr[0];
arr[0] = arr[minIndex];
arr[minIndex] = temp;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
cout<<"-------------------------------"<<endl;
minIndex = 1;
for (int j = 1; j < len; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
cout<<"minIndex = "<< minIndex <<endl;
// 交换
temp = arr[1];
arr[1] = arr[minIndex];
arr[minIndex] = temp;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
cout<<"-------------------------------"<<endl;
minIndex = 2;
for (int j = 2; j < len; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
cout<<"minIndex = "<< minIndex <<endl;
// 交换
temp = arr[2];
arr[2] = arr[minIndex];
arr[minIndex] = temp;
for (int i = 0; i < len; ++i)
cout<<arr[i]<<"\t";
cout<<endl;
cout<<"-------------------------------"<<endl;
cout<<"-------------------------------"<<endl;
}
最终版
#include <iostream>
using namespace std;
int main() {
int arr[] = {6, 1, 7, 8, 9, 3, 5, 4, 2};
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; ++i) {
int minIndex = i;
for (int j = i; j < len; ++j) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
for (int i = 0; i < len; ++i)
cout << arr[i] << "\t";
cout << endl;
}
网友评论