数据结构-排序算法实践

简单插入排序

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50 
// 定义顺序表结构
typedef struct {
   
	int r[MAXSIZE + 1];  //r[0]闲置或用作哨兵单元
	int length;  // 顺序表长度
}SqList;

/** * 对顺序表L作直接插入排序 * @param L 顺序表L */
void InsertSort(SqList& L) {
   
	int i, j;
	for (i = 2; i <= L.length; i++)
	{
   
		if (L.r[i] < L.r[i - 1]) {
     // "<",则需将L.r[i]插入有序表
			L.r[0] = L.r[i];  // 复制为哨兵
			L.r[i] = L.r[i - 1];  // 第i个<第i-1个，先交换一次
			for (j = i - 2; L.r[0] < L.r[j]; --j)  // 再从第i-2个开始往前比较
				L.r[j + 1] = L.r[j];  //记录后移
			L.r[j + 1] = L.r[0];  // 插入到正确位置
		}
	}
}

/** * 输出顺序表 * @param L 顺序表L */
void Print_SqList(SqList L) {
   
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i] << " ";
	cout << endl;
}

int main() {
   
	int n;
	int r[MAXSIZE + 1];
	cin >> n;
	SqList L;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> L.r[i];
	}
	L.length = n;

	cout << "插入排序：";
	InsertSort(L);
	Print_SqList(L);
	
	return 0;
}

冒泡排序

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50 
// 定义顺序表结构
typedef struct {
   
	int r[MAXSIZE + 1];  //r[0]闲置或用作哨兵单元
	int length;  // 顺序表长度
}SqList;

/** * 最顺序表L作冒泡排序 * @param L 顺序表L */
void BubbleSort(SqList& L) {
   
	for (int i = 1; i < L.length; i++)
	{
   
		bool flag = false;  // 是否发生交换的标志
		for (int j = L.length; j > i; j--)  // 一趟冒泡
		{
   
			if (L.r[j - 1] > L.r[j]) {
     // 逆序则交换
				swap(L.r[j - 1], L.r[j]);  // C++中提供的交换函数
				flag = true;
			}
		}
		if (!flag)
			break;  //一趟冒泡没有发生交换，说明表已有序
	}
}

/** * 输出顺序表 * @param L 顺序表L */
void Print_SqList(SqList L) {
   
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i] << " ";
	cout << endl;
}

int main() {
   
	int n;
	int r[MAXSIZE + 1];
	cin >> n;
	SqList L;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> L.r[i];
	}
	L.length = n;

	cout << "冒泡排序：";
	BubbleSort(L);
	Print_SqList(L);
	
	return 0;
}

快速排序

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50 
// 定义顺序表结构
typedef struct {
   
	int r[MAXSIZE + 1];  //r[0]闲置或用作哨兵单元
	int length;  // 顺序表长度
}SqList;

/** * 交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位 * 置，此时在它之前（后）的记录均不大（小）于它 * @param L 顺序表L * @param low 起始位置 * @param high 结束位置 * @return 返回枢轴位置 */
int Partition(SqList& L, int low, int high) {
   
	L.r[0] = L.r[low];  // 用子表的第一个记录作枢轴记录
	int pivotkey = L.r[low];  // 枢轴记录关键字
	while (low < high) {
     // 从表的两端交替地向中间扫描
		while (low < high && L.r[high] >= pivotkey)
			--high;
		L.r[low] = L.r[high];  // 将比枢轴记录小的记录移到低端
		while (low < high && L.r[low] <= pivotkey)
			++low;
		L.r[high] = L.r[low];  // 将比枢轴记录大的记录移到高端
	}
	L.r[low] = L.r[0];  // 枢轴记录到位
	return low;  // 返回枢轴位置
}
/** * 对顺序表L中的子序列L.r[low..high]作快速排序 * @param L 顺序表L * @param low 起始位置 * @param high 结束位置 */
void Qsort(SqList& L, int low, int high) {
   
	if (low < high) {
     // 长度大于1
		int pivotloc = Partition(L, low, high);  // 将L.r[low..high]一分为二
		Qsort(L, low, pivotloc - 1);  // 对低子表递归排序，piovtloc是枢轴位置
		Qsort(L, pivotloc + 1, high);  // 对高子表递归排序
	}
}
/** * 对顺序表L作快速排序 * @param L 顺序表L */
void QuickSort(SqList& L) {
   
	Qsort(L, 1, L.length);
}
/** * 输出顺序表 * @param L 顺序表L */
void Print_SqList(SqList L) {
   
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i] << " ";
	cout << endl;
}

