当前位置： 首页 > article >正文

排序《数据结构》

article 2024/9/20 22:32:15

排序 《数据结构》

  • 1.排序的概念及其运用
    • 1.1 排序的概念
    • 1.2 排序运用
    • 1.3常见的排序算法
    • 1.4 排序动图演示
  • 2.常见排序算法的实现
    • 2.1 插入排序
    • 2.2希尔排序
    • 2.3 快排
      • 左边做keyi，右边先走，可以保证相遇位置比keyi小
    • 2.4 快速排序优化
      • 快排（非递归）
    • 2.6堆排序
    • 2.7 归并排序

1.排序的概念及其运用

1.1 排序的概念

1、排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2、稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
3、 内部排序：数据元素全部放在内存中的排序。
4、外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

1.2 排序运用

在这里插入图片描述

在这里插入图片描述

1.3常见的排序算法

在这里插入图片描述

1.4 排序动图演示

插入排序

void InsertSort(int* a,int n)//n为数组大小

在这里插入图片描述

希尔排序

void ShellSort(int* a,int n)//n为数组大小

在这里插入图片描述

选择排序

void SelectSort(int*a, int n);//n为数组大小

在这里插入图片描述

堆排序

voidAdjustDwon(int*a, int n, int parent);//向下调整
{
// 先假设左孩子小
int child = parent * 2 + 1;

while (child < n)  // 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 = parent * 2 + 1;
	}
	else
	{
		break;
	}
}
}
voidHeapSort(int*a, int n);

在这里插入图片描述

快排

void QuickSort(int* a,int n);

在这里插入图片描述

2.常见排序算法的实现

2.1 插入排序

基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，
直到所有的记录插入完为止，得到一个新的有序序列。

根据以上文字：
我们可以用（玩扑克牌来实例化）

在这里插入图片描述

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

插入排序特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

插入排序的实现

void InsertSort(int* a,int n)
{
for(int i=0;i<n-1;i++)//多趟
//一趟插入排序
 {
int end=i;
int tmp=a[end+1];
while(end>=0)
  {
  if(a[end]>tmp)
    {
    a[end+1]=a[end];
    end--;
    }
  else
  break;//以防tmp是数组中最小的数
   }
a[end+1]=tmp;
 }

}

2.2希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

在这里插入图片描述

希尔排序的特性总结：
 1. 希尔排序是对直接插入排序的优化。
 2. 当gap > 1时都是预排序，目的是让数组更接近于有序。 当gap == 1时，数组已经接近有序的了，这样就
    会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.  希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
    希尔排序的时间复杂度都不固定：大概是n^(1.3)

在这里插入图片描述

4. 稳定性：不稳定

void ShellSort(int* a,int n)
{
while(gap>1)
 {
 // +1保证最后一个gap一定是1
 // gap > 1时是预排序
 // gap == 1时是插入排序
  int gap=(3/n)+1;//第一趟
  for(int i=0;i<n-gap;i++)
  {
  int end=i;
  int tmp=a[end+1];
  while(end>=0)
     {
     if(a[end]>tmp)
     {
      a[end+1]=a[end];
      end-=gap;
     }
     else
      break;
   }
   a[end+1]=tmp;
  }

}

}

2.3 快排

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

特点总结：

快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定

1、hoare版本

void QuickSort(int*a,int left,int right)
{
 if(right<=left)
 {
 return ;
 }
 int begin=lef;
 int keyi=left;
 int end=right;
 while(begin<end)
 {
   while(begin<end&&a[keyi]<=a[begin])
   {
      begin++;
   }
   while(begin<end&&a[keyi]>=a[end])
   {
    end--;
   }
   Swap(&a[begin],&a[end]);//交换
}
Swap(&a[begin],a[keyi]);
keyi=begin;
QuickSort(a,left,keyi-1);
QuickSort(a,keyi+1,right);
}

左边做keyi，右边先走，可以保证相遇位置比keyi小

相遇场景分析：
L遇R: R先走,停下来，那么R停下的条件是比keyi小的位置,
L没找到大的，遇到R停下来了

在这里插入图片描述

 R遇L:

在这里插入图片描述

那么我们可以得出：keyi在左边，R先走，keyi在右边，L先走

2、挖坑法

在这里插入图片描述
3、双指针表达法
在这里插入图片描述

代码实现：

int partSort1(int* a, int left, int right)//双指针排序法
{
	int prve = left;
	int cur = prve + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[keyi] < a[cur] && ++prve != cur)
		{
			Swap(&a[prve], &a[cur]);
			cur++;
		}
		cur++;
	}
	Swap(&a[prve], &a[keyi]);
	return prve;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if ((right - left + 1) < 10)
	{
		insertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = partSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

2.4 快速排序优化

  1. 三数取中法选key
int order(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] > a[midi])
	{
		if (a[midi] > a[right])
		{
			return midi;
	   }
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else if(a[midi]<a[right])
	{
		return midi;
	}
	else
	{
		if (a[left] < a[right])
		{
			return right;
		}
		else
			return left;
	}
	
}
  1. 递归到小的子区间时，可以考虑使用插入排序
