10、算法

2021/11/4 22:13:30

本文主要是介绍10、算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

八大排序:

1、冒泡排序(沉尸排序)

**思想:**每次找到一个最大值放在最后面,每次找到一个最大值向后放(升序),两两比较,如果左边大于右边就交换他们的的值,每次比较结束后会得到最大值。降序就反过来。

**时间复杂度:**O(n^2)

**空间复杂度:**O(1)

**优点:**实现简单,稳定,不存在跳跃交换

**缺点:**时间复杂度大

#include<stdio.h>
#include<assert.h>
int * Bubble_sort(int* arr, int arrSize)
{
	assert(arr != NULL);
	for (int i = 0; i < arrSize - 1; i++)//比较的轮数
	{
		int rt = 0;//用于优化多余的比较
		for (int j = 0; j < arrSize - 1-i; j++)//比较的次数
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = 0;
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				rt = -1;
			}
		}
		if (rt != -1)
		{
			break;//如果rt=-1则表示还有值交换位置
		}
	}
	return arr;
}
int main()
{
	int arr[10] = { 1,22223,34,45,222,122,322,43434,44,2323 };
	Bubble_sort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3qgvdKMh-1636030575859)(C:\Users\刘锦\AppData\Roaming\Typora\typora-user-images\image-20211104195404564.png)]

2、选择排序

**思想:**每一轮从待排序列中找到最小值的下标,和待排序列的第一个值进行比较(升序),每次找到一个最小值放在最前面。

**注意!!!:**找的是最小值的下标,而不是最小值

**时间复杂度:**O(n^2)

**空间复杂度:**O(1)

**稳定性:**不稳定,存在跨越交换

#include<stdio.h>
#include<assert.h>
void Select_sort(int* arr, int arrSize)
{
	assert(arr != NULL);
	int minindex = 0;//保存最小值下标
	for (int i = 0; i < arrSize - 1; i++)//轮数
	{
		minindex = i;
		for (int j = i + 1; j < arrSize; j++)//在待排序序列中找到最小值下标,和当前数进行交换
		{
			if (arr[j ] < arr[minindex])
			{
				minindex = j ;
			}
		}
		//第二层for循环结束后,能确定最小值下标保存在minindex中
		if (minindex != i)
		{
			int temp = 0;
			temp = arr[i];
			arr[i] = arr[minindex];
			arr[minindex] = temp;
		}
	}
}
int main()
{
	int arr[10] = { 1,233,12,12,2,1221,122121,32,34,45 };
	Select_sort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4D1LRwIU-1636030575861)(C:\Users\刘锦\AppData\Roaming\Typora\typora-user-images\image-20211104203554295.png)]

3、直接插入

4、堆排序

5、基数排序

6、二路归并排序

7、希尔排序

[外链图片转存中...(img-4D1LRwIU-1636030575861)]

## 3、直接插入

## 4、堆排序

## 5、基数排序

## 6、二路归并排序

## 7、希尔排序

## 8、快排


这篇关于10、算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程