七大经典比较排序算法

1. 插入排序 (⭐️⭐️)

🌟 思想：

直接插入排序是一种简单的插入排序法，思想是是把待排序的数据按照下标从小到大，依次插入到一个已经排好的序列中，直至全部插入，得到一个新的有序序列。例如：我们玩扑克牌的时候，每次摸进一张的新的牌我们会将其插入到合适的位置。

思路： 我们假设第一个数据有序，从第二个元素开始进行插入（最开始把前面第一个数据看作一个有序的区间），从后向前依次寻找合适位置，每次插入的时候如果当前位置不合适将当前位置向后移动一位。

InsertSort 实现：

// 插入排序
void InsertSort(int * nums , int size) {
	for (int i = 0; i < size - 1; i++) {
		// 把 [0 , end] 看作有序区间
		int end = i;
		// nums[end + 1]为需要插入的元素 使用 temp 保存
		int temp = nums[end + 1];
		// 找插入位置
		while (end >= 0 && temp < nums[end]) {
			// 把当前元素向后移动
			nums[end + 1] = nums[end];
			end--;
		}
		// 来到这里说明 temp >= nums[end] 找到插入位置
		// 插入
		nums[end + 1] = temp;
	}
}

我们可以思考一下极端情况：

  • 假设数据为 3 5 7，end 为 1，temp = 7，所以 temp < nums[end] 为 false 循环结束，执行 nums[end + 1] = temp，相当于 nums[2] = 7 而当前位置本来就是 7，不会有影响。
  • 假设数据为 3 5 1，end 为 1，temp = 1，当前 temp < nums[end] 将数据向后移动直至 3 3 5，当 end = -1循环结束，nums[end + 1] = temp 相当于 nums[0] = temp，所以最终结果为 1 3 5。

总结：

  1. 元素结合越接近有序，直接插入排序算法的时间效率就越高。
  2. 最坏时间复杂度： O ( N 2 ) O(N^2) O(N2)
  3. 接近有序或已经有序时间复杂度： O ( N ) O(N) O(N)
  4. 空间复杂度： O ( 1 ) O(1) O(1)

2.希尔排序 (⭐️⭐️⭐️)

🌟 思想：

希尔排序又称缩小增量法。希尔排序的基本思想是：先选定一个 gap (整数)，把待排序中的数据分成 gap 组（gap 距离的为同一组），并对每一组内的的数据进行插入排序。

假设 gap = 3 将下面的 10 个数分成 3 组。 {9 , 5 , 8 , 5}、{1 , 7 , 6}、{2 , 4 , 3}分别进行插入排序。当 gap 不为 1 时都是预排序，当 gap = 1时是插入排序，因为当数据接近有序的时候，插入排序的效率很高。

在这里插入图片描述

1️⃣ gap 组希尔排序： 这是希尔排序的 gap 组的一种写法，按上面的图来说，这样的写法是先走完红色组，再走蓝色组……

void ShellSort (int * nums , int size) {
	assert(nums);
	// 假设 gap = 3
	int gap = 3;
	for (int j = 0; j < gap; j++) {
		for (int i = j; i < size - gap; i+=gap) {
			int end = i;
			int temp = nums[end + gap];
			while (end >= 0 && temp < nums[end]) {
				nums[end + gap] = nums[end];
				end -= gap;
			}
			nums[end + gap] = temp;
		}
	}
}

2️⃣ gap 组希尔排序：第二种在上一种写法上进行了优化，原来是一组走完再走下一组，现在是一组一组间交替的去插入排序。

void ShellSort (int * nums , int size) {
	assert(nums);
	// 假设 gap = 3
	int gap = 3;
	for (int i = 0; i < size - gap; i++) {
		int end = i;
		int temp = nums[end + gap];
		while (end >= 0 && temp < nums[end]) {
			nums[end + gap] = nums[end];
			end -= gap;
		}
		nums[end + gap] = temp;
	}
}

ShellSort 实现：当 gap > 1 的时候都是预排序（是为了让数据更接近有序，因为直接插入排序当数据接近有序的时候是 O ( N ) O(N) O(N)），而这里 gap / 3 + 1 是为了最后一次让 gap = 1。 当 gap 越大的时候大的数会越快的到后面，但是数组越不接近有序。当 gap 越小的时候，数组越接近有序。当 gap = 1 就是直接插入排序。

