代码探险家

这个屌丝很懒，什么也没留下！

热门标签

0627，0628，0629，排序，文件

作者：代码探险家 | 2024-07-06 07:26:30

踩

01：请实现选择排序，并分析它的时间复杂度，空间复杂度和稳定性

void selection_sort(int arr[], int n);

解答：

~~稳定性：稳定，~~ 不稳定的，会发生长距离的交换 4 9 9 4 1 ，把第一个4换掉了

时间复杂度：比较（n-1）+(n-1)+(n-3)+……+1=n*(n/2)=O(n^2)

交换：最好情况，不交换，最坏情况O(n^2)==比较

一般情况：O(n^2)

空间复杂度：O(1)


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE(a) (sizeof(a)/sizeof(a[0]))
 
void selection_sort(int arr[], int n) {
	int max;
	for (int i = 0; i < n-1; i++) {
		//和后面的LEN-1个比较
		max = i;
		for (int j = i + 1; j < n; j++) {
			//max=arr[j]   arr[i]<arr[j]  swap
			if (arr[max] < arr[j]) {     //相等的元素不发生交换，稳定
				max = j;
			}
 		}
		//swap(arr[i], arr[max]);
		int temp = arr[i];
		arr[i] = arr[max];
		arr[max] = temp;
	}
}
void print_arr(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d  ", arr[i]);
	}
	printf("\n");
}
 
 
int main(void) {
	int arr[] = { 2,34,12,12,34,56,78,90,899,100 };
	print_arr(arr, SIZE(arr));
	selection_sort(arr, SIZE(arr));
	print_arr(arr, SIZE(arr));
	return 0;
}

答案：


#define SWAP(arr, i, j) {	\
	int tmp = arr[i];		\
	arr[i] = arr[j];		\
	arr[j] = tmp;			\
}
 
void selection_sort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int minIdx = i;
		// 找到最小元素的索引
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[minIdx]) {
				minIdx = j;
			}
		}
		// 交换arr[i]和arr[j]
		SWAP(arr, i, minIdx);
 
		// print_array(arr, n);
	}
}
 
分析：
1. 时间复杂度：O(n^2)
    比较次数: (n-1) + (n-2) + ... + 1 = n(n-1)/2
    交换次数：n-1
2. 空间复杂度：O(1)
  	不需要申请而外的数组
3. 稳定性: 不稳定
    会发生长距离的交换

02：请实现冒泡排序，并分析它的时间复杂度，空间复杂度和稳定性

void bubble_sort(int arr[], int n);

解答：

稳定性：稳定，

时间复杂度：比较（n-1）+(n-1)+(n-3)+……+1=n*(n/2)=O(n^2)

交换：最好情况，不交换，最坏情况O(n^2)==比较

一般情况：O(n^2)

空间复杂度：O(1)


void bubble_sort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {     //相等的元素不发生交换，稳定
			//如果 arr[i]<arr[j]  swap
			if (arr[i] < arr[j]) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

答案：


void bubble_sort(int arr[], int n) {
   	for (int i = 1; i < n; i++) { // i表示第几次冒泡
   		bool isSorted = true;  
   		// 比较arr[j]和arr[j+1]
   		for (int j = 0; j < n - i; j++) {
   			if (arr[j] > arr[j + 1]) {
   				SWAP(arr, j, j + 1);
   				isSorted = false;	// 发生交换，说明数组还未排好序
   			}
   		}
   
   		if (isSorted) break;
   	}
}
分析：
   1. 时间复杂度：
       最好情况：原数组有序, O(n)
       	比较次数：n-1
       	交换次数：0
       最坏情况：原数组逆序, O(n^2)
       	比较次数：(n-1) + (n-2) + ... + 1
       	交换次数：(n-1) + (n-2) + ... + 1
       平均情况：O(n^2) (和插入排序的分析方法一致)
       	比较次数：大于等于交换的次数，小于等于 n(n-1)/2
       	交换次数：n(n-1)/4 (等于逆序度)
   2. 空间复杂度：O(1)
   	不需要申请额外的数组
   3. 稳定性：稳定
       交换的是相邻两个元素，而且只交换逆序对。

03：请实现插入排序，并分析它的时间复杂度，空间复杂度和稳定性

void insertion_sort(int arr[], int n);

解答：

稳定性：稳定，

时间复杂度：比较（n-1）

交换：最好情况，不交换，最坏情况+(n-1)+(n-3)+……+1=n*(n/2)=O(n^2)

一般情况：O(n^2)

空间复杂度：O(1)


void insertion_sort(int arr[], int n) {
	//第一个元素看作有序数列，从第二个元素开始插入
	for (int i = 1; i < n; i++) {
		//保留要插入的值
		int val = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > val) {  //遇到相等的元素，插在后面，不进入循环
			arr[j + 1] = arr[j];
			j--;
		}//arr[j]<=val||j==-1
		arr[j + 1] = val;
	}
}

