冒泡排序实现以及优化

一，冒泡排序说明

冒泡排序是从第一个元素开始和后面一个元素进行判断是否满足左小右大，如果不满足就交换位置，再拿第二个和第三个进行上述操作一直到第n-1和第n个。

经过上述的一轮操作就可以把第一个最大值放到最右边，在进行n轮上述操作就可完成所有元素的排序

因此冒泡排序的时间复杂度稳定为O(n^2)

二，冒泡排序代码

//
// Created by 27893 on 2025/8/10.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BubbleSort.h"

void BubbleSort(SortTable *table) {
	for (int i=0;i<table->length;i++) {
		for (int j=0;j<table->length-i-1;j++) {
			if (table->data[j].key>table->data[j+1].key) {
				swap(&table->data[j],&table->data[j+1]);
			}
		}
	}
}

void swap(Element*a,Element*b) {
	Element*temp=malloc(sizeof(Element));
	memcpy(temp,a,sizeof(Element));
	memcpy(a,b,sizeof(Element));
	memcpy(b,temp,sizeof(Element));
	free(temp);
}

三，冒泡排序的优化

1.第一种

随着我们的交换可能不需要n轮就已经将所有元素排好序了，比如我们在对第一个最大值进行排序时就可以把所有元素排好序，就没必要进行第二轮了，我们就可以用一个变量来记录这轮内循环是否有过交换，若果没有就说明已经排好序了

void BubbleSort(SortTable *table) {
	for (int i=0;i<table->length;i++) {
		int isSorted=1;
		for (int j=0;j<table->length-i-1;j++) {
			if (table->data[j].key>table->data[j+1].key) {
				isSorted=0;
				swap(&table->data[j],&table->data[j+1]);
			}
		}
		if (isSorted) {
			break;
		}
	}
}

2.第二种

如下图假如经过第一轮排序，从65开始后面的元素就已经有序了，那么下轮排序就只需要循环到65为止后面的就不需要比较了

void BubbleSortV3(SortTable *table) {
	int newIndex=0;
	do {
		int n=table->length;
		for (int i=0;i<n-1;i++) {
			if (table->data[i].key>table->data[i+1].key) {
				swap(&table->data[i],&table->data[i+1]);
				newIndex=i+1;
			}
		}
		n=newIndex;
	}while (newIndex>0);
}