void ShellSort (int * nums , int size) {
	assert(nums);
	
	int gap = size;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < size - gap; i++) {
			int end = i;
			int temp = nums[end + gap];
			while (end >= 0 && temp < nums[end]) {
				nums[end + gap] = nums[end];
				end -= gap;
			}
			nums[end + gap] = temp;
		}
	}
}

总结：

  1. 时间复杂度 ~ O ( N 1.3 ) O(N^{1.3}) O(N1.3)
  2. 空间复杂度： O ( 1 ) O(1) O(1)
  3. 希尔排序是插入排序的优化

3. 选择排序 (⭐️)

🌟 思想：

每一次从待排序的数据种选出最小或者最大的元素下标，存放在当前序列的起始位置，直到排序结束。

请添加图片描述

1️⃣SelectSort 实现：

// 选择排序
void SelectSort(int * nums , int size) {
	assert(nums);
	for (int i = 0; i < size - 1; i++) {
		int minIndex = i + 1;
		// 选数
		for (int j = i + 1; j < size; j++) {
			if (nums[j] < nums[minIndex ]) {
				minIndex = j;
			}
		}
		// 交换
		int temp = nums[minIndex];
		nums[minIndex] = nums[i];
		nums[i] = temp;
	}
}

2️⃣ SelectSort 优化： 我们可以同时选出两个数一个最大一个最小，把最小的组交换到当前区间的左边，最大的交换到区间的右边。

void SelectSort(int * nums , int size) {
	assert(nums);
	int left = 0;
	int right = size - 1;
	while (left < right) {
		// 最小值下标默认从左区间开始
		int maxIndex = left;
		int minIndex = left;
		for (int i = left + 1; i <= right; i++) {
			if (nums[i] > nums[maxIndex]) {
				maxIndex = i;
			}
			if (nums[i] < nums[minIndex]) {
				minIndex = i;
			}
		}
		// 交换
		Swap(&nums[left] , &nums[minIndex]);
		// 特殊情况：假设第一个位置就是最大值 那么做完第一次交换最小的值到最左边
		// 而最大值被交换到了原来最小值的位置
		if (left == maxIndex) {
			maxIndex = minIndex;
		}
		Swap(&nums[right] , &nums[maxIndex]);
		left++;
		right--;
	}
}

Swap 实现：

// 交换
void Swap(int* val1, int* val2) {
	int temp = *val1;
	*val1 = *val2;
	*val2 = temp;
}

总结：

  1. 选择排序比较好理解，但是效率很低，实际种很少使用。
  2. 时间复杂度 O ( N 2 ) O(N^2) O(N2)

4. 堆排序 (⭐️⭐️⭐️)

🌟 思想：

堆排序是指用堆这种数据结构所设计的一种排序思想，它是选择排序的一种，它是用堆来进行选数。升序需要建大堆，降序需要建小堆。

拿升序来举例，因为大堆的堆顶是最大的数，此时我们可以让堆顶和末尾元素交换。再让堆顶的元素向下调整（只不过此时向下调整，我们先让数组的长度减 1，因为最大的数已经到末尾的位置了，不必算入堆内）

AdjustDown 实现（大堆举例）：

// 堆的向下调整算法
void AdjustDown(int * nums , int size , int parent) {
	assert(nums);
	// 默认左孩子最大
	int child = 2 * parent + 1;
	while (child < size) {
		// 选出左右孩子最大的孩子
		if (child + 1 < size && nums[child + 1] > nums[child]) {
			child++;
		}
		// 最大的孩子比父亲还大则调整
		if (nums[child] > nums[parent]) {
			Swap(&nums[child] , &nums[parent]);
			// 继续向下搜索
			parent = child;
			child = parent * 2 + 1;
		} else {
			break;
		}
	}
}

AdjustUp 实现（大堆举例）：

// 堆的向上调整算法
void AdjustUp (int * nums , int child) {
	int parent = (child - 1) / 2;
	// 当孩子 = 0的时候已经没有父亲节点了
	while (child > 0) {
		if (nums[child] > nums[parent]) {
			Swap(&nums[child] , &nums[parent]);
			// 继续向上搜索
			child = parent;
			parent = (child - 1) / 2;
		} else {
			break;
		}
	}
}

HeapSort 实现：

