【数据结构】排序算法精讲 | 交换排序全解：交换思想、效率对比与实战代码剖析

// 交换排序——冒泡排序
void BubbleSort(ElemType* nums, int len) {

}

	// 冒泡次数
	for (int i = 1; i < len; i++) {

	}

flowchart LR
a[冒泡元素] ---> b[待比较元素序列]

		// 一轮冒泡的比较次数
		for (int j = 0; j <= len - i - 1; j++) {

		}

	// 从后往前冒泡
	for (int i = 1; i < len; i++) {
		for (int j = len - 1; j >= i; j--) {

		}
	}

			LNode* p;					// 冒泡结点
			LNode* pre;					// 直接前驱
			LNode* suc;					// 直接后继
			// 判断元素是否逆序
			if (p->data > suc->data) {
				// 方法一：基于链表的交换操作
				pre->next = suc;		// 直接前驱指向直接后继
				p->next = suc->next;	// 冒泡结点指针指向原直接后继的直接后继
				suc->next = p;			// 原直接后继的后继指针指向冒泡结点
			}
			// 判断元素是否逆序
			if (nums[j] > nums[j + 1]) {
				// 方法二：基于顺序表的交换操作
				ElemType* tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}

			// 判断元素是否逆序
			if (p->data > suc->data) {
				// 方法三：参照顺序表实现的链表交换
				ElemType tmp = p->data;
				p->data = suc->data;
				suc->data = tmp;
			}

	// 冒泡次数
	for (int i = 1; i < len; i++) {
		// 交换标志
		bool flag = false;
		// 一轮冒泡的比较次数
		for (int j = 0; j <= len - i - 1; j++) {
			// 判断元素是否逆序
			if (nums[j] > nums[j + 1]) {
				// 方法二：基于顺序表的交换操作
				ElemType* tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
				flag = true;
			}
		}
		if (flag == false) {
			break;
		}
	}

// 算法头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <time.h>
typedef int ElemType;
// 交换排序——冒泡排序
void BubbleSort(ElemType* nums, int len);
// 插入排序——希尔排序
void ShellSort(ElemType* nums, int len);
// 插入排序——折半插入排序
void BInsertSort(ElemType* nums, int len);
// 插入排序——直接插入排序
void InsertSort(ElemType* a, int len);
// 数组打印
void Print(ElemType* arr, int len);
// 折半插入排序测试
void test();

// 算法实现文件
#include "Bubble_Sort.h"

// 交换排序——冒泡排序
void BubbleSort(ElemType* nums, int len) {
	// 冒泡次数
	for (int i = 1; i < len; i++) {
		// 交换标志
		bool flag = false;
		// 一轮冒泡的比较次数
		for (int j = 0; j <= len - i - 1; j++) {
			// 判断元素是否逆序
			if (nums[j] > nums[j + 1]) {
				// 方法二：基于顺序表的交换操作
				ElemType* tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
				flag = true;
			}
		}
		if (flag == false) {
			break;
		}
	}
}

// 插入排序——希尔排序
void ShellSort(ElemType* nums, int len) {
	// 第一层划分
	for (int d = len / 2; d >= 1; d /= 2) {
		// 第二层划分
		for (int i = 0; i < len - d; i++) {
			ElemType key = nums[i + d];	// 记录待插入元素
			// 查找与移动
			int j = i;	// 待插入元素下标
			while (j >= 0 && nums[j] > key) {
				nums[j + d] = nums[j];
				j -= d;
			}
			// 插入
			nums[j + d] = key;
		}
	}
}

