冒泡排序与选择排序（C++实现）
冒泡排序与选择排序
最近有练习C++/C的时候，顺便在看排序的问题，就想到了大学时学习的冒泡排序与选择排序。下面简单的介绍下两种排序并总结下各自的优缺点。
冒泡排序
冒泡排序是计算机科学领域中一种常用且简单的排序方法，其排序的方法是重复遍历所有需要排序的数字，逐个相邻的两个元素相互比较，只要满足排序的大小条件，就相互交换两个元素，直到所有的元素满足排序要求。
选择排序
选择排序是一种非常直观的排序方法，其具体的思想是给定一组需要排序的数组，从该数组中选择一个最小(最大)的数字放在最前或者最后的位置，再从剩下的数字中选择一个最小(最大)的数字放在次前或者次后的位置，依次这样选择排序，直到所有的元素满足排序要求。
两种排序的区别与优缺点
区别 （1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值； （2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置； （3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；
优缺点 冒泡排序： 优点: 比较简单，空间复杂度较低，是稳定的； 缺点: 时间复杂度太高，效率慢；
选择排序： 优点: 一轮比较只需要换一次位置； 缺点: 效率慢，不稳定（举个例子5，8，5，2，9 我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）。
代码
1、冒泡排序
// An highlighted block
#include <iostream>
#include <cmath>
using namespace std;
int i,j,len;
long arr[] = {
12, 25, 546, 1, 235, 57, 47, 25, 253};
long k = 0;
void Bubble_Aort();
void Pri();
int main()
{
len = sizeof(arr)/sizeof(arr[0]);
cout << "***Bubble Sort***" << endl;
cout << "Array before sorting:" << endl;
Pri();
cout << "Sorted array:"<< endl;
Bubble_Aort();
Pri();
cout << "Hello, world!" << endl;
return 0;
}
void Bubble_Aort()
{
for(i = 0; i < len; i++)
{
for(j = len-1; j > i; j--)
{
if(arr[j-1] > arr[j])
{
k = arr[j];
arr[j] = arr[j-1];
arr[j-1] = k;
}
}
}
}
void Pri()
{
for(i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
运行结果
// An highlighted block ***Bubble Sort*** Array before sorting: 12 25 546 1 235 57 47 25 253 Sorted array: 1 12 25 25 47 57 235 253 546 Hello, world!
2、选择排序
// An highlighted block
#include <iostream>
#include <cmath>
using namespace std;
int i,j,len;
long arr[] = {
12, 25, 546, 1, 235, 57, 47, 25, 253};
long k = 0;
void Choose_Aort();
void Pri();
int main()
{
len = sizeof(arr)/sizeof(arr[0]);
cout << "***Choose Sort***" << endl;
cout << "Array before sorting:" << endl;
Pri();
cout << "Sorted array:"<< endl;
Choose_Aort();
Pri();
cout << "Hello, world!" << endl;
return 0;
}
void Choose_Aort()
{
for(i=0;i<len;i++)
{
for(j=i;j<len;j++)
{
if(arr[i]>arr[j])
{
k=arr[j];
arr[j]=arr[i];
arr[i]=k;
}
}
}
}
void Pri()
{
for(i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
运行结果
// An highlighted block ***Choose Sort*** Array before sorting: 12 25 546 1 235 57 47 25 253 Sorted array: 1 12 25 25 47 57 235 253 546 Hello, world!