8.排序（直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序）的模拟实现

1.排序的概念及其运用

1.1排序的概念

  • 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

  • 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

  • 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

image-20230319215844914

2.常见排序算法的实现

2.1插入排序

1.直接插入排序

image-20230319215926363

// 最坏时间复杂度O(N^2) -- 原数组是逆序
// 最好时间复杂度O(N) -- 原数组是顺序有序

// 直接插入排序
void InsertSort(int* a, int n)
{
	// 在[0,end]范围内 插入第 end+1 个数据  并使[0, end+1]范围内的数据有序
	for (int i = 0; i < n - 1; ++i)
	{
        // 根据上面的图解来理解a[end] 和 tmp的下标
		int end = i;
		int tmp = a[end + 1];
        
        // 当end >= 0，那么就继续比较a[end]与tmp
		while (end >= 0)
		{
            // 将数组排列为一个升序数组
			if (a[end] > tmp)
			{
                // 如果前一个数据a[end]，大于后一个数据tmp
                // 直接用end位置的数据覆盖end + 1的数据，保持tmp不发生改变
				a[end + 1] = a[end];
                
                // 迭代
				--end;
			}
			else
			{
				break;
			}
		}
        
        // 当循环结束，end + 1处的数据是旧数据，需要使用tmp更新
		a[end + 1] = tmp;
	}
}

打印数组（便于我们来观察排序）

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

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

image-20230319220012509

// 情况二：
// 注：希尔排序的时间复杂度，太过复杂，我们可以默认理解希尔排序的时间复杂度为O(N^1.3)，
// 当数据量很大时，是比堆排序O(N*logN)略差的
// 希尔排序的时间复杂度为O(N^1.3)

// 这个函数采用的是多组并排排序的方法来实现希尔排序
void ShellSort(int* a, int n)
{
    // 将间隔为gap的数据分为一组
	int gap = n;
    
    // gap > 1  预排序
	// gap == 1 直接插入排序
    // 当while循环结束，说明缩小gap间隙最终为1，数组已经很接近有序了
	while (gap > 1)
	{
        // 下面是缩小间隙的两种方法，本文采用第二种
		// gap = gap / 2;
		gap = gap / 3 + 1;       
		
        // 当for循环结束，gap为n的所有组数据就排列好了
        // 下面for循环的算法就是，直接插入排序的算法，
        // 只是改变了a[end]和tmp下标之间的距离
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            
            // 直到end < 0才可以停止比较
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
	}
}

// 情况一： 分组进行排序
// 时间复杂度为：O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		// 间隔为gap的数据
        // 当j改变，就是代表一组数据排列完成，将要对下一组数据进行排序
		for (int j = 0; j < gap; ++j)
		{
			// 间隔为gap一组排序
			for (int i = j; i < n - gap; i += gap)
			{
				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;
			}
		}
	}
}

2.2 选择排序

1.直接选择排序

基本思想：

​ 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序:

  • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素

  • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换

  • 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

image-20230319220049930