答案：


void insertion_sort(int arr[], int n) {
	for (int i = 1; i < n; i++) { // i:待插入元素的索引
		// 保存待插入的元素
		int value = arr[i];
		int j = i - 1;
		while (j >= 0 && arr[j] > value) {
			arr[j + 1] = arr[j]; // 逻辑上的交换操作
			j--;
		}
		// j == -1 || arr[j] <= value
		arr[j + 1] = value;
	}
}

04：请实现归并排序，并分析它的时间复杂度，空间复杂度和稳定性

void merge_sort(int arr[], int n);

解答：

稳定性：稳定，

时间复杂度：O(n)

空间复杂度：O(n)


int temp[N];
void m_sort(int arr[], int left, int right, int mid) {
	//比较左边和右边区间，小的加入数组
	int i = left;
	int i_left = left; int i_right = mid+1;
 
	while (i_left <= mid && i_right <= right) {
		if (arr[i_left] <= arr[i_right]) {  //两边相等，插左边区间进数组
			temp[i++] = arr[i_left++];
		}else{
			temp[i++] = arr[i_right++];
		}
	}//i_left>mid ||  i_right>right
 
	while (i_left <= mid) {
		temp[i++] = arr[i_left++];
	}
	while (i_right <= right) {
		temp[i++] = arr[i_right++];
	}//i==N
	for (int j = right; j>=left; j--) {
		arr[j] = temp[j];
	}
	
}
void merge_sort_help(int arr[], int left, int right) {
	if (left>=right)  //1个0个，有序
		return;
	//排序左边区间
	//排序右边区间
	//归并
	//int mid = left + (right-left >> 1);
	int mid = (left + right) / 2;
	merge_sort_help(arr, left, mid);//[0,mid]   
	merge_sort_help(arr, mid+1, right);//[mid+1,right]
	m_sort(arr, left, right, mid);
}
void merge_sort(int arr[], int n) {
	//外包
	merge_sort_help(arr, 0, n - 1);
}

答案：


int tmp[10];
 
void merge(int arr[], int left, int mid, int right) {
	int i = left, j = left, k = mid + 1;
	// 两个区间都有元素
	while (j <= mid && k <= right) {
		if (arr[j] <= arr[k]) {		// Caution: 不能写成 arr[j] < arr[k], 就不稳定了
			tmp[i++] = arr[j++];
		} else {
			tmp[i++] = arr[k++];
		}
	} // j > mid || k > right
	// 左边区间有元素
	while (j <= mid) {
		tmp[i++] = arr[j++];
	}
	// 右边区间有元素
	while (k <= right) {
		tmp[i++] = arr[k++];
	}
	// 将tmp数组中的元素，复制到原数组的对应区间
	for (int i = left; i <= right; i++) {
		arr[i] = tmp[i];
	}
}
 
void m_sort(int arr[], int left, int right) {
	// [left, right] 归并排序
	// 边界条件
	if (left >= right) return;
	// 递归公式
	int mid = left + (right - left >> 1);
	m_sort(arr, left, mid);
	m_sort(arr, mid + 1, right);
	merge(arr, left, mid, right);
 
	print_array(arr, 10);
}
 