// 堆排序
void HeapSort(int * nums , int size) {
	assert(nums);
	// 先建堆
	// 向上调整算法建堆
	// for (int i = 1; i < size; i++) {
		// AdjustUp(nums , i);
	// }
	
	// 向下调整算法建堆
	// 向下调整的前提是：左右子树必须都是堆
	// 所以大堆从第一个非叶子节点开始向下调整
	for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
		AdjustDown(nums , size , parent);
	}

	// 排序
	int end = size - 1;
	while (end > 0) {
		// 堆顶元素和末尾元素交换
		Swap(&nums[0] , &nums[end]);	
		AdjustDown(nums , end , 0);
		end--;
	}
}

总结：

  1. 堆排序的时间复杂度 O ( N ∗ l o g N ) O(N*logN) O(N∗logN)
  2. 向上调整算法建堆的时间复杂度是 O ( N ∗ l o g N ) O(N * logN) O(N∗logN)，向下调整算法建堆的时间复杂度是 O ( N ) O(N) O(N)，但是向下调整算法建堆的前提是：当前左右子树必须是堆。所以向下调整算法要从非叶子节点开始向下调整，最后一个非叶子节点就是最后一个元素的父节点 (size - 1 - 1) / 2。

5. 冒泡排序 (⭐️⭐️)

🌟 思想：

冒泡排序是交换排序的一种。所谓交换就是根据序列中两个记录下标值的比较结果来对这一对数据进行交换，当第一躺冒泡排序结束后，若是升序会把最大的数冒到最后末尾，以此类推。

BubbleSort 实现：

// 冒泡排序
void BubbleSort(int* nums, int size) {
	assert(nums);
	for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				Swap(&nums[j] , &nums[j + 1]);
			}
		}
	}
}

BubbleSort 优化：当数组为有序的时候，我们用 enchage 来记录，若当前这一趟一次都没有交换，则数组已经有序。

// 冒泡排序
void BubbleSort(int* nums, int size) {
	assert(nums);

	for (int i = 0; i < size - 1; i++) {
		int exchage = 1;
		for (int j = 0; j < size - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				exchage = 0;
				Swap(&nums[j] , &nums[j + 1]);
			}
		}
		if (exchage) {
			break;
		}
	}
}

总结：

  1. 冒泡排序是非常经典的排序
  2. 时间复杂度 O ( N 2 ) O(N^2) O(N2)

6. 快速排序 (⭐️⭐️⭐️⭐️)

🌟 思想：

快速排序是 Hoare于1962年提出的一种二叉树结构的交换排序方法。基本思想是：从待排序序列中选一个 key（通常为最左边或者最右边），按照 key 把待排序序列分成两个子序列，左序列中的元素都 < key，右序列的元素都 > key，然后左右序列重复该过程，直到所有元素都排列在对应的位置上。

在这里插入图片描述

1.hoare版本：

思路和结论：假设 key 为最左边的数，那么就要先从右边走，再走左边。假设 key 为最右边的数，那么就要从左边先走，再走右边。这样做的目的是：当 left 与 right 相遇结束的时候，让 key 位置的元素与当前相遇位置交换，而当前相遇位置一定能保证比 key 要小（或大）。 第一次快速排序相当于处理好了第一个区间，因为 key 找到了合适的位置左面的数都比 key 小，右面的数都比 key 要大，此时只需要让左右区间重复上面的过程。左右区间划分为了 [begin , keyIndex - 1] keyIndex [keyIndex + 1 , end]。递归处理即可，当左右区间只剩一个数（begin == end）或者区间不存在（begin > end）的时候为递归结束条件。

QucikSort实现：

void QuickSort(int * nums , int begin , int end) {
	
	// 只剩一个数或者区间不存在不需要处理
	if (begin >= end) {
		return;
	}

	int left = begin;
	int right = end;
	// key 默认为最左边的数字
	int keyIndex = left;
	while (left < right) {
		// 右边先走，找小
		while (left < right && nums[right] >= nums[keyIndex]) {
			right--;
		}
		// 左边找大
		while (left < right && nums[left] <= nums[keyIndex]) {
			left++;
		}
		// 交换
		Swap(&nums[left] , &nums[right]);
	}
	// 相遇位置和 keyIndex 交换
	Swap(&nums[keyIndex] , &nums[left]);
	// 更改 keyIndex
	keyIndex = left;
	
	QuickSort(nums , begin , keyIndex - 1);
	QuickSort(nums , keyIndex + 1, end);
}

