排序就是将数据按一定顺序重新排列。它是很多算法的基础，可以让数据变得更容易处理。这篇文章会简单地介绍几种排序算法，当然这是初等排序，在效率上会比较差，但实现起来相对容易。
1. 插入排序法
插入排序法是一种很容易想到的算法，它的思路与打扑克时排列手牌的方法很相似。
插入排序法的算法如下：
insertionSort(A,N) //包含N个元素的0起点数组A
for i从１到N-1
v = A[i]
j = i - 1
while j >= 0 且 A[j] > v
A[j+1] = A[j]
j–
A[j+1] = v
请编写一个程序，用插入排序法将包含N个元素的数列A按升序排列。为检验算法的执行过程，请输出个计算步骤的数组。
输入 在第１行输入定义数组长度的整数N。在第２行输入N个整数，以空格隔开。
输出 输出总共有N行。
限制 1 =< N =< 100
0 =< A的元素 =< 1000
C
#include <stdio.h>
/* 按顺序输出数组元素 */
void trace(int A[], int N){
int i;
for(i=0;i<N;i++){
if(i>0) printf(" "); /*相邻元素之间输出１个空格 */
printf("%d", A[i]);
}
printf("\n");
}
/* 插入排序 */
void insertionSort(int A[], int N){
int j, i, v;
for(i=1;i<N;i++){
v = A[i];
j=i-1;
while(j>=0 && A[j]>v){
A[j+1] = A[j];
j--;
}
A[j+1] = v;
trace(A,N);
}
}
int main(){
int N, i, j;
int A[100];
scanf("%d", &N);
for(i=0; i < N; i++) scanf("%d", &A[i]);
trace(A,N);
insertionSort(A,N);
return 0;
}
2. 冒泡排序法
顾名思义，冒泡排序法就是让数组元素像水中的气泡一样逐渐上浮，进而达到排序的目的。下述算法便是利用冒泡排序法将数列排为升序的例子。
bubbleSort(A,N) //包含N个元素的0起点数组A
flag = 1
while flag
flag = 0
for j从N-1到1
if A[j]<A[j-1]
A[j]与A[j-1]交换
flag = 1
请编写一个程序，读取数列A，利用冒泡排序法将其按升序排列并输出。另外请报告冒泡排序法执行元素交换的次数。
输入 在第１行输入定义数组长度的整数N。在第2行输入N个整数，以空格隔开。
输出 总计２行。请在第１行输出排序后的数列。相邻元素以一个空格隔开。第２行输出元素交换的次数。
限制 1 =< N =< 100
0 =< A的元素 =< 100
C++
#include <iostream>
using namespace std;
//使用flag的冒泡排序法
int bubbleSort(int A[], int N){
int sw = 0;
bool flag = 1;
for(int i=0; flag; i++){
flag = 0;
for(int j= N-1; j>=i+1; j--){
if(A[j] < A[j-1]){
swap(A[j], A[j-1]);
flag = 1;
sw++;
}
}
}
return sw;
}
int main(){
int A[100], N, sw;
cin >> N;
for( int i=0; i< N; i++) cin >> A[i];
sw = bubbleSort(A,N);
for(int i=0; i < N; i++){
if (i) count << " ";
count << A[i];
}
count << endl;
count << sw << endl;
return 0;
}
3.选择排序法
选择排序法是一种非常直观的算法，它会在每个计算步骤中选出一个最小值，进而完成排序。
selectionSort(A,N)
for i 从0到N-1
minj = i
for j从i到N-1
if A[j] < A[minj]
minj = j
A[i]与A[min]交换
请编写一个程序，读取数列A，利用选择排序法将其按升序排列并输出。请输出实际运行过程中执行交换操作的次数。
输入 在第１行输入定义数组长度的整数N。在第2行输入N个整数，以空格隔开。
输出 总计２行。请在第１行输出排序后的数列。相邻元素以一个空格隔开。第２行输出元素交换的次数。
限制 1 =< N =< 100
0 =< A的元素 =< 100
C
#include <stdio.h>
/*选择排序法*/
int selectionSort( int A[], int N){
int i,j, t, sw=0, minj;
for(i = 0;i < N-1; i++){
minj = i;
for(j = i; j< N; j++) {
if(A[j] < A[minj] ) minj = j;
}
t = A[i]; A[i] = A[minj]; A[minj] = t;
if (i != minj) sw++;
}
return sw;
}
int main(){
int A[100], N, i, sw;
scanf("%d", &N);
for(i=0; i < N; i++) scanf("%d", &A[i]);
sw = selectionSort(A,N);
for(i = 0; i < N; i++){
if( i > 0) printf(" ");
printf("%d", A[i]);
}
printf("\n");
printf("%d", A[i]);
}
printf("\n");
printf("%d\n", sw);
return 0;
}
4. 稳定排序
所谓稳定排序，是指当数据中存在２个或２个以上键值相等的元素时，这些元素在排序处理前后顺序不变。
现在我们来给扑克牌排序。我们使用的扑克牌包含S,H,C,D的４种花色以及１，２，…,9，的９个数字，总计３６张。例如红桃８记为“H８”，方块１记为“D1”。
请编写一个程序，分别用冒泡排序法和选择排序法对输入的N张扑克牌进行以数字为基准的升序排列。两种算法需各自遵循下述伪代码的描述。下述数组元素皆为0起点。
bubbleSort(C,N)
for i = 0 to N-1
for j = N-1 downto i+1
if C[j].value < C[j-1].value
C[j] 与 C[j-1]交换
selestionSort(C, N)
for i = 0 to N-1
minj = i
for j = i to N-1
if C[j].value < C[minj].value
minj = j
C[i] 与 C[minj] 交换
另外，请报告各算法对于所给输入是否有稳定输出。
输入 在第１行输入扑克牌的张数N.
第２行输入N张扑克牌的数据。每张牌由代表花色和数字的２个字符组成，相邻扑克牌之间用１个空格隔开。
输出 在第一行按顺序输出经冒泡排序法排序后的扑克牌，相邻扑克牌之间用１个空格隔开。
在第２行输出该输出是否稳定。
在第3行按顺序输出经选择排序法排序后的扑克牌，相邻扑克牌之间用１个空格隔开。
在第4行输出该输出是否稳定。
限制 1 =< N =< 36
C++
#include <iostream>
using namespace std;
struct Card{ char suit, value;};
void bubble(struct Card A[], int N){
for(int i=0; i<N; i++){
for(int j = N-1; j >= i+1; j--){
if(A[j].value < A[j-1].value){
Card t= A[j]; A[j]=A[j-1]; A[j-1]=t;
}
}
}
}
void selection(struct Card A[], int N){
for(int i=0; i<N;i++){
int minj = i;
for(int j=i; j< N; j++){
if(A[j].value < A[minj].value) minj = j;
}
Card t = A[i]; A[i] = A[minj]; A[minj] = t;
}
}
void print(struct Card A[], int N){
for (int i=0; i<N; i++){
if(i>0) cout << " ";
cout << A[i].suit<< A[i].value;
}
cout << endl;
}
bool isStable(struct Card C1[], struct Card C2[], int N){
for( int i=0; i< N;i++){
if(C1[i].suit != C2[i].suit) return false;
}
return true;
}
int main(){
Card C1[100], C2[100];
int N;
char ch;
cin >> N;'
for( int i=0; i< N;i++){
cin >> C1[i[.suit >> C1[i].value;
}
for(int i=0; i<N; i++) C2[i] = C1[i];
bubble(C1,N);
selection(C2, N);
print(C1,N);
cout<< "Stable" << endl;
print(C2, N);
if( isStable(C1,C2,N){
cout<< "Stable" << endl;
} else {
cout << "not stable" << endl;
}
return 0;
}
5. 希尔排序法
我们在插入排序法的基础上进一步发挥，将包含ｎ个整数的数列A通过下列程序进行升序排列。
insertionSort(A,n,g)
for i = g to n-1
v = A[i]
j = i - g
while j >= 0 && A[j] > v
A[j+g] = A[j]
j = j - g
cnt ++
A[j+g] = v
shellSort(A,n)
cnt = 0
m = ?
G[] = {?,?,?,?,…,?}
for i = 0 to m-1
insertionSort(A, n, G[i])
insertionSort(A,n,g)是以间隔为g的元素为对象进行的插入排序。shellSort(A,n)则是insertionSort(A,n,g)的循环，并在每轮循环后逐渐缩小g的范围。这种排序方法称为希尔排序法。
C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;
//指定了间隔g的插入排序
void insertionSort(int A[], int n, int g){
for( int i = g; i< n; i++){
int v = A[i];
int j = i - g;
while (j >= 0 && A[j] > v){
A[j+g] = A[j];
j -= g;
cnt++;
}
A[j+g] = v;
}
}
void shellSort( int A[], int n){
//生成数列 G={1,4,13,40,121,364, 1093,...}
for (int h=1; ; ){
if(h > n) break;
G.push_back(h);
h = 3*h + 1;
}
for ( int i = G.size()-1; i>= 0; i--){
//按逆序指定G[i] = g
insertionSort(A, n, G[i]);
}
}
int main(){
cin >> n;
//使用速度更快的scanf函数进行输入
for ( int i=0; i < n; i++) scanf("%d", &A[i]);
cnt = 0;
shellSort(A,n);
cout << G.size() << endl;
for( int i= G.size() - 1; i >= 0; i--){
printf("%d", G[i]);
if(i) printf(" ");
}
printf("\n");
printf("%d\n", cnt);
for ( int i = 0; i < n; i++) printf("%d\n", A[i]);
return 0;
}