// 直接选择排序最坏时间复杂度：O(N^2)
// 直接选择排序最好时间复杂度：O(N^2)
void SelectSort(int* a, int n)
{
    // 初始化begin和end下标
	int begin = 0, end = n - 1;
    // 只有begin小于end时，才可以继续
	while (begin < end)
	{
		// 选出最小的放begin位置
		// 选出最大的放end位置
        
        // 将标识最大值和最小值的下标都初始化为begin
		int mini = begin, maxi = begin;
        // 当for循环结束时，a[mini]为最小值，a[maxi]为最大值，在[begin,end]范围内
		for (int i = begin + 1; i <= end; ++i)
		{
            // 如果为真，那么i下标所在的元素就是最大值，所以更改最大值的下标maxi为i
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

        // 1.现将最小值a[mini]与初始位置的值进行交换
		Swap(&a[begin], &a[mini]);
		
        // 修正一下maxi
        // 如果初始位置的值是最大值，由于上面进行了交换,所以此时最大值的下标为mini
        // 因此，将mini赋值给maxi
		if (maxi == begin)
			maxi = mini;

        // 2.将最大值a[maxi]与末尾位置的值进行交换
		Swap(&a[end], &a[maxi]);
        
        // 迭代
		++begin;
		--end;
	}
}

2.堆排序

void AdjustDown(int* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild + 1 < n && a[minChild + 1] > a[minChild])
		{
			minChild++;
		}

		if (a[minChild] > a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// O(N*logN)
void HeapSort(int* a, int n)
{
	// 大思路：选择排序，依次选数，从后往前排
	// 升序 -- 大堆
	// 降序 -- 小堆
	// 建堆 -- 向下调整建堆 - O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// 选数 N*logN
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}
  • 关于堆排序请查看作者的另一篇文章，堆排序。

2.3 交换排序

1.冒泡排序

image-20230319220214966

// 交换排序（冒泡排序）
// 冒泡排序最坏情况的时间复杂度：O(N^2)
// 冒泡最好情况的时间复杂度：O(N)
void BubbleSort(int* a, int n)
{
    // n是数组中元素的个数
    // 这个for代表趟数
	for (int j = 0; j < n; ++j)
	{
        // 每一趟都会将exchange初始化为0
        // 如果还有a[i - 1] > a[i]存在，那么exchange就会被修改为1
        // 但是最后一趟时，数组已经是一个有序的数组了，因此exchange不会被修改
		int exchange = 0;
        
        // for代表了一趟中，a[i]与a[i - 1]迭代比较
		for (int i = 1; i < n - j; ++i)
		{
            // a[i - 1]是下标较小的元素，a[i]是下标较大的元素
            // 当这个条件为真，那么交换两个元素的位置
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
        
		if (exchange == 0)
		{
			break;
		}
	}
}

2.快速排序

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

1.hoare版本

image-20230319220240821

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// PartSort函数，是一趟（想要利用上述的方法将这个数组的元素排序，还需要很多趟，具体看后续的解释）
// 返回left和right相遇节点的下标
int PartSort(int* a, int left, int right)
{
    // 将左侧的下标定义为keyi下标
	int keyi = left;
    
    // 当left等于right说明两个人相遇了，那么就停止循环
	while (left < right)
	{
		// Right需要找比a[keyi]小的数
        // 因此，如果a[right] >= a[keyi]为真，那么就继续循环
        // 注意：在循环的过程中一定要保证left < right，否则就没有意义了
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// Lift需要找比a[keyi]大的数
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

        // 如果此时left < right为真，那么就交换a[left]和a[right]
		if (left < right)
			Swap(&a[left], &a[right]);
	}

    // 此时，left和right都是相遇节点的下标，
    // 使用left赋值给meeti
	int meeti = left;

    // 将相遇节点的数据与keyi下标的数据进行交换
	Swap(&a[meeti], &a[keyi]);

	return meeti;
}

image-20230319220322585

// 快速排序
void QuickSort(int* a, int begin, int end)
{
    // 必须满足begin小于end
    // 否则，就返回
	if (begin >= end)
	{
		return;
	}

    // 先使用PartSort()函数对[begin,end]区间的数进行一趟排序
    
    // PartSort()的返回值是meeti，也就是相遇节点的下标，将其存放到keyi
	int keyi = PartSort(a, begin, end);
    // 以keyi为分割点，将[begin,end]区间分割为下面两个区间
	// [begin, keyi-1] keyi [keyi+1, end]

    // 左区间递归，和右区间递归
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}
快速排序的优化

image-20230319220354572

// 优化之后的代码

// 三数取中
int GetMidIndex(int* a, int left, int right) 
{
    // 数组中间的数的下标就是mid
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
        // 此时a[mid]已经大于a[left]，那么只要满足a[mid] < a[right]，就返回a[mid]的下标
        // 满足a[left] > a[right],也就是a[mid]>a[left] > a[right],就返回a[left]的下标
        // 都不满足，也就是a[right]<a[left]<a[mid],就返回a[right]的下标
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


// [left, right] -- O(N)
// hoare
// PartSort1函数，是一趟(单趟排序)
int PartSort1(int* a, int left, int right) 
{
	// 三数取中，得到left，right，left + (right - left) / 2中，中间大的哪个数
	int mid = GetMidIndex(a, left, right);
    // 此处的mid就是指中间大的哪个数的下标
	//printf("[%d,%d]-%d\n", left, right, mid);

    // 将中间大的数，放在数组的最左侧
	Swap(&a[left], &a[mid]);

    // keyi依旧是最左侧的数的下标（继承优化前的代码，不需要做出改动）
	int keyi = left;
	while (left < right)
	{
		// R找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// L找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		if (left < right)
			Swap(&a[left], &a[right]);
	}

	int meeti = left;

	Swap(&a[meeti], &a[keyi]);

	return meeti;
}


// 快速排序函数
void QuickSort(int* a, int begin, int end)   // 分区间递归
{
    // 必须保证begin >= end为假，才可以继续迭代
	if (begin >= end)
	{
		return;
	}

    // 8的取值，参考经验，8比较合适
    // 当[begin,end]区间的元素小于等于8时，这个时候再分小区间，后三层小区间有很多个
    // 为了减小栈的开销，当end - begin <= 8为真时，采用直接插入排序来将数组进行排序（此时的数组已经很接近有序了，因此使用直接插入排序，并不会降低太多的效率）
	if (end - begin <= 8) 
	{
        // 小区间优化，最后三层用直接插入排序
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
        // 先使用PartSort()函数对[begin,end]区间的数进行一趟排序
    
    	// PartSort()的返回值是meeti，也就是相遇节点的下标，将其存放到keyi
		int keyi = PartSort1(a, begin, end);
        // 以keyi为分割点，将[begin,end]区间分割为下面两个区间
		// [begin, keyi-1] keyi [keyi+1, end]

        // 迭代左区间
        // 迭代右区间
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}
2.挖坑法（重要）

image-20230319220421603

// 三数取中
int GetMidIndex(int* a, int left, int right) 
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


// 挖坑法
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

    // 将key值初始化为a[left]
    // 将坑位的下标hole初始化为left
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		// 右边找小，填到左边坑
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
        // 此时right对应的下标成为新的坑位
		hole = right;

		// 左边找大，填到右边坑
		while (left < right && a[left] <= key)
		{
			++left;
		}

		a[hole] = a[left];
		hole = left;
	}

    // 当left和right相遇，将key值放入这个坑位（最后的这个坑位）
	a[hole] = key;
	return hole;
}


// [begin, end]
void QuickSort(int* a, int begin, int end)   // 分区间递归
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin <= 8) // 8的取值，参考经验，8比较合适
	{
		InsertSort(a + begin, end - begin + 1);// 小区间优化，最后三层用插入排序
	}
	else
	{
		int keyi = PartSort2(a, begin, end);
		//[begin, keyi-1] keyi [keyi+1, end]

		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}
3.前后指针法
  • 本质就是cur指向的值小于key，prev指向的值大于key，那么交换cur和prev所指向的值

image-20230319220445586

// 三数取中
int GetMidIndex(int* a, int left, int right) 
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}


// 前后指针法
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		// 找小
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[keyi], &a[prev]);

	return prev;
}


