IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> C++多种排序算法(针对数组) -> 正文阅读

[数据结构与算法]C++多种排序算法(针对数组)

一、冒泡排序

template<class T>
inline void CMySort_Array<T>::Bubble_sort(T arr[],int len)
{
	int i, j, tempval;
	for (i = len-1; i > 0; i--)
		for (j = 0; j < i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tempval = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tempval;
			}
		}
}

二、选择排序

template<class T>
inline void CMySort_Array<T>::Selection_sort(T arr[], int len)
{
	int i, j, serial, tempval;
	for (j = 0; j < len - 1; j++)
	{
		serial = j;
		for (i = j + 1; i < len; i++)
		{
			if (arr[serial] > arr[i])serial = i;
		}
		tempval = arr[serial];
		arr[serial] = arr[j];
		arr[j] = tempval;
	}
}

三、插入排序

template<class T>
inline void CMySort_Array<T>::Insertion_Sort(T arr[], int len)
{
	int j, tempval;
	for (int i = 1; i < len; i++)
	{
		tempval = arr[i];
		j = i - 1;
		while (j >= 0 && tempval < arr[j])
		{
			arr[j + 1] = arr[j];
			j -= 1;
		}
		arr[j + 1] = tempval;
	}
}

四、希尔排序

template<class T>
inline void CMySort_Array<T>::Shell_Sort(T arr[], int len)
{
	int j, tempval;
	int jump = len >> 1;
	while (jump != 0)
	{
		for (int i = jump; i < len; i++)
		{
			tempval = arr[i];
			j = i - jump;
			while (j >= 0 && tempval < arr[j])
			{
				arr[j + jump] = arr[j];
				j -= jump;
			}
			arr[j + jump] = tempval;
		}
		jump >>= 1;
	}
}

五、快速排序

1、这里调用_Quick_Sort(arr, 0, len-1);的目的是定义对象后方便使用这个算法

template<class T>
inline void CMySort_Array<T>::Quick_Sort(T arr[], int len)
{
	_Quick_Sort(arr, 0, len-1);
}

2、上面调用的函数(_Quick_Sort(arr, 0, len-1);)的代码,真正的快排代码

template<class T>
inline void CMySort_Array<T>::_Quick_Sort(T arr[], int low, int hight)
{
	int L = arr[low];//标杆值
	int head = low + 1;//期望指的数比标杆小
	int tail = hight;//期望指的数比标杆大

	if (low >= hight)return;//表示只有一个元素,该元素无需定位

	int tempval;
	while (head<=tail)
	{
		while (head <= tail && arr[head] <= L)head++;
		while (head <= tail && arr[tail] >= L)tail--;
		if (head < tail)
		{
			tempval = arr[head];
			arr[head] = arr[tail];
			arr[tail] = tempval;
			head++;
			tail--;
		}
	}
	arr[low] = arr[tail];
	arr[tail] = L;
	_Quick_Sort(arr, low, tail - 1);
	_Quick_Sort(arr, tail + 1, hight);
}

六、归并排序

1、这里调用_Merge_Sort_Recursion(arr, 0, len - 1);的目的是定义对象后方便使用这个算法

template<class T>
inline void CMySort_Array<T>::Merge_Sort(T arr[], int len)
{
	_Merge_Sort_Recursion(arr, 0, len - 1);
}

2、归操作代码

template<class T>
inline void CMySort_Array<T>::_Merge_Sort_Recursion(T arr[], int left, int right)
{
	//归操作
	if (left >= right)return;//只有一个元素
	int mid = left + ((right - left) >> 1);
	_Merge_Sort_Recursion(arr, left, mid);//左区间
	_Merge_Sort_Recursion(arr, mid+1, right);//右区间

	//并操作
	_Merge_Sort_Merge(arr, left, mid, right);
}

3、并操作代码

template<class T>
inline void CMySort_Array<T>::_Merge_Sort_Merge(T arr[], int left, int mid, int right)
{
	//准备一个合并用的辅助数组
	int length = right - left + 1;
	int* pDate = new int[length];

	//合并
	int low = left;//表示左区间最小值
	int hight = mid + 1;//表示右区间最小值
	int index = 0;
	while (hight <= right && low <= mid)//表示左右区间存在
	{
		while (hight <= right && arr[low] > arr[hight])//表示右区间最小值要小
		{
			pDate[index] = arr[hight];
			index++;
			hight++;
		}
		while (low <= mid && arr[low] <= arr[hight])//表示左区间最小值要小
		{
			pDate[index] = arr[low];
			index++;
			low++;
		}
	}

	//到这一步,证明有一个区间是合并进辅助数组了
	if (hight <= right)//右区间还没有合并完
		memmove(&pDate[index], &arr[hight], sizeof(T) * (right - hight + 1));
	if (low <= mid)//左区间还没有合并完
		memmove(&pDate[index], &arr[low], sizeof(T) * (mid - low + 1));

	//辅助空间合并完成之后拷贝回原始数组
	memmove(&arr[left], pDate, sizeof(T) * length);
	delete[] pDate;
}

七、排序算法 .h 文件下载地址

链接: CMySort_Array.h

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-26 12:18:24  更:2021-07-26 12:18:58 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/27 9:46:24-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计