数据结构——八大排序

参考英雄哥的《画解数据结构》，并做了点自己的修改

本章实现默认是基于升序排序的原则进行排序

在此之前呢我们提前准备好一个打印函数，方便我们进行测试

void print_array(int* a, int n) {
	for (int i = 0; i < n; ++i) {
		printf("%d", a[i]);
		printf(" ");
	}
	printf("n");
}

void InsertSort(int* a, int n) {
	int i, j;
	print_array(a, n);
	for (i = 1; i < n; ++i) {
	//从第一个开始因为默认0处有序
		int tmp = a[i];//记录比较的数
		for (j = i - 1; j >= 0; --j) {
			//一直往前比
			if (a[j] > tmp) {
				a[j + 1] = a[j];//比tmp大的往前放
			}
			else {
				break;//直到没有比tmp大的说明前面已经有序
			}
			//把tmp放入正确的位置奥，已经退出j循环判断一下发现要放入j+1的位置
			//因为上一轮应该a[j]
	int a[] = { 7,3,6,78,1,3,6,4,2,2,10 };
	InsertSort(a, 11);
	return 0;
}

其实就是从前往后比，采取一个先让前面有序再让后面有序的一个过程，每次选择一个 key，让每一个前面的值与他作比较，

如果比他则往后移，比他小或者相等则不动，就说面前面都是比他小的了，将其放入这个值前面的数即可。

好的情况每个比一次循环依次为 大O(n)

最坏时间复杂度每个都比 key大每个都要交换即是 大O(n)

具有 稳定性

运行结果如下图所示：

在写之前先写个swap交换的函数

int swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

在写一个打印函数

void print_arr(int* a, int len, int swapped) {
	for (int i = 0; i < len; ++i) {
		printf("%d", arr[i]);
		printf(" ");
	}
	printf("%sn", swapped ? "swapped" : "not swapped");
}

最后就可以开始写冒泡排序啦

void bubble_sort(int* a, int len) {
		//第一次循环全部都要比，第一次把最终确定的最大数放到顶上
	for (int i = len; i > 1; --i) {
		int swapped = 0;//做标记
		//当i=1时候自然为升序	
		for (int j = 1; j < i; j++) {
			if (a[j - 1] > a[j]) {
				swap(&a[j - 1], &a[j]);//比他小的时候大的往上冒泡
				swapped = 1;//修改标记表示已经交换过啦
			}
		}
		print_arr(a, len, swapped);
		if (!swapped)
			break;//说明下面全部有序不用在冒泡啦
	}
}
//测试函数
int main() {
	int a[] = { 7,3,6,78,1,3,6,4,2,2,10 };
	
	bubble_sort(a, 11);
	return 0;
}

写这算法最好把数组想想为竖着的一个柱子，第一遍对全部数列进行排序，把最大的从某一处冒到最顶上，然后就造成了 局部有序，然后最大的数在最顶上的情况，接着开始不用比最顶了，就 长度减1然后再从底下依次往上冒，直到某一次下面全部都没有往上冒泡了，即 swapped=0 结束循环

运行结果如下

在之前写好的 swap交换函数和 print_array函数的前提下直接开始写这个函数

//选择排序
int SelectSort(int* a, int len) {
	int i, j, min;
	for (i = 0; i < len; ++i) {
		min = i;//假设第一个为最小的第二轮第一个选出最小的就假设第二个为最小的
		for (j = i + 1; j < len; ++j) {
			//后面的元素和min比小的跟min换
			if (a[min] > a[j]) {
				min = j;
			}
		}
		//这时候min已经是最小下标了
	   //直接交换即可
		swap(&a[min], &a[i]);
		print_array(a,len);
	}
}
//测试代码
int main() {
	int a[] = { 7,3,6,78,1,3,6,4,2,2,10 };
	print_array(a, 11);
	
	
	SelectSort(a, 11);
	return 0;
}

其实这个排序也很简单，主要的思想就是：

1.把每次大循环的第一个数组下标都假定成最小的那一个

2.循环后续的数组数据，如果找到比之前假定的数组值小则将其下标赋值给 min

3.小循环后找出最小值，swap第一个和最小的元素值

时间复杂度：可以发现两层for，轻松推得复杂度为 O(n²)

空间复杂度：由于没借用其他空间复杂度依然保持为 O(1)

运行结果如下

稍微有点意思啦这个算法

1636. 按照频率将数组升序排序 - 力扣（LeetCode）

上面这道题就可以用这个方法

让我们来看看这算法咋写吧

//计数排序
void counting_sort(int* a, int len) {
	if (len < 2) return;
	//寻找到数组最大的项
	int max = a[0];
	for (int i = 0; i < len; ++i) {
		if (a[i] > a[0]) {
			max = a[i];
		}
	}
	//找到max最大数值了
	//建立一个count计数数组
	int* count = (int*)malloc(sizeof(int) * (max + 1));
	memset(count, 0, sizeof(int) * (max + 1));//初始化全0
	//按下表放入类似哈希
	for(int i=0;i
		count[a[i]]++;
	}
	//统计累计值
	for (int i = 1; i < max + 1; ++i) {
		count[i] = count[i] + count[i - 1];//类似贪心
		//出来的数组就是后一个数组值是前面全部加起来的累计值
	}
	//创建临时数组保存结果
	int* tmp = (int*)malloc(sizeof(int) * len);
	//按原来数组的顺序依次放入
    //假设元素组：332151
	for (int i = 0; i < len; i++) {
		//第一个元素
		tmp[count[a[i]]-1] = a[i];
		count[a[i]]--;//记得一定要给计数器减，因为会有重复的元素不减位置不知道了
	}
	//最后将结果赋值给元素组
	for (int i = 0; i < len; ++i) {
		a[i] = tmp[i];
	}
	return;
}

配合我的注释进行理解：

第一步：用哈希的思想把元素出现的大小按升序的方式记录起来，小标表示的元素的值，并且里面记录的元素代表的是元素出现的次数

第二步：设计计数数组，按贪心算法的思想将数组每一项前面包括自己出现次数加起来，每个下标值代表数组中出现的元素，其中记录的值代表的是下标值及其前面所有出现的次数

第三步：设置临时数组对照这原数组和计数数组将元素依次放入即可，如何放入呢？举例第一个元素把，由原数组找出元素值，然后区计数数组中找到其值也就是下标，由于计数数组记录的是到它包括它自己的所有元素，又由于第一个元素小标0，所以其元素值-1即是他升序后应该在的位置，就这样依次遍历完原数组即可找到所有值

第四步：把临时数组的值赋值给原数组结束！！！

其运行结果如下