数据结构-常见的排序算法

这篇具有很好参考价值的文章主要介绍了数据结构-常见的排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

排序的概念及其运用

排序的概念

常见的排序算法

常见排序算法的实现

插入排序

插入排序

希尔排序(缩小增量排序)

选择排序

直接选择排序

堆排序

交换排序

冒泡排序

快速排序

归并排序

非比较排序

排序算法复杂度及稳定性分析


排序的概念及其运用

排序的概念

排序:所谓排序,就是按照某个或者某些关键词的大小,按找指定顺序进行排列。

稳定性:假设在待定排序的记录序列中,经过排序之后,这些记录的相对次序保持不变,则称为这种排序算法是稳定的;否则称为不稳定。

内部排序:数据元素全部存放在内存中的排序。

外部排序:数据元素过多,无法同时存放外内存中。

常见的排序算法

数据结构-常见的排序算法,数据结构,排序算法,算法

常见排序算法的实现

插入排序

插入排序

插入排序:将待排序的元素按照大小逐一插入到一个已经排序好的有序队列当中,从而得到一个新的有序序列。

在生活中,扑克牌排序就运用了插入排序的思想

数据结构-常见的排序算法,数据结构,排序算法,算法

        当插入第i(i>=0)个元素时,前面的array[0],array[1].....array[i-1]已经进行了排序,此时用array[i]的排序与前面的元素进行比较,找到array[i]的位置进行插入,原来位置上的元素向后移动。

数据结构-常见的排序算法,数据结构,排序算法,算法

 代码实现:

//插入排序代码实现
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//[0,end]为升序排列 tmp为a[end+1]元素和[0,end]元比较进行插入
		//使得[0,end+1]成为升序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

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

void TestInsert()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestInsert();
	return 0;
}

希尔排序(缩小增量排序)

        希尔排序法又称缩小增量法。希尔排序的基本思想是:先选定一个整数最为距离,把待排序文件中所有记录分组,所有距离为相同的记录分为一组,并对每一组内的记录进行排序之后缩小距离,再重复上序分组和排序工作,最后当距离为1事后,所有记录在组内完成排序。

         希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

数据结构-常见的排序算法,数据结构,排序算法,算法

数据结构-常见的排序算法,数据结构,排序算法,算法

//希尔排序代码实现
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
        //gap=gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

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

void TestShellSort()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestShellSort();
	return 0;
}

数据结构-常见的排序算法,数据结构,排序算法,算法

在上述代码中 gap 取 gap / 2 ,也可取 gap / 3 +1 进行实现  ,并且时间复杂度数据结构-常见的排序算法,数据结构,排序算法,算法之间,取数据结构-常见的排序算法,数据结构,排序算法,算法

选择排序

直接选择排序

        每一次从待排序的数据中选出最大(或最小)的一个元素,存放在序列的起始位置,直到所有待排序的元素排序完成。

数据结构-常见的排序算法,数据结构,排序算法,算法

//选择排序实现
//每次遍历同时找出最小值和最大值,放入队尾和队末
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		//如果max被换走了 则修改位置
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

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

void TestSelectSort()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestSelectSort();
	return 0;
}

堆排序

        堆排序(HeapSort)使用堆树数据结构所设计的一种排序算法,属于选择排序的一种。通过堆来进行数据选择。注意:排升序需要建大堆 ,排降序需要建小堆

数据结构-常见的排序算法,数据结构,排序算法,算法

//堆排序代码实现
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

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

void TestHeapSort()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestHeapSort();
	return 0;
}

交换排序

冒泡排序

        冒泡排序:从序列中的第一个元素开始,依次对相邻的两个元素进行比较,如果前一个元素大于后一个元素则交换它们的位置。如果前一个元素小于或等于后一个元素,则不交换它们;直到最后一个还未排好序的元素为止。

数据结构-常见的排序算法,数据结构,排序算法,算法

//冒泡排序代码实现
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;    //exchange记录是否进行交换
		for (int j = 1; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j], &a[j - 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)    //若未进行交换 则说明剩余数列均已排列
		{
			break;
		}
	}
}

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

void TestBubbleSort()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestBubbleSort();
	return 0;
}

快速排序

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想是:任取待排序元素序列中的某元素作为基准值,按照排序码将待排序的集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值。

Hoare版本

数据结构-常见的排序算法,数据结构,排序算法,算法

Hoare版本实现代码

//Hoare
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//保证最后一个位置的数要比keyi小 要先进行--right
		//找比keyi小的
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//找比keyi大的
		while (left > right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

//QickSort
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

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

void TestQuickSort1()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	QuickSort1(a, 0, sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestQuickSort1();
	return 0;
}
挖坑法

数据结构-常见的排序算法,数据结构,排序算法,算法

挖坑法代码实现:

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && key <= a[right])
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && key >= a[left])
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return left;
}

//QickSort
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort2(a, begin, end);
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}

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

void TestQuickSort2()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	QuickSort2(a, 0, sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestQuickSort2();
	return 0;
}
前后指针法

数据结构-常见的排序算法,数据结构,排序算法,算法

前后指针代码实现:

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;
	
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}

//QickSort
void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort3(a, begin, end);
	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);
}

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

void TestQuickSort3()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	QuickSort3(a, 0, sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestQuickSort3();
	return 0;
}
快速排序优化

        1.在上述代码中,调用了GetMidi函数,GetMidi函数可以或者数列中接近中间位置的值,从而减少递归次数。

        2.在递归到小区间的时候,可以使用插入排序。