int main() {
   
	int n;
	int r[MAXSIZE + 1];
	cin >> n;
	SqList L;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> L.r[i];
	}
	L.length = n;

	cout << "快速排序：";
	QuickSort(L);
	Print_SqList(L);
	
	return 0;
}

归并排序

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50 
// 定义顺序表结构
typedef struct {
   
	int r[MAXSIZE + 1];  //r[0]闲置或用作哨兵单元
	int length;  // 顺序表长度
}SqList;

int B[MAXSIZE];  // 辅助数组B
/** * 表A的两端A[low..mid]和A[mid+1..high]各自有序，将它们合并成一个有序表 * @param A 数组A * @param low 起始位置 * @param mid 中间位置 * @param high 结束位置 */
void Merge(int A[], int low, int mid, int high) {
   
	int i, j, k;
	for (k = low; k <= high; k++)
		B[k] = A[k];  // 将A中的所有元素赋值到B中
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
   
		if (B[i] <= B[j])  // 比较B的左右两段中的元素，将较小值复制到A中
			A[k] = B[i++];
		else
			A[k] = B[j++];
	}
	while (i <= mid)  // 若第一个表未检测完，直接复制后面的
		A[k++] = B[i++];
	while (j <= high)  // 若第二个表未检测完，直接复制后面的
		A[k++] = B[j++];
}
/** * 对表A作归并排序 * @param A 表A * @param low 起始位置 * @param high 结束位置 */
void MergeSort(int A[], int low, int high) {
   
	if (low < high) {
   
		int mid = (low + high) / 2;  // 从中间划分为两个子序列
		MergeSort(A, low, mid);  // 对左侧子序列进行递归排序
		MergeSort(A, mid + 1, high);  // 对右侧子序列进行递归排序
		Merge(A, low, mid, high);  // 归并
	}
}

/** * 输出顺序表 * @param L 顺序表L */
void Print_SqList(SqList L) {
   
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i] << " ";
	cout << endl;
}

int main() {
   
	int n;
	int r[MAXSIZE + 1];
	cin >> n;
	SqList L;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> L.r[i];
	}
	L.length = n;

	cout << "归并排序：";
	MergeSort(L.r, 1, L.length);
	Print_SqList(L);
	
	return 0;
}

堆排序

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50 
// 定义顺序表结构
typedef struct {
   
	int r[MAXSIZE + 1];  //r[0]闲置或用作哨兵单元
	int length;  // 顺序表长度
}SqList;

/** * 对顺序表H进行调整为大顶堆，H.r[s..m]中记录的关键字均满足堆的定义 * @param H 顺序表H * @param s 起始位置 * @param m 结束位置 */
void HeapAdjust(SqList& H, int s, int m) {
   
	int rc = H.r[s];
	for (int j = 2 * s; j <= m; j *= 2) {
     // 沿关键字值较大的孩子结点向下筛选
		if (j < m&& H.r[j] < H.r[j + 1])  // j为关键字值较大的记录的下标
			++j;
		if (rc >= H.r[j])  // rc应插入在位置s上
			break;
		H.r[s] = H.r[j];
		s = j;
	}
	H.r[s] = rc;  // 插入
}
/** * 对顺序表H进行堆排序 * @param H [description] */
void HeapSort(SqList& H) {
   
	for (int i = H.length / 2; i > 0; --i)  // 把H.r[1..H.length]建成大顶堆
		HeapAdjust(H, i, H.length);
	for (int j = H.length; j > 1; --j) {
   
		swap(H.r[1], H.r[j]);  // 将堆顶记录和当前未经排序子序列H.r[i..i]中最后一个记录相互交换
		HeapAdjust(H, 1, j - 1);  // 将H.r[1..j-1]重新调整为大顶堆
	}
}

/** * 输出顺序表 * @param L 顺序表L */
void Print_SqList(SqList L) {
   
	for (int i = 1; i <= L.length; i++)
		cout << L.r[i] << " ";
	cout << endl;
}

int main() {
   
	int n;
	int r[MAXSIZE + 1];
	cin >> n;
	SqList L;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> L.r[i];
	}
	L.length = n;

	cout << "堆排序：";
	HeapSort(L);
	Print_SqList(L);
	
	return 0;
}