// [begin, end]
void QuickSort(int* a, int begin, int end)   // 分区间递归
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin <= 8) // 8的取值，参考经验，8比较合适
	{
		InsertSort(a + begin, end - begin + 1);// 小区间优化，最后三层用插入排序
	}
	else
	{
		int keyi = PartSort3(a, begin, end);
		//[begin, keyi-1] keyi [keyi+1, end]

		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

3.快速排序（非递归的方法）

image-20230319220509273

void QuickSortNonR(int* a, int begin, int end)
{
    // 栈结构对象在堆上面开辟空间，不用担心栈溢出
	ST st;  
    // 初始化栈
	StackInit(&st);
    // 将区间[begin,end]的左右断点存储到栈对象中
	StackPush(&st, begin);
	StackPush(&st, end);

    // 直到栈为空，循环结束（意味着所有的小区间都已经排序完毕了）
	while (!StackEmpty(&st))
	{
        // 因为压栈的时候是先压入的左端点，再压入右端点（都是下标）
        // 所以，从栈顶拿出数据时，是先拿出右端点，再拿出左端点（都是下标）
		int right = StackTop(&st);
		StackPop(&st);

		int left = StackTop(&st);
		StackPop(&st);

		/*if (left >= right)       // 在取出时，判断区间是否满足排序要求
		{
			continue;
		}*/

        // 根据拿出的区间断点，对这个区间的数据进行一趟排序
		int keyi = PartSort3(a, left, right);
        
        // 排序完之后，得到下标keyi，根据下标keyi将之前的区间重新分为两个新区间
        // 再将两个新区间的左右端点入栈，就可以重复上述的操作，完成所有区间的排序
		// [left, keyi-1] keyi [keyi+1,right]

        // 在存入时，判断区间是否满足存入要求，避免无效存储，和取出判断
		if (keyi + 1 < right)     
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
	
        // 在存入时，判断区间是否满足存入要求，避免无效存储，和取出判断
		if (left < keyi- 1)     
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
	}

    // 最后，销毁栈对象开辟的空间，防止内存泄漏
	StackDestroy(&st);
}

2.4 归并排序

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and

Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有

序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

image-20230319220539106

归并排序（递归的方法

image-20230319220600395

归并排序（递归的方法）

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

// 归并排序（递归的方法）
// 函数_MergeSort是函数MergeSort的一部分
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    // 必须保证begin >= end为假，否则就直接返回
	if (begin >= end)
		return;

    // 取数组的中间下标，将数组分为两个区间
	int mid = (end + begin) / 2;
	// [begin, mid] [mid+1, end]

    // 左区间迭代和右区间迭代
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
    
    // 迭代完之后，此时有无数个被分裂的小区间，每个区间只有一个数

	// 归并 取两个区间中小的数值尾插到tmp中（tmp是一个临时数组，临时存放这些归并的数据的）
    // 注：因为左右区间是迭代的，所以begin,mid,end的大小对应相应的迭代，当回到迭代最初的地方
    // 那么[begin, mid] [mid+1, end]这两个区间的数已经是有序的了
	// [begin, mid] [mid+1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
    
    // 两个区间的数归并时，必须满足 begin1 <= end1 && begin2 <= end2
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
        // 取两个区间中较小的数尾插到tmp中
		if (a[begin1] <= a[begin2])
		{
            // 后置++，先使用，后++
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

    // 如果区间2的数尾插完了，但是区间1的数没有尾插完，那么这里将区间一剩余的数尾插到tmp中
	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;
	}

    // void _MergeSort(int* a, int begin, int end, int* tmp)
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

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

void TestMergeSort()
{
	int a[] = { 100, 56, 25, 86, 99, 72, 66 };
	int n = sizeof(a) / sizeof(int);
	MergeSort(a, n);
	PrintArray(a, n);
}

int main()
{
	TestMergeSort();
	return 0;
}
memcpy()的用法

在C语言中，memcpy() 函数用于在内存之间复制一定数量的字节。它的原型如下：

void *memcpy(void *dest, const void *src, size_t n);
  • dest 是目标内存区域的指针，指向要复制到的位置。
  • src 是源内存区域的指针，指向要复制的数据的起始位置。
  • n 是要复制的字节数。

memcpy() 函数将源内存区域中的数据复制到目标内存区域中。它返回目标内存区域的起始位置（即 dest 指针），这使得可以将 memcpy() 作为一个表达式的一部分来使用。

以下是一个示例代码，演示了如何使用 memcpy() 函数复制内存中的数据：

#include <stdio.h>
#include <string.h>

int main() {
    char src[] = "Hello, world!";
    char dest[20];

    // 将 src 中的数据复制到 dest 中
    memcpy(dest, src, strlen(src) + 1);

    // 打印复制后的字符串
    printf("Copied string: %s\n", dest);

    return 0;
}

在这个示例中，我们将字符串 "Hello, world!" 从源内存区域 src 复制到目标内存区域 dest 中，然后打印出复制后的字符串。

归并排序（非递归的方式）

image-20230319220643122

image-20230319220715925

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
        // 首次循环时，每个区间只有一个数，此时gap=1
        // 当归并一次之后，每个区间就有两个数，那时就将gap扩大两倍
		// gap个数据  gap个数据归并
        
        // gap每改变一次，进行一次for循环
		for (int j = 0; j < n; j += 2 * gap)
		{
			// 归并两个区间 取较小的值尾插到tmp
            // j为区间一的区间为[j,j + gap - 1]
            // 区间二的区间为[j + gap,j + 2 * gap - 1]
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
            
			// 当归并到最后两组的数据，并且第一组就完全越界了
            // 那么不需要进行归并，直接跳出循环就可以
			if (end1 >= n)
			{
				printf("[%d,%d]", begin1, n-1);
				break;
			}

			// 第二组全部越界，直接跳出循环就可以
            // 此时的第一组数据必然是有序的
			if (begin2 >= n)
			{
				printf("[%d,%d]", begin1, end1);
				break;
			}

			// 第二组部分越界
			if (end2 >= n)
			{
				// 修正一下end2，继续归并（第二组最后一个数的下标，最大为n-1）
				end2 = n - 1;
			}

			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			int i = j;
			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+j, tmp+j, (end2-j+1)*sizeof(int));
		}

        // 扩大区间范围
		gap *= 2;
		printf("\n");
	}

	free(tmp);
	tmp = NULL;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/534070.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

