数据结构---排序算法（2）

二分查找（数组本身就是有序的）：

非递归：

例如：

（1）先定位left和right,将数组一分为二，选取中间位置定为right

（2）比较中间位置和要寻找的数，如果中间位置大于要寻找的数则在中间数左边寻找要寻找的数

，如果中间位置小于要寻找的数则在中间数右边寻找要寻找的数

（3）如果中间位置大于要寻找的数则在中间数左边寻找要寻找的数，将right定位为中间位置加一除以二，将中间位置的左边重新看为数组，将数组一分为二

（4）再比较right下标的数和要寻找的数的大小，重复上述步骤，直到找到或left=right

int BinarySearch(int* arr, int len, int val)
{
	int left = 0;
	int right = len / 2;
	while (right >= 1)
	{
		if (arr[right] == val)
		{
			return right;
		}
		if (arr[left] == val)
		{
			return left;
		}
		if (arr[right] > val)
		{
			right = (right + 1) / 2;
		}
		else
		{
			left = right;
			right = (left + len) / 2;
		}
	}
}

递归：

int BinarySearch0(int* arr, int left, int right, int len,int val)
{
	if (arr[right] == val)
	{
		return right;
	}
	else if (arr[left] == val)
	{
		return left;
	}
	else if (arr[right] > val)
	{
		BinarySearch0(arr, left, (left + right) / 2,len, val);
	}
	else if (arr[right] 

• 时间复杂度：

  • 平均情况：O (log n)
  • 最坏情况：O (log n)
  • 最好情况：O (1)（目标元素恰好在中间位置）

• 空间复杂度：

  • 迭代实现：O (1)（仅需常数级额外空间）
  • 递归实现：O (log n)（递归调用栈的深度）

归并排序：

将数组分为n个归并段，分别将两个归并段内的数据排列有序，再将归并段范围扩大排列有序，直到只存在一个归并段

非递归：

void Merge(int* arr, int len, int gap)
{
	int left1 = 0;
	int right1 = left1 + gap - 1;
	int left2 = right1 + 1;
	int right2 = left2 + gap - 1 > len - 1 ? len - 1 : left2 + gap - 1;
	int* tmp = (int*)malloc(len * sizeof(int));
	int j = 0;
	//存在两个归并段
	while (left2 len - 1 ? len - 1 : left2 + gap - 1;
	}
	//不存在两个归并段
	for (int i = left1; i 

递归：

void Merge0(int* arr, int left1, int right1,int left2,int right2 , int len,int gap,int* tmp,int j)
{
	//存在两个归并段
	if(left2  len - 1 ? len - 1 : left2 + gap - 1;
		Merge0(arr, left1, right1, left2, right2, len, gap, tmp, j);
	}
	//不存在两个归并段
	else
	{
		for (int i = left1; i  len - 1 ? len - 1 : left2 + i - 1;
		int j = 0;
		Merge0(arr, left1, right1, left2, right2,len, i,tmp,j);
	}
}

• 时间复杂度：

  • 平均情况：O (n log n)
  • 最坏情况：O (n log n)
  • 最好情况：O (n log n)

• 空间复杂度：O (n)（需要额外的数组存储合并结果）

• 稳定性：稳定（相等元素的相对位置在排序后保持不变）

堆排序：

堆排序时分为两种情况：

大堆顶和小堆顶：

大堆顶：根节点始终大于他的左孩子和右孩子的情况

小堆顶：根节点始终小于他的左孩子和右孩子的情况

（1）首先将每一个根节点和左右孩子变幻为大堆顶或小堆顶

（2）再将树的根节点和最后一个叶子节点交换位置

（3）重复上述步骤（1）（2）直至有序

void ADjust(int* arr,int begin,int len)
{
	int tmp = arr[begin];
	while (2*begin+1 tmp)
		{
			arr[begin] = arr[maxindex];
			begin = maxindex;
		}
		else
			break;
	}
	arr[begin] = tmp;
}
void HeapSort(int* arr, int len)
{
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)
		ADjust(arr, i, len);
	Swap(&arr[0], &arr[len - 1]);
	len--;
	while (len > 0)
	{
		ADjust(arr, 0, len);
		Swap(&arr[0], &arr[len - 1]);
		len--;
	}
}

• 时间复杂度：

  • 平均情况：O (n log n)

  • 最坏情况：O (n log n)

  • 最好情况：O (n log n)

• 空间复杂度：O (1)（原地排序，仅需常数级额外空间）

• 稳定性：不稳定（堆调整过程中可能改变相等元素的相对位置）

希尔排序：

（1）将数组分为n组，且跳跃性分组例如下图，以五个跳跃为一组进行排序

（2）再将跳跃数缩小为3，进行排序

（3）直至跳跃数缩小为1，进行排序后，整个数组已经大致有序再对数组进行快排，即可得到有序数组

void Shell(int *arr, int len, int gap){
for(int i=gap; i=0; j=j-gap) {
if(arr[j] > tmp) {
arr[j+gap] = arr[j];
}
else {
break;
}
}
arr[j+gap] = tmp;
}
}
void Shell_Sort(int *arr, int len){
int gap[] = {5,3,1};//缩小增量数组
for(int i=0; i

• 时间复杂度：

  • 平均情况：取决于增量序列，通常为 O (n^1.3)

  • 最坏情况：O (n²)（当增量序列为 1,2,4,… 时）

  • 最好情况：O (n)（当增量序列选择适当时）

• 空间复杂度：O (1)（原地排序，仅需常数级额外空间）

• 稳定性：不稳定（不同增量轮次的插入排序可能改变相等元素的相对位置）

文章来源于互联网:数据结构—排序算法（2）

相关推荐: AIGC（生成式AI）试用 24 — 跟着清华教程学习 – 普通人如何抓住DeepSeek红利

目标：继续学习 个人理解： – 扩展生存的空间：广度和深度 – 更多的奇思妙想得到更快的、更充分的、更有逻辑的验证 – “如何提问”仍是最关建的问题：学会问问题和挑选答案     > 学会发现问题、有解决问题的意愿、对问题有明确的期望     > …