💬 思考问题：

  1. nums[left] <= nums[keyIndex] 和 nums[right] >= nums[keyIndex] 这里为什么要使用 = ，不使用 = 可以吗？结论是不可以。

    在这里插入图片描述

  1. 为什么右边和左边走的时候要加上 left < right？

在这里插入图片描述

  1. 为什么 key 如果是左边的数就要先从右边走呢？左边先走可以吗？结论是不可以。
    在这里插入图片描述

2.挖坑版本：

思路：先将最左面的数据存在一个临时变量 key 中，这样当前 key 这个位置就是一个坑位。右面 right 找小，找到之后把小的数填到当前坑中 nums[keyIndex] = nums[right]，此时更换坑的位置 keyIndex = right。左面 left 找大，找到之后把大的数继续填到当前坑中 nums[keyIndex] = nums[left]，此时继续更换坑的位置 keyIndex = left。当 left 与 right 相遇时在把 key 填入相遇（坑位）位置。

QucikSort实现：

void QuickSort(int * nums , int begin , int end) {
	// 只剩一个数或者区间不存在不需要处理
	if (begin >= end) {
		return;
	}
	
	int left = begin;
	int right = end;
	// 保存当前坑的元素
	int key= nums[left];
	// 坑位
	int keyIndex = left;
	while (left < right) {
		while (left < right && nums[right] >= key) {
			right--;
		}
		// 填坑
		nums[keyIndex] = nums[right];
		// 更换坑的位置
		keyIndex = right;
		while (left < right && nums[left] <= key) {
			left++;
		}
		// 填坑
		nums[keyIndex] = nums[left];
		// 更换坑的位置
		keyIndex = left;
	}
	// 循环结束填入当前坑位
	nums[keyIndex] =  key;

	QuickSort(nums , begin , keyIndex - 1);
	QuickSort(nums , keyIndex + 1, end);
}

注：同样一组数，使用 hoare 思想和挖坑法思想进行一轮快排的结果是不同的。

例如：{6 , 1 , 2 , 7 , 9 , 3 , 4 , 5 , 10 , 8}

  1. hoare： 第一次交换 {6 , 1 , 2 , 5 , 9 , 3 , 4 , 7 , 10 , 8}、第二次交换 {6 , 1 , 2 , 5 , 4 , 3 , 9 , 7 , 10 , 8}、循环结束相遇位置与 keyIndex 位置交换 {3 , 1 , 2 , 5 , 4 , 6 , 9 , 7 , 10 , 8} 最终结果。

  2. 挖坑法： 第一次挖坑 {5 , 1 , 2 , 7 , 9 , 3 , 4 , (5) , 10 , 8}、第二次 {5 , 1 , 2 , (7) , 9 , 3 , 4 , 7 , 10 , 8}、第三次 {5 , 1 , 2 , 4 , 9 , 3 , (4) , 7 , 10 , 8}、第四次 {5 , 1 , 2 , 4 , (9) , 3 , 9 , 7 , 10 , 8}、第五次 {5 , 1 , 2 , 4 , 3 , (3) , 9 , 7 , 10 , 8}、循环结束把当前坑位填入 key 最终结果是 {5 , 1 , 2 , 4 , 3 , 6 , 9 , 7 , 10 , 8}。

3.前后指针版本：

思路： 定义一个 prev 和 cur，cur 找比 key 要小的数，若找到则 ++prev 和 cur 当前下标的元素进行交换，这样做有一种把小的数翻到前面来，大的往后推。而 prev 后面的数都要比 key 大，最终 cur 越界循环结束，再把 keyIndex 位置和 prev 位置的元素进行交换。

QucikSort 实现：

void QuickSort(int * nums , int begin , int end) {
	// 只剩一个数或者区间不存在不需要处理
	if (begin >= end) {
		return;
	}
	
	int prev = begin;
	int cur = prev + 1;
	int keyIndex = begin;
	while (cur <= end) {
		if (nums[cur] < nums[keyIndex] && ++prev != cur) {
			Swap(&nums[prev] , &nums[cur]);
		}
		cur++;
	}
	Swap(&nums[prev] , &nums[keyIndex]);
	keyIndex = prev;
	
	QuickSort(nums , begin , keyIndex - 1);
	QuickSort(nums , keyIndex + 1, end);
}