node.js-入门

node.js-入门

定义 Node.js是一个跨平台Javascript运行环境&#xff0c;使开发者可以搭建服务器端的Javascript应用程序 作用&#xff1a;使用Node.js编写服务器端程序 1&#xff09;编写数据接口&#xff0c;提供网页资源浏览功能等 2&#xff09;前端工程化&#xff1a;为后续学习Vue和…
阅读更多...
DSP笔记8-通用GPIO

DSP笔记8-通用GPIO

电源类 AD引脚类 系统相关JTAG 时钟 GPIO (general purpose input output)复用&#xff0c; 复用&#xff0c;I/O引脚&#xff0c;外设的功能引脚&#xff0c; 88个GPIO引脚&#xff0c;通用的输入输出口&#xff0c;功能复用的。 GPIO特点 输入电平与TTL电平兼容。>2.0V…
阅读更多...
记一次IP访问MySQL失败多次被自动锁定导致无法连接问题，解决方法一条SQL足以。

记一次IP访问MySQL失败多次被自动锁定导致无法连接问题，解决方法一条SQL足以。

&#x1f469;&#x1f3fd;‍&#x1f4bb;个人主页&#xff1a;阿木木AEcru &#x1f525; 系列专栏&#xff1a;《Docker容器化部署系列》 《Java每日面筋》 &#x1f4b9;每一次技术突破&#xff0c;都是对自我能力的挑战和超越。 前言 今天下午还在带着耳机摸鱼&#xff…
阅读更多...
企业售后技术支持如何管理？远控行为如何追溯？

