©一颗斯特拉
参考资料：《C++数据结构与算法》（第4版）
题目：分别采用以下3种排序方法，对数组[5,2,3,8,1]按升序排序。
【选择排序】
include<iostream>
using namespace std;
void selection(int *num,int n ) {
int i, j, least, temp;
for (i = 0; i < n; i++) {
least = i;
for (j = i + 1; j < n; j++)
if (num[j] < num[least])
least = j;
if (least != i)
swap(num[j - 1], num[j]);
}
int main() {
int num[5] = {5, 2, 3, 8, 1};
selection(num, 5);
for (int i = 0; i < 5; i++)
cout << num[i];
}
【冒泡排序】
#include<iostream>
using namespace std;
//从前往后冒
void bubblesortFromhead(int *num,int n ) {
int i, j, temp;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++)//最大的放在最后一个
if (num[j + 1] < num[j])//谁小谁往前
swap(num[j], num[j + 1]);
}
int main(){
int num[5]={5,2,3,8,1};
bubblesortFromhead(num,5);
for(int i=0;i<5;i++)
cout << num[i];
}
#include<iostream>
using namespace std;
//从后往前冒
void bubblesortFromback(int *num,int n ) {
int i, j, temp;
for (i = 0; i < n - 1; i++)
for (j = n - 1; j > i; j--)
if (num[j - 1] > num[j]) {
swap(num[j-1],num[j]);
}
}
int main(){
int num[5]={5,2,3,8,1};
bubblesortFromback(num,5);
for(int i=0;i<5;i++)
cout << num[i];
}
【插入排序】
#include<iostream>
using namespace std;
void insertionsort(int *num,int n ) {
int i, j, temp;
for (i = 1; i < n ; i++) {
temp = num[i];
for (j = i; j > 0 && temp < num[j - 1]; j--) {//到0位置或前面小停止
num[j] = num[j - 1];
num[j-1] = temp;
}
}
}
int main(){
int num[5]={5,2,3,8,1};
insertionsort(num,5);
for(int i=0;i<5;i++)
cout << num[i];
}
1.选择排序
选择排序就是先找到位置不合适的元素，再把它放在其最终的合适位置上，很明确地直接交换数组元素。
（1）算法
如N个数升序排列:
step1：0到N-1位置找最小值（注意是找到最小的再交换，不是找到了小的就交换）和第0位置交换。
step2：1到N-1位置找最小值，和第1位置交换。
···
stepN-1：N-2到N-1位置找最小值，和第N-2位置交换。
伪代码如下：
selectionsort(data[],n)
for i=0 到 n-2//n-2s是最后一个i值，因为如果除最后一个元素之外的所有元素都放在合适的位置上，那么第n个元素（位于n-1位置上）就一定是最大的
找出元素data[i],…,data[n-1]中的最小元素;
将其与data[i]交换;
（2）复杂度
时间复杂度：
额外空间复杂度：
（3）优缺点
优点：赋值次数少。这次其它算法无法比拟的。
2.冒泡排序
（1）算法
如N个数升序排列:
①从前往后冒泡
round1
step1：0到1位置哪个大，谁跑后面去。
step2：1到2位置哪个大，谁跑后面去。
···
stepN-1：N-2到N-1位置哪个大，谁跑后面去。
round2
step1：0到1位置哪个大，谁跑后面去。
step2：1到2位置哪个大，谁跑后面去。
···
stepN-2：N-3到N-2位置哪个大，谁跑后面去。
······
roundN-1
step1：0到1位置哪个大，谁跑后面去。
伪代码如下：
bubblesort(data[],n)
for i=0 到 n-2
for j=0 往上到 n-2-i
如果两者逆序，则交换位置j和位置j-1的元素
②从后往前冒泡
round1
step1：N-1到N-2位置哪个小，谁跑前面去。
step2：N-2到N-3位置哪个小，谁跑前面去。
···
stepN-1：1到0位置哪个小，谁跑前前去。
round2
step1：N-2到N-3位置哪个小，谁跑前面去。
step2：N-3到N-4位置哪个小，谁跑前面去。
···
stepN-2：1到0位置哪个小，谁跑前面去。
······
roundN-1
step1：1到0位置哪个小，谁跑前面去。
伪代码如下：
bubblesort(data[],n)
for i=0 到 n-2
for j=n-1 往下到 j+1
如果两者逆序，则交换位置j和位置j-1的元素
（2）复杂度
时间复杂度：
额外空间复杂度：
（3）优缺点
缺点：元素需要一步步地向上冒泡知道数组的顶部，这是非常费时的。
3.插入排序
（1）算法
如N个数升序排列:
使0到位置有序。
step1：从1位置往前看，前面大就交换，否则停止。
step2：到0位置或前面小停止。
这里的时间复杂度与数据的具体状况有关，这是与前两者排序的区别。
伪代码如下：
insertionsort(data[],n)
for i=1 到 n-1
将大于data[i]的所有元素data[j]都移动有一个位置，将data[i]放在合适的位置上
（2）复杂度
时间复杂度：（算法流程按照最差情况来估计时间复杂度，但是做实验一定比前两者好。）
额外空间复杂度：
【拓展】对有序数列查找某元素——二分法
在一个有序数组中，找某个数是否存在
在一个有序数组中，找>=某个数最左侧的位置
局部最小值问题
如N个升序排列的数，要找n：
时间复杂度：。多少次才能分成只有一个数。
（3）优缺点
优点：只有需要时才会对数组进行排序。如果数组已经排好序，就不会再对数据进行移动。
网友评论