[数据结构与算法]初等排序算法（图解+代码）

插入排序法

输入示例：
6
5 2 4 6 1 3

输出示例：
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

#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 i, j, 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;
    
}

冒泡排序法

输入示例：
5 
5 3 2 4 1
输出示例：
1 2 3 4 5
8

#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) cout << " ";
		cout << A[i];
	}
    
	cout << endl;
	cout << sw << endl;
	
	return 0;
    
}

选择排序法

输入示例：
6
5 6 4 2 1 3
输出示例：
1 2 3 4 5 6
4

#include<stdio.h>

// 选择排序法（0起点）
int selectionSort(int A[], int N){
	int i, j, t, sw = 0, minj;
	
	for(int 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\n",sw);
    
	return 0;

}

稳定排序

输入示例：
5
H4 C9 S4 D2 C3
输出示例：
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

#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;
		}
	} 
} 


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;

}



	} 
	
	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;

}