//QuickSort优化
void QuickSort4(int* a, int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	//小区间优化 对小区间不采用递归 使用插入排序 减少递归次数
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort1(a, begin, end);    //可以使三种方法任一钟
		QuickSort4(a, begin, keyi - 1);
		QuickSort4(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);   
	}
}
非递归实现快速排序

        在非递归实现快速排序时,需要调用之前的栈的实现。将每次需要排序的区间放入栈中,在获取排序区间后调用上述任一排序方法进行排序,直到所有区间 (区间大小大于0) 存入栈中并且将所有区间进行出栈获取区间后排序,此时排序完成。

//非递归实现QuickSort
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);
		int keyi = PartSort1(a, left, right);
		//[left,keyi-1]	keyi [keyi+1,right]
		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		if (left < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}
	STDestroy(&st);
}

归并排序

基本思想

        归并排序(Merge-Sort)建立在归并操作上的一种有效的排序算法,该算法采用分治法(Divide and Conquer)。将已有的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序即将两个有序表合成一个有序表,称为二路归并。

数据结构-常见的排序算法,数据结构,排序算法,算法

数据结构-常见的排序算法,数据结构,排序算法,算法

递归实现
/归并排序(递归实现)
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
	tmp = NULL;
}

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

void TestQuickSort3()
{
	int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
	MergeSort(a, 0, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main(){
	TestMergeSort();
	return 0;
}
非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap;
			//[begin1 end1] [begin2 end2]
			//如果第二组不存在 这两组不用进行归并
			if (begin2 >= n)
			{
				break;
			}

			//如果第二组越界 ,修正边界值
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, (2 * gap) * sizeof(int));
		}
		gap *= 2;
	}
	free(tmp);
}

非比较排序

计数排序

计数排序:又称鸽巢原理,是对哈希直接定址发的变形应用。

主要思想:统计相同元素出现次数根据统计的结果将序列回收到原来的序列中

数据结构-常见的排序算法,数据结构,排序算法,算法

 计数排序代码实现:

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for(int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
    //选取range 尽可能减少开辟的空间
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(count, 0, sizeof(int) * range);

	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[index++] = i + min;
		}
	}
}

排序算法复杂度及稳定性分析

数据结构-常见的排序算法,数据结构,排序算法,算法

数据结构-常见的排序算法,数据结构,排序算法,算法文章来源地址https://www.toymoban.com/news/detail-839010.html

到了这里,关于数据结构-常见的排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(55)
  • 【数据结构】——常见排序算法(演示图+代码+算法分析)

    目录 1.  常见排序算法 1.2 稳定性 2.  常见排序算法的实现 2.1 插入排序 2.1.1基本思想 2.1.2代码 2.1.4算法分析  2.2 希尔排序 2.2.1基本思想 2.2.2代码 2.2.3演示图  2.2.4算法分析 2.3 选择排序 2.3.1基本思想 2.3.2代码 2.3.3演示图 2.3.4算法分析 2.4 堆排序 2.4.1基本思想  2.4.2代码 2.4.3演示

    2024年02月11日
    浏览(72)
  • 【数据结构---排序】庖丁解牛式剖析常见的排序算法

    排序在我们生活中处处可见,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 常见的排序算法可以分为四大类:插入排序,选择排序,交换排序,归并排序;其中,插入排序分为直接插入排序和希尔排序;选择排序分为直接

    2024年02月16日
    浏览(62)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(46)
  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(66)
  • 【数据结构】七种常见的排序

    目录 1、排序的概念即运用 1.1、排序的概念  1.2、常见排序算法的分类 2、插入排序 2.1、排序原理 2.2、直接插入排序  2.3、希尔排序(缩小增量排序) 3、选择排序 3.1、直接选择排序  3.2、堆排序   4、选择排序 4.1、冒泡排序  4.2、快速排序  4.2.1、挖坑法实现快速排序 4

    2024年02月04日
    浏览(38)
  • 常见排序集锦-C语言实现数据结构

    目录 排序的概念 常见排序集锦      1.直接插入排序      2.希尔排序      3.选择排序      4.堆排序      5.冒泡排序      6.快速排序             hoare              挖坑法             前后指针法             非递归      7.归并排序             非递归 排序实现

    2024年02月12日
    浏览(48)
  • 数据结构——C语言实现常见排序(插入排序、希尔排序、选择排序、堆排序、冒泡排序)

    现在是北京时间2023年6月23日13点19分,度过了一个非常愉快的端午节。由于刚从学校回家,一下子伙食强度直升了个两三个档次。这也导致我的肠胃不堪重负,我也准备等会去健身房消耗一下盈余的热量。回到家陪伴爷爷走人生最后的阶段才是我这个暑假最重要的事情。自从

    2024年02月10日
    浏览(52)
  • 【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】

    目录 1.排序的概念及其运用 1.1排序的概念 1.2排序运用 1.3常见的七大排序 2.直接插入排序 2.1基本思想 2.2直接插入排序 2.3动图助解 2.4直接插入排序源码 2.5直接插入排序的特性总结 3.希尔排序( 缩小增量排序 ) 3.1希尔排序概念及思想 3.2希尔排序图解 3.3希尔排序源码 3.4希尔排序

    2024年02月13日
    浏览(53)
  • 【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】

    目录 前言 1.直接选择排序 1.1基本思想 1.2直接选择排序实现过程 1.3动图助解 1.4直接选择排序源码 2.堆排序 2.1堆排序的概念 2.2堆排序源码  选择排序有两种常见的【直接选择排序】、【堆排序】 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起

    2024年02月16日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包