void insertSort(int* a, int n)
{
	
	for (int i = 0;i < n-1;i++)
	{
		int end=i;
		int tmp = a[end+1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		
		}
		a[end + 1] = tmp;
	}
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if ((right - left+1) < 10)//小区间优化
	{
		insertSort(a+left, right - left + 1);
	}
	else
	{
		int midi = order(a, left, right);
		Swap(&a[midi], &a[left]);
		int keyi = left;
		int begin = left, end = right;
		while (begin < end)
		{
			while (begin < end && a[end] >= a[keyi])
			{
				--end;
			}
			while (begin < end && a[begin] <= a[keyi])
			{
				++begin;
			}
			Swap(&a[begin], &a[end]);
		}


		Swap(&a[begin], &a[keyi]);
		keyi = begin;
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

快排（非递归）

用栈来代替递归

 先把区间left和right入栈，然后分隔区间，在令分隔的右区间先入栈，左区间后入栈（因为栈后进先出的原则），那么弹出来的就是左区间下标，在对坐下标进行处理，每一次出栈都代表着区间排序，
等栈为空时，那么排序就完成了

void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);//进栈
STPush(&st, left);//进栈
while()
left = STTop(&st);
STPop(&st);
right= STTop(&st);
STPop(&st);
int begin = left;
int end = right;
int keyi = begin;
while (begin < end)//交换
{

	while (begin < end && a[end] >= a[keyi])
	{
		end--;
	}
	while (begin < end && a[begin] <= a[keyi])
	{
		begin++;
	}
	Swap(&a[begin],&a[end]);
}
Swap(&a[keyi], &a[begin]);
   keyi = begin;
// [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);
}

2.6堆排序

直接选择排序的特性总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

实现代码：

void headsport(int* arr, int n)
{
	//时间复杂度O(N)
	for (int i = (n-1-1)/2;i >=0;i--)
	{
		AdjustDown(arr,n,i);//向下调整建堆
	}
	int end = n - 1;//取最后一位数据
    while (end > 0)
{
	Swap(&arr[0], &arr[end]);//交换
	AdjustDown(arr, end, 0);//在向下建堆
	end--;
  }
}

2.7 归并排序

基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

在这里插入图片描述

特性总结：

 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
 2. 时间复杂度：O(N*logN)
 3.  空间复杂度：O(N)
 4.  稳定性：稳定

代码实现:

void _mergeSort(int* a, int* tmp ,int begin, int end)
{
	if (end-begin<1)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//如果[begin,mid-1],[mid,end]有序就归并
	_mergeSort(a, tmp, begin, mid);
	_mergeSort(a, tmp, mid+1, end);
	//归并
	int begin1 = begin;
	int begin2 = mid+1;
	int end1 = mid;
	int end2 = end;
	int i = begin;
	while (begin1<=end1&&begin2<=end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = 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);
}

排序部分结束啦！！！感谢大家观看


http://www.kler.cn/news/305679.html

相关文章：

  • 面试问题001
  • 力扣第200题 岛屿数量
  • 前端工程化3：使用lerna管理多包
  • 一图读懂 若依后端
  • JavaScript web API part3
  • PCIe进阶之TL：Address Spaces, Transaction Types, and Usage
  • Java多线程1
  • Android13 Launcher3屏蔽桌面指示器
  • 外包干了半年，快要废了。。。
  • 【c++】类和对象详解
  • React18快速入门
  • 切换淘宝最新镜像源npm
  • VSCode学习笔记
  • Linux开发讲课44---linux性能查看命令和工具
  • 在职研生活学习--20240907
  • FaaS（Function as a Service）框架集成springboot
  • 【数据结构-一维差分】力扣2848. 与车相交的点
  • MySQL 8.0授权语法变更及解决方案‌
  • 点云深度学习系列：Sam2Point——基于提示的点云分割
  • 2024上半年国产操作系统卖疯了！麒麟4.9亿，统信1.9亿！
  • 架构设计：负责网络、定时、坐下、站起、重连等，支持多类游戏的无锁房间
  • Oracle发送邮件功能：配置自动化发信指南？
  • Redis搭建集成
  • 【ACM独立出版】第二届物联网与云计算技术国际学术会议 (IoTCCT 2024，9月27-29)
  • BookStack在线文档管理系统本地Docker部署与远程访问详细教程
  • 安全运维工程师学习路线
  • Unity实现自己的协程系统
  • RFB_modified模块的作用？和ASPP模块的区别？
  • GLSL 棋盘shader
  • STM32 HAL freertos零基础（六）计数型信号量