kubeflow 另类堆栈 Hibernate ajax qt class oop listview variables generics arraylist plugins vue插件 管理后台模板 jquery第一个子元素 centos查看php版本 idea返回值快捷键 android富文本框架 pr序列设置哪个好 python计算器 python环境安装教程 python创建文件 java框架学习 java基础框架 java学习流程 javalist转数组 mac地址修改器 1660ti 神剪辑教程 saminside oem修改器 扫微信二维码诈骗原理 机械键盘个别键位失灵 cdlinux教程 类似迅雷的下载软件 js字符串转数字 SQLite编辑器 zepto下载 cad如何旋转图形 topaz滤镜
当前位置: 首页 > 学习教程  > 编程语言

四大排序算法:冒泡,插入,选择,快速

2020/8/11 20:33:27 文章标签:

四大排序算法:冒泡,插入,选择,快速

  • 冒泡排序
    • 基本概念
    • C++代码
    • 时间复杂度和空间复杂度
  • 插入排序
    • 基本概念
    • C++代码
    • 时间复杂度和空间复杂度
  • 选择排序
    • 基本概念
    • C++代码
    • 时间复杂度和空间复杂度
  • 快速排序
    • 基本概念
    • C++代码
    • 时间复杂度和空间复杂度

冒泡排序

基本概念

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。一遍冒泡排序之后,就会将最大(最小)的数放到最后去,所以第二遍时就不用再与第一遍冒泡排序最后的数进行比较。

C++代码

#include<iostream>
using namespace std;
// 声明冒泡排序算法(参数含义:1.数组 2.数组尺寸)
void BubbleSort(int arr[], int n);
// 声明打印算法
void PrintArr(int arr[], int n);

int main()
{
	// 数组例子
	int arr[] = { 2, 3, 4, 1, 5, 6, 2, 8, 9 };
	// 数组大小
	int n = sizeof(arr) / sizeof(int);
	// 冒泡排序
	BubbleSort(arr, n);
	PrintArr(arr, n);
	return 0;
}
// 冒泡排序实现
void BubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		for (j = 0; j < n - 1 - i; j++)
		{
			// 交换
			if (arr[j + 1] < arr[j])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}
// 打印算法实现
void PrintArr(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

时间复杂度和空间复杂度

时间复杂度为:O(n^2)
空间复杂度为:O(1),空间复杂度就是看有没有辅助存储对象,因为有一个临时变量temp,作用为交换两个元素。其实,空间复杂度可以降为O(0),就是将交换代码改为:

a = a + b;
b = a - b;
a = a - b;

但是,这样有可能出现越界的问题,所以,老老实实的用临时变量较好

插入排序

基本概念

从左到右逐步构建递增或者递减序列,对于未排序数据,逐步在已排序的数据中找到合适的位置插入
选择当前为key的值插入之前排序好的数组中,让其也变为排序好的数组,这样循环往复,就会使整个数组排序好
插入排序在小规模数据或者基本有序的数据中应用时高效
而在对较大规模并且无序的数据时,插入排序并不高效,需要进行改进,希尔排序就可实现这个效果

C++代码

#include<iostream>
using namespace std;
// 声明插入排序算法(参数:1.数组 2.数组大小)
void InsertSort(int arr[], int n);
// 声明打印方法
void PrintArr(int arr[], int n);

int main()
{
	// 例子数组
	int arr[] = { 4, 4, 6, 1, 7, 8, 23, 15, 9, 2 };
	// 数组大小
	int n = sizeof(arr) / sizeof(int);
	InsertSort(arr, n);
	PrintArr(arr, n);
	return 0;
}
// 插入排序实现
void InsertSort(int arr[], int n)
{
	int i, j, key;
	for (i = 0; i < n; i++)
	{
		// 选择当前为key的值插入i之前排序好的数组中,让其也变为排序好的数组
		key = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > key)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}
}
// 打印输出方法实现
void PrintArr(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << "  ";
	}
	cout << endl;
}

时间复杂度和空间复杂度

时间复杂度为:O(n^2)
空间复杂度为:O(0),交换没有临时变量temp

选择排序

基本概念

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

C++代码

#include<iostream>
#include<iomanip>
using namespace std;

void SelectSort(int arr[], int n);//选择排序
void EnterArr(int arr[], int n);
void PrintArr(int arr[], int n);

int main()
{
	int arr[10] = { 7, 6, 8, 2, 1, 4, 0, 9, 2, 3 }; 
	int n = 10;
	SelectSort(arr, n);
	cout << "排好序后:";
	PrintArr(arr, n);
	return 0;
}

void SelectSort(int arr[], int n)
{
	int i, j, min, temp;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i + 1; j < n; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		if (i != min)
		{
			temp = arr[min];
			arr[min] = arr[i];
			arr[i] = temp;
		}
	}
}

void EnterArr(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
}

void PrintArr(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

时间复杂度和空间复杂度

时间复杂度为:O(n^2)
空间复杂度为:O(1),因为有一个临时变量temp

快速排序

基本概念

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

C++代码

#include<iostream>
using namespace std;
void Qsort(int arr[], int low, int high);//快速排序
int main()
{
	int arr[10] = { 7, 6, 8, 2, 1, 4, 0, 9, 2, 3 }; 
	int n = 10;
	Qsort(arr, 0, sizeof(arr) / sizeof(int) - 1);
	cout << "排好序后:";
	PrintArr(arr, n);
	return 0;
}
void Qsort(int arr[], int low, int high)//快速排序
{
	if (high <= low)
	{
		return;
	}
		
	int i = low;
	int j = high + 1;
	int key = arr[low];
	while (true)
	{
		//从左往右找比key大的值
		while (arr[++i] < key)
		{
			if (i == high)
			{
				break;
			}
		}
		//从右往左找比key小的值
		while (arr[--j] > key)
		{
			if (j == low)
			{
				break;
			}
		}
		if (i >= j)
		{
			break;
		}
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//中枢值与j对应的值交换
	int temp = arr[low];
	arr[low] = arr[j];
	arr[j] = temp;
	// 左边递归快排
	Qsort(arr, low, j - 1);
	// 右边递归快排
	Qsort(arr, j + 1, high);
}
void PrintArr(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

时间复杂度和空间复杂度

时间复杂度为:最优情况:O(nlogn),最坏情况:O(n^2),平均:O(nlogn)
空间复杂度为:O(logn)


本文链接: http://www.dtmao.cc/news_show_100360.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?