🌟 快排优化

💬 为什么要优化？

因为 key 会影响快排的效率，如果每次的 key 都是中间那个值那么每次都是二分，若每次的 key 都是最小的，最坏情况下快排的时间复杂度 O ( N 2 ) O(N^2) O(N2)。最大的问题是会引起 栈溢出。

1.三数取中优化：

思路： 第一个数和中间还有最后的数，选不是最大也不是最小的数。三数取中主要体现在数据已经有序的情况下。

getMidIndex 实现：

int getMidIndex(int* nums, int begin, int end) {
	int midIndex = (begin + end) / 2;
	if (nums[begin] > nums[midIndex]) {
		// nums[begin] > nums[minIndex]
		if (nums[midIndex] > nums[end]) {
			// nums[begin] > nums[minIndex] > nums[end]
			return midIndex;
		}
		else if (nums[begin] > nums[end]) {
			// nums[begin] > nums[minIndex]
			// nums[end] >= nums[minIndex]
			// nums[begin] > nums[end]
			return end;
		}
		else {
			// nums[begin] > nums[minIndex]
			// nums[end] >= nums[minIndex]
			// nums[begin] <= nums[end]
			return begin;
		}
	}
	else {
		// nums[begin] <= nums[minIndex]
		if (nums[begin] > nums[end]) {
			// nums[begin] <= nums[minIndex]
			// nums[begin] > nums[end]
			return begin;
		}
		else if (nums[midIndex] > nums[end]) {
			// nums[begin] <= nums[minIndex]
			// nums[begin] <= nums[end]
			// nums[minIndex] > nums[end]
			return end;
		}
		else {
			// nums[begin] <= nums[minIndex]
			// nums[begin] <= nums[end]
			// nums[minIndex] <= nums[end]
			return midIndex;
		}
	}
}

2.小区间优化：

思路： 若只剩最后 10 - 20 个数，还使用快速排序的递归就有点不太划算了。所以当区间较小的时候，就不再使用递归继续划分小区间。考虑直接用其他排序对小区间处理，而希尔排序和堆排序对于数据量小的时候也不太优，所以在简单排序中，插入排序适应性最强。 小区间优化体现在减少递归的调用次数。

QuickSort 优化实现：

void QuickSort(int* nums, int begin, int end) {
	// 只剩一个数或者区间不存在不需要处理
	if (begin >= end) {
		return;
	}

	if (end - begin > 15) {
		int prev = begin;
		int cur = prev + 1;
		int keyIndex = begin;
		// 三数取中优化
		int midIndex = getMidIndex(nums, begin, end);
		Swap(&nums[keyIndex], &nums[midIndex]);

		while (cur <= end) {
			if (nums[cur] < nums[keyIndex] && ++prev != cur) {
				Swap(&nums[prev], &nums[cur]);
			}
			cur++;
		}
		Swap(&nums[prev], &nums[keyIndex]);
		keyIndex = prev;

		QuickSort(nums, begin, keyIndex - 1);
		QuickSort(nums, keyIndex + 1, end);
	} 
	else {
		// 小区间优化
		// 插入排序
		InsertSort(nums + begin  , end - begin + 1);
	}
}

🌟 快排非递归

QuickSortNoneR 非递归实现：

// 快排非递归（使用栈）
void QucikSortNoneR(int* nums, int begin, int end) {
	assert(nums);

	Stack stack;
	StackInit(&stack);
	// 区间进栈
	StackPush(&stack , end);
	StackPush(&stack, begin);
	while (!StackEmpty(&stack)) {
		// 取出左右区间
		int left = StackTop(&stack);
		StackPop(&stack);
		int right = StackTop(&stack);
		StackPop(&stack);
		
		// 快排
		int keyIndex = left;
		int prev = left;
		int cur = prev + 1;
		while (cur <= right) {
			if (nums[cur] < nums[keyIndex] && ++prev != cur) {
				Swap(&nums[prev], &nums[cur]);
			}
			cur++;
		}
		Swap(&nums[prev], &nums[keyIndex]);
		keyIndex = prev;

		// [left , keyIndex - 1] keyIndex [keyIndex + 1 , right]

		if (keyIndex + 1 < right) {
			// 区间存在 入栈
			StackPush(&stack, right);
			StackPush(&stack, keyIndex + 1);
		}

		if (left < keyIndex - 1) {
			// 区间存在 入栈
			StackPush(&stack, keyIndex - 1);
			StackPush(&stack, left);
		}
	}

	StackDestroy(&stack);
}