void merge_sort(int arr[], int n) {
	// 委托
	m_sort(arr, 0, n - 1);  // [0, n-1]
}

05：请实现快速排序，并分析它的时间复杂度，空间复杂度和稳定性

void quick_sort(int arr[], int n);

解答：

稳定性：不稳定，

时间复杂度：最坏，O(n^2) 可以避免，
最好O（nlogn) 平均O（nlogn)

空间复杂度：栈的使用空间，O(nlogn)


int partition(int arr[], int left, int right) {
	int pivot = arr[left];
	int i = left, j = right;//i下一个小于基准值的树，J下一个大于基准值的数
	while (j>i) {
		//j，J找到小于基准值的数，覆盖I的位置
		while (j>i&&arr[j] >= pivot) {
			j--;
		}
		arr[i] = arr[j];
		//i，i找到da于基准值的数，覆盖j的位置
		while (j > i && arr[i]<=pivot) {
			i++;
		}
		arr[j] = arr[i];
	}//i==j
	arr[i] = pivot;
	return i;
}
void q_sort(int arr[], int left, int right) {
	if (left >= right)
		return;
	//基准值最终位置
	int idx = partition(arr, left, right);
	//排序左边[left,idx-1]
	q_sort(arr, left, idx - 1);
	//排序右边[idx+1,right]
	q_sort(arr,  idx + 1,right);
}
void quick_sort(int arr[], int n) {
	//外包
	q_sort(arr, 0, n - 1);
}

答案：


int partition(int arr[], int left, int right) {
	// 选取基准值
	int pivot = arr[left];
	// 双向分区
	int i = left, j = right;
	while (i < j) {
		// 移动j, 找第一个比pivot小的元素
		while (i < j && arr[j] >= pivot) {
			j--;
		} // i == j || arr[j] < pivot
		arr[i] = arr[j];
 
		// 移动i，找第一个比pivot大的元素
		while (i < j && arr[i] <= pivot) {
			i++;
		} // i == j || arr[i] > pivot
		arr[j] = arr[i];
 
	} // i == j
	arr[i] = pivot;
	return i;
}
 
void q_sort(int arr[], int left, int right) {
	// [left, right]
	// 边界条件
	if (left >= right) return;
	// 递归公式
	// 对[left, right]区间分区, idx是分区后基准值所在的位置
	int idx = partition(arr, left, right);
 
	print_array(arr, 10);
 
	q_sort(arr, left, idx - 1);
	q_sort(arr, idx + 1, right);
}
 
void quick_sort(int arr[], int n) {
	q_sort(arr, 0, n - 1);	// [0, n-1]
}

06：给定一个排好序的数组，请设计一个算法将数组随机打乱。

void shuffle(int arr[], int n)

解答：


