交换排序
交换排序的基本思想：
两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。
冒泡排序是基于简单交换思想而实现的。
冒泡排序
冒泡排序（Bubble Sort）是一种最简单的交换排序方法。
通过两两比较相邻的关键字，如果发生逆序，则进行交换，从而使关键字小的记录（值较小的）如气泡一般逐渐往上“漂浮”（左移），或者说是使关键字大的记录（值较大的）如石块一样逐渐向下“坠落”（右移）。
算法步骤：
① 设待排序序列存放在数组arr[0...n-1]中（n为待排序序列的长度）。首先将第一个数（arr[0]）和第二个数（arr[1]）进行比较，若为逆序（即arr[0]>arr[1]），则交换两个值。然后比较第二个数（arr[1]）和第三个数（arr[2]）……以此类推，直到第n-1个数（arr[n-2]）和第n个数（arr[n-1]）进行比较为止。
上述过程称作一趟冒泡排序，其结果使得值最大的数（假设为max）被放置到最后一个位置上去（即arr[n-1]=max）。
② 然后进行第二趟冒泡排序，对前n-1个数进行同样的操作（同①过程），其结果使得值次大的数被放置到第n-2个位置上去。
③ 重复上诉比较和交换过程，第i趟是从arr[0]到arr[n-i]依次比较相邻两个数的值，并在“逆序”时交换相邻的数，其结果是这n-i+1个记录中值最大的数被交换到第n-i+1的位置上。
直到在某一趟排序过程中没有进行过交换操作，说明序列已全部达到排序要求，则排序完成。
图文说明：
冒泡排序
实现代码：【C++版】
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int arr[200010];
// 冒泡排序
// O(N^2)
// arr[]：存储待排序序列的数组
// length：待排序序列的长度
void bubblesort(int arr[],int length)
{
int m=length-1;
int flag=1;
while(m>0 && flag==1)
{
flag=0;
for(int i=0;i<m;i++)
{
if(arr[i]>arr[i+1])
{
swap(arr[i],arr[i+1]);// 交换的过程
/*
int temp；
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=arr[i];
*/
flag=1;// 标记，表示在此趟排序过程中有值的交换
}
}
m--;// 减一
}
}
int main()
{
scanf("%d",&n);// 输入序列的长度n
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);// 输入待排序序列
}
bubblesort(arr,n);// 【冒泡排序】
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);// 输出排序好的序列
}
return 0；
}
运行结果
算法分析：
（1） 时间复杂度：
-
最好情况（初始序列为正序）：只需要进行一趟排序，在排序过程中进行n-1次值的比较，且不移动对应值的位置。
-
最坏情况（初始序列为逆序）：需进行n-1趟排序，总的值的比较次数KCN和对应值位置的移动次数RCN（每次交换都要移动3次位置）分别为：
KCN==
RCN==
所以，在平均情况下，冒泡排序的值的比较次数和位置移动次数分别约为和
，时间复杂度为
。
（2）空间复杂度：
冒泡排序只有在两个值交换位置时需要辅助空间用作暂存记录，所以空间复杂度为。
算法特点：
- 是稳定排序。
- 可用于顺序结构，也可用于链式存储结构。
- 移动位置次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。
选择排序
选择排序的基本思想：
每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的后面，直到全部排完为止。
下面我们将介绍一种简单选择排序方法。
简单选择排序
简单选择排序（Simple Selection Sort）也称为直接选择排序。
算法步骤：
① 设待排序的记录存放在数组arr[0...n-1]中。第一趟从arr[0]开始，通过n-1次比较，从n个记录中选出关键字（值）最小的记录（数组下标），记为arr[k]，交换arr[i]和arr[k]。
② 第二趟从arr[1]开始，通过n-2次循环，从n-1个记录中选出关键字（值）最小的记录（数组下标），记为arr[k]，交换arr[1]和arr[k]。
③ 以此类推，第i趟从arr[i-1]开始，通过n-i次比较，从n-i+1个记录中选出关键字（值）最小的记录（数组下标），记为arr[k]，交换arr[i-1]和arr[k]。
④ 经过n-1趟，排序完成。
图文说明：
简单选择排序
实现代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int arr[200010];
// 【简单选择排序】
// O(N^2)
// arr[]：存储待排序序列的数组
// length：待排序序列的长度
void selectsort(int arr[],int length)
{
int k;// 记录(数组下标)
// 在arr[0...length-1]中选择关键字(值)最小的记录(数组下标)
for(int i=0;i<length-1;i++)// length-i-1次循环
{
k=i;
for(int j=i+1;j<length;j++)// length-j次循环
{
if(arr[j]<arr[k])k=j;// k指向此趟排序中关键字(值)最小的记录(数组下标)
}
if(k!=i)
{
swap(arr[k],arr[i]);// 交换arr[i]和arr[k]
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
selectsort(arr,n);// 【简单选择排序】
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
算法分析：
（1）时间复杂度：
简单选择排序过程中，所需进行记录移动的次数较少。
- 最好情况（正序）：不移动。
- 最坏情况（逆序）：移动
次。
然而，无论记录的初始排序如何，所需进行的关键字间的比较次数相同，均为
=
=
因此，简单选择排序的时间复杂度也是。
（2）空间复杂度：
同冒泡排序一样，只有在两个记录交换时需要一个辅助空间，所以空间复杂度为。
算法特点：
- 就选择排序本身来讲，它是一种稳定的排序方法。但是，就程序中的简单选择排序，这是一种不稳定的排序（由于采用“交换记录”的策略造成的）。
- 可用于链式存储结构。
- 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。
写在最后
上述两种排序方法的时间复杂度均为，是最基础的两种排序方法，后面将逐步介绍一些更快、更高级的排序方法。
参考资料：
- 《数据结构(C语言版) (第2版)》严蔚敏
- 博客：https://www.cnblogs.com/chengxiao/p/6103002.html (部分图片来源)
- 博客：https://www.cnblogs.com/jingmoxukong/p/4303289.html (部分图片来源)
如有错误，欢迎指正。
网友评论