总结：

  1. 时间复杂度 O ( N ∗ l o g N ) O(N*logN) O(N∗logN)
  2. 空间复杂度 O ( l o g N ) O(logN) O(logN)

7. 归并排序 (⭐️⭐️⭐️)

🌟 思想：

归并排序是建立在归并操作上的一种有效的排序算法，是分治的一个典型的应用。将两个有序的子序列归并得到完全有序的序列。归并排序要借助额外的空间。

MergeSort 递归实现：

void merge(int* nums, int begin, int end, int* temp) {

	// 区间只有一个数或者不存在
	if (begin >= end) {
		return;
	}
	
	int midIndex = (begin + end) / 2;

	// [begin , midIndex] [minIndex + 1 , end]
	merge(nums , begin , midIndex , temp);
	merge(nums , midIndex + 1 , end , temp);

	// 归并
	int leftBegin = begin;
	int leftEnd = midIndex;
	int rightBegin = midIndex + 1;
	int rightEnd = end;
	int i = leftBegin;
	while (leftBegin <= leftEnd && rightBegin <= rightEnd) {
		if (nums[leftBegin] < nums[rightBegin]) {
			temp[i++] = nums[leftBegin++];
		}
		else {
			temp[i++] = nums[rightBegin++];
		}
	}

	// 左区间还存在
	while (leftBegin <= leftEnd) {
		temp[i++] = nums[leftBegin++];
	}

	// 右区间还存在
	while (rightBegin <= rightEnd) {
		temp[i++] = nums[rightBegin++];
	}

	// 拷贝回原数组
	memcpy(nums + begin , temp + begin, (end - begin + 1) * sizeof(int));
}

// 归并排序
void MergeSort(int* nums, int size) {
	assert(nums);

	int* temp = (int*)malloc(sizeof(int) * size);
	assert(temp);

	merge(nums , 0 , size - 1 , temp);

	free(temp);
}

🌟 归并非递归

MergeSort 非递归实现：

// 归并排序非递归
void MergeSortNoneR(int* nums, int size) {
	assert(nums);

	int* temp = (int*)malloc(sizeof(int) * size);
	assert(temp);

	int gap = 1;
	while (gap < size) {
		for (int i = 0; i < size; i += 2 * gap) {
			int leftBegin = i;
			int leftEnd = i + gap - 1;
			int rightBegin = i + gap;
			int rightEnd = i + 2 * gap - 1;

			// 检查边界
			if (leftEnd >= size) {
				// 修正左区间
				leftEnd = size - 1;
				// 让右区间不存在
				rightBegin = size + 1;
				rightEnd = size;
			}
			else if (rightBegin >= size) {
				rightBegin = size + 1;
				rightEnd = size;
			}
			else if (rightEnd >= size) {
				rightEnd = size - 1;
			}

			// 归并
			int j = leftBegin;
			while (leftBegin <= leftEnd && rightBegin <= rightEnd) {
				if (nums[leftBegin] < nums[rightBegin]) {
					temp[j++] = nums[leftBegin++];
				}
				else {
					temp[j++] = nums[rightBegin++];
				}
			}

			// 左区间还存在
			while (leftBegin <= leftEnd) {
				temp[j++] = nums[leftBegin++];
			}

			// 右区间还存在
			while (rightBegin <= rightEnd) {
				temp[j++] = nums[rightBegin++];
			}

		}
		memcpy(nums, temp, sizeof(int) * size);
		gap *= 2;
	}


	free(temp);
}

总结：

  1. 时间复杂度 O ( N ∗ l o g N ) O(N*logN) O(N∗logN)
  2. 空间复杂度 O ( N ) O(N) O(N)

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

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

相关文章

Vue3搭建启动

Vue3搭建启动

Vue3搭建&启动 一、创建项目二、启动项目三、配置项目1、添加编辑器配置文件2、配置别名3、处理sass/scss4、处理tsx(不用的话可以不处理) 四、添加Eslint 一、创建项目 npm create vite 1.project-name 输入项目名vue3-vite 2.select a framework 选择框架 3.select a var…
阅读更多...
【Spring】聊聊Spring如何解决的循环依赖以及三级缓存