企业售后技术支持如何管理？远控行为如何追溯？

随着企业业务规模的不断扩大&#xff0c;远程技术支持需求自然会不断增加&#xff0c;在这个环节中就尤其容易出现管理上的缺位&#xff0c;进而造成不必要的客诉纠纷&#xff0c;影响品牌形象。 在这样的客观环境下&#xff0c;原始的“小作坊”式管理显然已经不再合适&#…
阅读更多...
Vue3 使用ElementUI 显示异常

Vue3 使用ElementUI 显示异常

element提供的样例不能正常显示&#xff0c;需要进行配置 1.npm install element-plus --save 2.main.js // main.ts import { createApp } from vue import ElementPlus from element-plus //全局引入 import element-plus/dist/index.css import App from ./App.vue const …
阅读更多...
Python程序设计 字符类型及其操作

Python程序设计 字符类型及其操作

1. 提取身份证号性别 通过身份证的第17位也就是倒数第二位的数字可以辨别该身份证所属人的性别,奇数为男性,偶数为女性。 输入身份证号&#xff0c;第17位若是偶数&#xff0c;输出性别女&#xff0c;否则输出性别男 1.通过input()函数接收用户输入的身份证号&#xff0c;将其…
阅读更多...
API管理平台：你用的到底是哪个？