void shuffle(int arr[], int n) {
	srand(time(NULL));
	int j;
	for (int i = 0; i < n; i++) {
		j = rand() % (n - 1);  //0-n-1
		int temp=arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

答案：

好好好，和AI是一样的貌似


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SWAP(arr, i, j) {	\
	int tmp = arr[i];		\
	arr[i] = arr[j];		\
	arr[j] = tmp;			\
}
 
#define SIZE(a) (sizeof(a) / sizeof(a[0]))
 
void shuffle(int arr[], int n) {
	srand(time(NULL));
	for (int i = 0; i < n - 1; i++) {
		// [i, n-1]
		int j = rand() % (n - i) + i;
		SWAP(arr, i, j);
	}
}
 
void print_array(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
int main(void) {
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
	shuffle(arr, SIZE(arr));
	print_array(arr, SIZE(arr));
 
	return 0;
}

———————————————————————————————————————————

01：请实现堆排序，并分析它的时间复杂度，空间复杂度和稳定性

void heap_sort(int arr[], int n);

解答：


void heapify(int arr[], int i ,int len) {
	while (i < len) { //len--
		int lchild = 2 * i + 1;
		int rchild = 2 * i + 2;
		int maxIdx = i;
		if (lchild<len && arr[lchild]>arr[maxIdx]) {
			maxIdx = lchild;
		}
		if (rchild<len && arr[rchild]>arr[maxIdx]) {
			maxIdx = rchild;
		}
		if (maxIdx == i) { break; } //调整完成
		SWAP(arr, i, maxIdx);//maxIdx=lchild || rchild   比原来大捏
		i = maxIdx;
	}//i>=len,maxIdx==i
}
void heap_build(int arr[], int n) {
	//2*i+1<=n-1  n>i-2>>1    挨个
	for (int i = n - 2 >> 1; i >= 0; i--) {
		heapify(arr, i, n);
	}//i<0
}
void heap_sort(int arr[], int n) {
	//构建大顶堆
	heap_build(arr, n);
	int len = n;
	while (len > 1) {
		//交换第一个元素和 无序区最后一个元素
		SWAP(arr, 0, len - 1);
		len--;
		heapify(arr, 0, len);  //重新调整无序区
	}//len==1;
}

答案：


// i: 可能违反大顶堆规则的结点，并且它的左右子树都是大顶堆
// n: 逻辑上堆的长度
// 时间复杂度：O(logn)
void heapify(int arr[], int i, int n) {
	while (i < n) {
		int lchild = 2 * i + 1;
		int rchild = 2 * i + 2;
		// 求i, lchild, rchild的最大值
		int maxIdx = i;
		if (lchild < n && arr[lchild] > arr[maxIdx]) {
			maxIdx = lchild;
		}
		if (rchild < n && arr[rchild] > arr[maxIdx]) {
			maxIdx = rchild;
		}
 
		if (maxIdx == i) break;
 
		SWAP(arr, i, maxIdx);
		i = maxIdx;
	}
}
 
void build_heap(int arr[], int n) {
	// 从后往前构建, 找第一个非叶子结点
	// lchild(i) = 2i+1 <= n-1
	// i <= (n-2)/2
	for (int i = n - 2 >> 1 ; i >= 0; i--) {
		heapify(arr, i, n);
	}
}
 
void heap_sort(int arr[], int n) {
	build_heap(arr, n);		// O(n)
 
	print_array(arr, n);
 
	int len = n;	// 无序区的长度
	while (len > 1) {
		// 交换堆顶元素和无序区的最后一个元素
		SWAP(arr, 0, len - 1);
		len--;
		heapify(arr, 0, len); // 0: 可能违反堆规则的结点，这个结点的左右子树都是大顶堆
		                      // len: 逻辑上堆的大小
 
		print_array(arr, n);
	} // len == 1
}

02：给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isValidBST(struct TreeNode* root) {
    
}

解答：

答案：


struct TreeNode* max; // 记录遍历结点中的最大结点
 
bool validate(struct TreeNode* root) {
    // 边界条件
    if (root == NULL) return true;
    // 验证左子树
    if (!validate(root->left)) return false;
    // 验证根结点
    if (max != NULL && max->val >= root->val) return false; 
    max = root;  // 将根结点设为最大结点
    
    return validate(root->right); // 验证右子树
}
 
bool isValidBST(struct TreeNode* root) {
    max = NULL;
    return validate(root);
}

03：请实现下列二分查找的变种：


// 查找最后一个与 key 相等的元素
int binary_search1(int arr[], int n, int key);
// 查找最后一个小于等于 key 值的元素
int binary_search2(int arr[], int n, int key);

解答：


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
 
// 查找最后一个与 key 相等的元素
int binary_search1(int arr[], int n, int key) {
	int left = 0;
	int right = n - 1;
	
 
	//比较，小于KEY，rigth动，大于,LEFTdong1
	while (left <= right) {
		int mid = left + (right - left >> 1);
		int cmp = key - arr[mid];
		if (cmp < 0) {
			right = mid - 1;
		}
		else if (cmp > 0) {
			left = mid + 1;
		}
		else {   //后一个元素大于key,可能没有后一个元素||最后一个元素大于等于
			while (mid < right && arr[mid + 1] <= key) {
				right = mid - 1;
			}//mid==right || arr[mid+1]>key
			if (mid == right) { return mid; }
			else { return mid + 1; }
		}
	}
	return -1;
}
// 查找最后一个小于等于 key 值的元素
int binary_search2(int arr[], int n, int key) {
	int left = 0;
	int right = n - 1;
 
	//都比key小，返回N-1，都比KEY大，-1.
	while (left <= right) {
		int mid = left + (right - left >> 1);
		int cmp = key - arr[mid];   //   left  mid    right  
		if (cmp < 0) {
			right = mid - 1;
		}
		else if (cmp > 0) {
			if (arr[left + 1] > key) { return left; }
			left = mid + 1;
		}
		else {   //mid向right靠近
			while (mid <= right && arr[mid + 1] <= key) {   //mid<=right  arr[right]也要进行比较
				mid++;
			}//mid==right|| arr[mid+1]>key
			return mid;
		}
	}
	return -1;
}
 
 
int main(void) {
	int arr[] = { 10,20,20,20,30,30,40,50,50,50,50,60,70,100,100,100,1001,1001,1200 };
	//int y01=binary_search1(arr,SIZE(arr),12);  
	int y01 = binary_search2(arr, SIZE(arr), 30);
	return 0;
}

答案：


// 查找最后一个与 key 相等的元素
int binary_search1(int arr[], int n, int key) {
	int left = 0, right = n - 1;
 
	while (left <= right) {
		int mid = left + (right - left >> 1);
		int cmp = key - arr[mid];
		if (cmp < 0) {
			right = mid - 1;
		} else if (cmp > 0) {
			left = mid + 1;
		} else {
			if (mid == right || arr[mid + 1] > key) {
				return mid;
			}
			left = mid + 1;
		}
	}
	return -1;
}
 
// 查找最后一个小于等于 key 值的元素
int binary_search2(int arr[], int n, int key) {
	int left = 0, right = n - 1;
 
	while (left <= right) {
		int mid = left + (right - left >> 1);
		int cmp = arr[mid] - key;
 
		if (cmp <= 0) {
			if (mid == right || arr[mid + 1] > key) {
				return mid;
			}
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
 
	return -1;
}

04：用 fread/fwrite 实现文件的复制。


// copyFile.c
int main(int argc, char* argv[]);

解答：


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE(a) (sizeof(a)/sizeof(a[0]))
 
int main(int argc, char* argv[]) {
	if (argc != 3) {
		printf("error,\n");
		exit(1);
	}
	//打开源文件
	FILE* mam = fopen(argv[1], "rb");
	if (!mam) {
		printf("error,\n");
		exit(1);
	}
	//打开目标文件
	FILE* son = fopen(argv[2], "wb");
	if (!son) {
		printf("error,\n");
		fclose(mam);
		exit(1);
	}
	//复制
	char buffer[75000];
	int n;
	while ((n=fread(buffer, 1, SIZE(buffer), mam)) != 0) {
		fwrite(buffer, 1, n, son);
	}
 
	fclose(mam);
	fclose(son);
 
	return 0;
}
 
/*
用 fread/fwrite 实现文件的复制。
// copyFile.c
int main(int argc, char* argv[]);*/

答案：


int main(int argc, char* argv[]) {
	// 打开文件流
	FILE* src = fopen(argv[1], "rb");
	if (!src) {
		fprintf(stderr, "Open %s failed.\n", argv[1]);
		exit(1);
	}
 
	FILE* dst = fopen(argv[2], "wb");
	if (!dst) {
		fclose(src);
		fprintf(stderr, "Open %s failed.\n", argv[2]);
		exit(1);
	}
 
	char buffer[4096];  // 4k, buffer的就是块的大小
	int n;
	while ((n = fread(buffer, 1, 4096, src)) > 0) {	// 实际读取了n个元素
		fwrite(buffer, 1, n, dst);
	}
 
	// 关闭文件流
	fclose(src);
	fclose(dst);
	return 0;
}

———————————————————————————————————————————

001：将一个文件读入程序，将其中的大小写字母右旋13个位置后，写入另一个文件。

[A-Ma-m] 转换成 [N-Zn-z]

[N-Zn-z] 转换成 [A-Ma-m]

其余字符不变

int main(int argc, char* argv[]) {}

解答：


//请实现下面功能将一个文件读入程序，将其中的大小写字母右旋13个位置后，写入另一个文件。
void right_handed(FILE* str1, FILE* str2) {
	//打开文件
	FILE* source = fopen(str1,"rb");
	if (!source) {
		perror("source\n");
		exit(1);
	}
	FILE* right = fopen(str2, "wb");
	if (!right) {
		perror("right\n");
		exit(1);
	}
	//逐字符读入，字符判断，右旋。写入目标文件
	int a;
	while ((a = fgetc(source)) != EOF) {
		if ((a <= 'M' && a >= 'A') || (a <= 'm' && a >= 'a')) {
			fputc(a+13, right);
		}
		else if ((a <= 'Z' && a >= 'N') || (a <= 'z' && a >= 'n')) {
			fputc(a - 13, right);
		}
		else {
			fputc(a, right);
		}
	}
	fclose(source);
	fclose(right);
}

002：将一个文件读入程序，在每一行前面添加序号，然后写入另一个文件。如：


Allen
Beyonce
Cindy
Dianna

变成


1. Allen
2. Beyonce
3. Cindy
4. Dianna

解答：


void add_num(FILE* str1, FILE* str2) {
	FILE* source = fopen(str1, "r");
	if (!source) {
		perror("source\n");
		exit(1);
	}
	FILE* add_num = fopen(str2, "w");
	if (!add_num) {
		perror("add_num\n");
		exit(1);
	}
	//行读取  s输出
	char massage1[MAXLINE];
	int line = 0;
	while (fgets(massage1, MAXLINE, source) != NULL) {
		line++;
		fprintf(add_num,"%d.%s",line,massage1);//写入字符串数组
	}
	fclose(source);
	fclose(add_num);
}

003：然后将规范化处理的学生信息，写入新的文件 students.dat.


1 Allen f 100 100 100
2 Beyonce f 90 90 90
3 Cindy f 95 95 95
4 Dianna f 98 98 98

字段的含义分别是：学号、姓名、性别、语文、数学、英语。现在需要对分数进行规范化处理，每个同学的语文成绩需要乘以 0.85，数学成绩乘以 0.9，英语成绩乘以 0.8。然后将规范化处理的学生信息，写入新的文件 students.dat.

解答：


void stu_information(FILE* str1, FILE* str2) {
	FILE* before = fopen(str1, "r");
	if (!before) {
		perror("before\n");
		exit(1);
	}
	FILE* after = fopen(str2, "w");
	if (!after) {
		perror("after\n");
		exit(1);
	}
	//标准化输入
	Stu s;
	while (1) {  //返回转换说明的个数
		int n = fscanf(before, "%d%s %c%d%d%d",
			&s.id,
			s.name,
			&s.gender,
			&s.chinese,
			&s.math,
			&s.english);
		if (n != 6) { break; }
		n++;
		s.chinese *= 0.8;
		s.math *= 0.9;
		s.english *= 0.7;
		fprintf(after,"%3d %10s %2c %3d %3d %3d\n",
			s.id,
			s.name,
			s.gender,
			s.chinese,
			s.math,
			s.english);
	}
	fclose(before);
	fclose(after);
}

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

0627，0628，0629，排序，文件

01：请实现选择排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

02：请实现冒泡排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

03：请实现插入排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

04：请实现归并排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

05：请实现快速排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

06：给定一个排好序的数组，请设计一个算法将数组随机打乱。

解答：

答案：

01：请实现堆排序，并分析它的时间复杂度，空间复杂度和稳定性

解答：

答案：

02：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

解答：

答案：

03：请实现下列二分查找的变种：

解答：

答案：

04：用 fread/fwrite 实现文件的复制。

解答：

答案：

001：将一个文件读入程序，将其中的大小写字母右旋13个位置后，写入另一个文件。

解答：

002：将一个文件读入程序，在每一行前面添加序号，然后写入另一个文件。如：

解答：

003：然后将规范化处理的学生信息，写入新的文件 students.dat.

解答：

02：给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。