【Spring】聊聊Spring如何解决的循环依赖以及三级缓存

循环依赖是什么 在平时的面试中&#xff0c;只要问到Spring&#xff0c;那么大概率肯定会问什么是循环依赖&#xff0c;Sping是如何解决循环依赖的。以及三级缓存机制是什么。所以为了从根本上解决这个问题&#xff0c;本篇主要详细介绍一下循环依赖的问题。 Spring Bean初始…
阅读更多...
谷粒商城第七天-商品服务之分类管理下的分类的拖拽功能的实现

谷粒商城第七天-商品服务之分类管理下的分类的拖拽功能的实现

目录 一、总述 1.1 前端思路 1.2 后端思路 二、前端实现 2.1 判断是否能进行拖拽 2.2 收集受影响的节点&#xff0c;提交给服务器 三、后端实现 四、总结 一、总述 这个拖拽功能对于这种树形的列表&#xff0c;整体的搬迁是很方便的。但是其实现却并不是那么的简单。 …
阅读更多...
Android SDK 上手指南||第一章 环境需求||第二章 IDE：Eclipse速览

Android SDK 上手指南||第一章 环境需求||第二章 IDE：Eclipse速览

第一章 环境需求 这是我们系列教程的第一篇&#xff0c;让我们来安装Android的开发环境并且把Android SDK运行起来&#xff01; 介绍 欢迎来到Android SDK入门指南系列文章&#xff0c;如果你想开始开发Android App&#xff0c;这个系列将从头开始教你所须的技能。我们假定你…
阅读更多...
Vue2封装自定义全局Loading组件

Vue2封装自定义全局Loading组件

前言 在开发的过程中&#xff0c;点击提交按钮&#xff0c;或者是一些其它场景总会遇到Loading加载框&#xff0c;PC的一些UI库也没有这样的加载框&#xff0c;无法满足业务需求&#xff0c;因此可以自己自定义一个&#xff0c;实现过程如下。 效果图 如何封装&#xff1f; 第…
阅读更多...
MySQL | 常用命令示例

MySQL | 常用命令示例

MySQL | 常用命令示例 一、启停MySQL数据库服务二、连接MySQL数据库三、创建和管理数据库四、创建和管理数据表五、数据备份和恢复六、查询与优化 MySQL是一款常用的关系型数据库管理系统&#xff0c;广泛应用于各个领域。在使用MySQL时&#xff0c;我们经常需要编写一些常用脚…
阅读更多...
Qt之切换语言的方法（传统数组法与Qt语言家）

Qt之切换语言的方法（传统数组法与Qt语言家）

http://t.csdn.cn/BVigB 传统数组法&#xff1a; 定义一个字符串二维数组&#xff0c; QString weekStr[2][7] {"星期一","星期二","星期三","星期四","星期五","星期六","星期日",\ "Monday&…
阅读更多...
自己创建的类，其他类中使用错误

自己创建的类，其他类中使用错误

说明&#xff1a;自己创建的类&#xff0c;在其他类中创建&#xff0c;报下面的错误&#xff08;Cannot resolve sysmbol ‘Redishandler’&#xff09;&#xff1b; 解决&#xff1a;看下是不是漏掉了包名 加上包名&#xff0c;问题解决&#xff1b;
阅读更多...
云计算——云计算与虚拟化的关系

云计算——云计算与虚拟化的关系

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 前言 一.虚拟化 1.什么是虚拟化 2.虚拟化技术作用 二.云计算与虚拟化的关系 三.虚…
阅读更多...
[STL]stack和queue使用介绍

[STL]stack和queue使用介绍

[STL]stack和queue使用介绍 文章目录 [STL]stack和queue使用介绍stack使用介绍stack介绍构造函数empty函数push函数top函数size函数pop函数 queue使用介绍queue介绍构造函数empty函数push函数front函数back函数size函数pop函数 deque介绍 stack使用介绍 stack介绍 stack是一种…
阅读更多...
Tensorflow报错protobuf requires Python ‘＞=3.7‘ but the running Python is 3.6.8

Tensorflow报错protobuf requires Python ‘＞=3.7‘ but the running Python is 3.6.8

