八、选择排序(从小到大)：
选择排序的基本思想是：每一趟从待排序的数据中，通过“打擂台”比较选出最小元素，放在这些数据的最前面。
这样，第一趟把 n 个数中（第 1 个到第 n 个）最小的放在第一个位置，
第二趟把剩余的 n-1 个数中（第 2 个到第 n 个）最小的放在第二个位置，
第三趟把剩余的 n-2 个数中（第 3 个到第 n 个）最小的放在第三个位，……
第 n-1 趟把剩下的 2 个数中（第 n-1 个到第 n 个）最小的放在第 n-1 个位置，
剩下的最后一个数（第 n 个）一定最大，自然落在了第 n个位置。
#### 选择排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i <= n; i++){
k = i; // 定义k为最小的位置
for(j = i+1; j <= n; j++)
if(h[j] < h[k]) k = j;// 在 i~n 之间的最小元素
temp = h[i];
h[i] = h[k]; // 把最小的放到第一个位置i ，依次第二个位置...
h[k] = temp;// 将 i~n 之间的最小元素放到第 i 个位置
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
九、冒泡排序(从小到大)：
冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果“逆序”就交换。
这样，一趟排序结束后，最大的元素就放在了第 n 个位置了。
第二趟把剩余的前 n-1 个数中最大的交换到第 n-1 个位置，
第三趟把剩余的前 n-2 个数中最大的交换到第 n-2 个位置，……
经过 n-1 趟，排序结束。
#### 冒泡排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++)
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
十、对于冒泡排序，我们还可以做些算法“优化”。
如果一趟排序下来，都没有任何“逆序”数对，即没有发生“交换”操作，
则说明已经排好序了。此时，就可以立刻退出循环。
#### 优化后的冒泡排序：
#include<iostream>
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++){
bool flag = true;
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
flag = false;
}
if(flag) break;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
十一、插入排序(从小到大):
插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。
每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。
开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；
第二趟，把第 3 个数插入进去，保证前 3 个数有；……
第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。
#### 插入排序的代码(从小到大)：
#include<iostream>
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 2; i <= n; i++){
temp = h[i];
k = 1;
while(h[k] <= temp && k < i) k++;
for(j = i-1; j >= k; j--) h[j+1] = h[j];
h[k] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