// 插入排序——折半插入排序
void BInsertSort(ElemType* nums, int len) {
	// 按左侧有序有边界进行划分
	for (int i = 0; i < len - 1; i++) {
		int key = nums[i + 1];	// 待排序对象
		// 折半查找
		int l = 0, r = i;	// 折半查找的左右指针
		while (l <= r) {
			int m = (r - l) / 2 + l;
			// 中间值 大于 目标值，目标值位于中间值左侧
			if (nums[m] > key) {
				r = m - 1;	// 更新右边界
			}
			// 中间值 小于等于 目标值，目标值位于中间值右侧
			else {
				l = m + 1;
			}
		}
		// 移动
		for (int j = i; j >= l; j--) {
			nums[j + 1] = nums[j];
		}
		// 插入
		nums[l] = key;
	}
}

//插入排序——直接插入排序
void InsertSort(ElemType* a, int len) {
	//以左侧有序对象的起点作为分界线对排序对象进行划分
	for (int i = 0; i < len - 1; i++) {
		//记录需要排序的元素
		ElemType key = a[i + 1];
		//插入位置的查找
		int j = i;//记录左侧有序元素的起点
		//j < 0时表示查找完左侧所有元素
		//a[j] <= key时表示找到了元素需要进行插入的位置
		while (j >= 0 && a[j] > key) {
			a[j + 1] = a[j];//元素向后移动
			j -= 1;//移动查找指针
		}
		//插入元素
		a[j + 1] = key;
	}
}

// 数组打印
void Print(ElemType* arr, int len) {
	printf("元素序列：");
	for (int i = 0; i < len; i++) {
		printf("%d\t", arr[i]);
	}
	printf("\n");
}

// 冒泡排序测试
void test() {
	ElemType* arr1 = (ElemType*)calloc(100000, sizeof(ElemType));
	assert(arr1);
	ElemType* arr2 = (ElemType*)calloc(100000, sizeof(ElemType));
	assert(arr2);
	ElemType* arr3 = (ElemType*)calloc(100000, sizeof(ElemType));
	assert(arr3);
	ElemType* arr4 = (ElemType*)calloc(100000, sizeof(ElemType));
	assert(arr4);
	ElemType* arr5 = (ElemType*)calloc(10, sizeof(ElemType));
	assert(arr5);
	// 设置伪随机数
	srand((unsigned)time(NULL));
	// 生成10w个随机数
	for (int i = 0; i < 100000; i++) {
		arr1[i] = rand() % 100000;
		arr2[i] = arr1[i];
		arr3[i] = arr1[i];
		arr4[i] = arr1[i];
		if (i < 10) {
			arr5[i] = rand() % 100;
		}
	}

	// 算法健壮性测试
	printf("\n排序前：");
	Print(arr5, 10);
	BubbleSort(arr5, 10);
	printf("\n排序后：");
	Print(arr5, 10);

	// 算法效率测试
	int begin1 = clock();
	InsertSort(arr1, 100000);
	int end1 = clock();
	double time_used1 = ((double)(end1 - begin1)) / CLOCKS_PER_SEC;
	printf("\n直接插入排序总耗时：%lf 秒\n", time_used1);

	int begin2 = clock();
	BInsertSort(arr2, 100000);
	int end2 = clock();

	double time_used2 = ((double)(end2 - begin2)) / CLOCKS_PER_SEC;
	printf("\n折半插入排序总耗时：%lf 秒\n", time_used2);

	int begin3 = clock();
	ShellSort(arr3, 100000);
	int end3 = clock();

	double time_used3 = ((double)(end3 - begin3)) / CLOCKS_PER_SEC;
	printf("\n    希尔排序总耗时：%lf 秒\n", time_used3);

	int begin4 = clock();
	BubbleSort(arr4, 100000);
	int end4 = clock();

	double time_used4 = ((double)(end4 - begin4)) / CLOCKS_PER_SEC;
	printf("\n    冒泡排序总耗时：%lf 秒\n", time_used4);

	free(arr1);
	arr1 = NULL;
	free(arr2);
	arr2 = NULL;
	free(arr3);
	arr3 = NULL;
	free(arr4);
	arr4 = NULL;
	free(arr5);
	arr5 = NULL;
}

// 算法测试文件
#include "Bubble_Sort.h"
int main() {
	test();
	return 0;
}