API管理平台：你用的到底是哪个？

Apifox是不开源的&#xff0c;在github的项目只是readme文件&#xff0c;私有化需要付费。当然saas版目前是免费使用的。 一、Swagger 为了让Swagger界面更加美观&#xff0c;有一些项目可以帮助你实现这一目标。以下是一些流行的项目&#xff0c;它们提供了增强的UI和额外的功…
阅读更多...
.NET邮箱API发送邮件的流程？如何使用API？

.NET邮箱API发送邮件的流程？如何使用API？

.NET邮箱API发送邮件需要哪些步骤&#xff1f;怎么配置API发信&#xff1f; 电子邮件已经成为我们日常工作和生活中不可或缺的一部分。对于开发人员来说&#xff0c;掌握如何使用API发送邮件是一项非常实用的技能。AokSend将详细介绍使用.NET邮箱API发送邮件的流程&#xff0c…
阅读更多...
Oracle ORA-28547:connection to server failed,probable Oracle Net admin error

Oracle ORA-28547:connection to server failed,probable Oracle Net admin error

使用Navicat连接oracle数据库时报ORA-28547错误 因为Navicat自带的oci.dll并不支持oracle11g&#xff0c;需要去官网下载支持的版本。 1.去oracle下载对应的oci.dll文件 下载地址&#xff1a;Oracle Instant Client Downloads 可以用 11.2.0.4 2. 复制刚下载下来的instant…
阅读更多...
Linux进阶篇：firewalld详解——firewalld 的概念作用以及如何使用

Linux进阶篇：firewalld详解——firewalld 的概念作用以及如何使用

Linux firewalld详解——firewalld 的概念&作用以及如何使用 在这篇文章中&#xff0c;我们将详细介绍Linux系统中的firewalld&#xff0c;它是一款强大的防火墙管理工具。我们将介绍firewalld的基本概念和作用&#xff0c;并通过实例演示如何使用它来保护您的系统。 一、…
阅读更多...
轻松记录收支明细，支持查看所有记录并统计某个账户的开销，轻松掌握开销明细

轻松记录收支明细，支持查看所有记录并统计某个账户的开销，轻松掌握开销明细

在繁忙的现代生活中&#xff0c;我们时常为琐碎的开销所困扰&#xff0c;难以清晰掌握自己的财务状况。为了帮助你更好地管理个人财务&#xff0c;我们推出了一款全新的智能收支记录工具&#xff0c;让你轻松记录每一笔开销&#xff0c;并实时统计账户信息&#xff0c;从此告别…
阅读更多...
【论文阅读】MCTformer: 弱监督语义分割的多类令牌转换器

【论文阅读】MCTformer: 弱监督语义分割的多类令牌转换器