报错信息 仔细观察下方命令后&#xff0c;可得运行:python -m pip install --upgrade pip即可 完成后再次执行性安装命令 成功&#xff01;&#xff01;&#xff01;
阅读更多...
爆肝！《Java 权威面试指南（阿里版）》，冲击“金九银十”有望了

爆肝！《Java 权威面试指南（阿里版）》，冲击“金九银十”有望了

这次金九银十你准备好了吗&#xff1f; 莫慌莫慌&#xff0c;“面试造火箭&#xff0c;工作拧螺丝” 说得不无道理&#xff0c;偶然从朋友那得到的这份 Alibaba 内部疯传《Java 权威面试指南&#xff08;阿里版&#xff09;》堪称精品&#xff0c;或可能助你一臂之力&#xff…
阅读更多...
Doris注意事项，Doris部署在阿里云，写不进去数据

Doris注意事项，Doris部署在阿里云，写不进去数据

1.Doris官网 Doris官网https://doris.apache.org/ 2.根本原因 本地idea访问FE&#xff0c;FE会返回BE的地址&#xff0c;但是在服务器上通过ip addr查看&#xff0c;发现只有局域网IP&#xff0c;所以FE返回了局域网的IP&#xff0c;导致idea连接不上BE 3.解决办法 重写Ba…
阅读更多...
Jmeter并发测试

Jmeter并发测试

基本步骤 1、新建线程组 测试计划右键——>添加——>线程&#xff08;用户&#xff09;——>线程组 2、 添加HTTP请求 线程组右键——>添加——>取样器——>HTTP请求 3、 添加HTTP信息头管理器 线程组右键——>添加——>配置元件——>HTTP信息头…
阅读更多...
ChatGPT炒股：自动批量提取股票公告中的表格并合并数据

ChatGPT炒股：自动批量提取股票公告中的表格并合并数据

在很多个股票公告中&#xff0c;都有同样格式的“日常性关联交易”的表格&#xff0c;如何合并到一张Excel表格中呢&#xff1f; 首先&#xff0c;在ChatGPT中输入提示词&#xff1a; 写一段Python代码&#xff1a; F盘文件夹“新三板 2023年日常性关联交易20230704”中很多…
阅读更多...
2023 7-30

2023 7-30

题目1 lee2331.计算布尔二叉树的值 对于一棵完整的二叉树(每一个根节点孩子的个数不是0就是2) 叶子节点是1或者是0，其中1代表true,0代表false非叶子节点的值是2或者3，其中2代表逻辑或or,3代表逻辑与and计算方式 如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者…
阅读更多...
一、创建自己的docker python容器环境；支持新增python包并更新容器；离线打包、加载image

一、创建自己的docker python容器环境；支持新增python包并更新容器；离线打包、加载image

1、创建自己的docker python容器环境 参考&#xff1a;https://blog.csdn.net/weixin_42357472/article/details/118991485 首先写Dockfile&#xff0c;注意不要有txt等后缀 Dockfile # 使用 Python 3.9 镜像作为基础 FROM python:3.9# 设置工作目录 WORKDIR /app# 复制当前…
阅读更多...
创造自己的宠物医院预约服务小程序，步骤详解

创造自己的宠物医院预约服务小程序，步骤详解

在现代社会&#xff0c;越来越多的人开始养宠物&#xff0c;而宠物的健康管理也成为了一个重要的话题。为了方便宠物主人随时随地进行宠物医院的管理和服务&#xff0c;开发一个宠物医院管理小程序是很有必要的。今天我们将分享一些制作宠物医院管理小程序的技巧&#xff0c;帮…
阅读更多...
基于Open3D的点云处理12-体素化

基于Open3D的点云处理12-体素化

体素化Voxelization 体素&#xff08;voxel&#xff09;是像素&#xff08;pixel&#xff09;、体积&#xff08;volume&#xff09;和元素&#xff08;element&#xff09;的组合词&#xff0c;相当于3D空间中的像素; 体素化是通过用空间均匀大小的体素网格(voxel grid)来模…
阅读更多...
【C++】开源：grpc远程过程调用（RPC）配置与使用

【C++】开源：grpc远程过程调用（RPC）配置与使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍grpc远程过程调用&#xff08;RPC&#xff09;配置与使用。 无专精则不能成&#xff0c;无涉猎则不能通。。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站