【论文阅读】MCTformer: 弱监督语义分割的多类令牌转换器 文章目录 【论文阅读】MCTformer: 弱监督语义分割的多类令牌转换器一、介绍二、联系工作三、方法四、实验结果 Multi-class Token Transformer for Weakly Supervised Semantic Segmentation 本文提出了一种新的基于变换…
阅读更多...
LeetCode——622设计循环队列

LeetCode——622设计循环队列

. - 力扣&#xff08;LeetCode&#xff09;. - 备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/design-circular-queue/ 1.题目 设计你的循环队列实现。 循环队列是一…
阅读更多...
成都污水处理设备厂家哪家好？

成都污水处理设备厂家哪家好？

在成都地区&#xff0c;选择一家专业可靠的一体化污水处理设备厂家对于实现环保目标至关重要。在这方面&#xff0c;四川博水环保科技有限公司无疑是一个值得推荐的选择。 博水办公楼外景 四川博水环保科技有限公司是一家领先的一体化污水处理设备供应商&#xff0c;专注于为各…
阅读更多...
执行docker-compose up的时候报错network with driver “bridge“

执行docker-compose up的时候报错network with driver “bridge“

执行docker-compose up的时候报错network with driver “bridge” (base) [rootVM-100-213-centos ~/composetest]# docker-compose up -d Creating network “composetest_default” with the default driver ERROR: could not find an available, non-overlapping IPv4 addre…
阅读更多...
docker基本的掌握

docker基本的掌握

前言&#xff1a;先要了解docker是干什么的&#xff0c; 1掌握基本概念&#xff0c;如;镜像&#xff0c;容器&#xff0c;数据卷 2知道使用常用命令 简易图; 补充&#xff1a; 默认情况下&#xff0c;每次重启虚拟机我们都需要手动启动Docker和Docker中的容器。通过命令可以实…
阅读更多...
计算机网络-TCP连接建立阶段错误应对机制

计算机网络-TCP连接建立阶段错误应对机制

错误现象 丢包 网络问题&#xff1a;网络不稳定可能导致丢包&#xff0c;例如信号弱或干扰强。带宽限制可能导致路由器或交换机丢弃包&#xff0c;尤其是在高流量时段。网络拥塞时&#xff0c;多个数据流竞争有限的资源&#xff0c;也可能导致丢包。缓冲区溢出&#xff1a;TC…
阅读更多...
【深度学习】最强算法之：Transformer

【深度学习】最强算法之：Transformer

Transformer 1、引言2、Transformer2.1 引言2.2 核心概念2.3 应用2.4 算法公式2.5 代码示例 3、总结 1、引言 小屌丝&#xff1a;鱼哥&#xff0c;昨天的感受咋样 小鱼&#xff1a;啥感受啊&#xff1f; 小屌丝&#xff1a;你确定不知道&#xff1f; 小鱼&#xff1a;我… 小屌…
阅读更多...
查看每月网站的带宽以及网站访问记录

查看每月网站的带宽以及网站访问记录

接到一位用户反馈想要了解知道在带cPanel面板的虚拟主机中如何查看每个网站使用的带宽数值以及网站访问记录&#xff0c;这边私信进行沟通了解到他当前使用的是Hostease 的LInux虚拟主机&#xff0c;由于是属于新手&#xff0c;对于cPanel面板也不是很了解&#xff0c;因而在论…
阅读更多...
Python爬虫之Scrapy框架基础

Python爬虫之Scrapy框架基础

Scrapy爬虫框架介绍 文档 英文文档中文文档 什么是scrapy 基于twisted搭建的异步爬虫框架. scrapy爬虫框架根据组件化设计理念和丰富的中间件, 使其成为了一个兼具高性能和高扩展的框架 scrapy提供的主要功能 具有优先级功能的调度器去重功能失败后的重试机制并发限制ip使用次…
阅读更多...
最新文章

Copyright @ 2022~2023