【C-数据结构与算法】408必背算法

1. 顺序表相关

1.1 快速排序

#include <stdio.h>


// 划分序列
int Partition(int arr[],int low,int hight) {
	int pivot = arr[low];// 设最左边的数为枢纽
	while (low < hight) {
		// 从右往左，找到第一个小于pivot 的数，再将其放入low指向位置
		while (low < hight && arr[hight] >= pivot) {
			hight--;
		}
		arr[low] = arr[hight];
		// 从左往右，找到第一个大于pivot 的数，再将其放入hight指向位置
		while (low < hight && arr[low] <= pivot) {
			low++;
		}
		arr[hight] = arr[low];
	}
	// 最终 low 和 hight 都指向了同一个已经被使用过的元素，把pivot填入即可
	arr[low] = pivot;
	return low;// 返回中间元素下标

}

void Qsort(int arr[], int low, int hight) {
	if (low < hight) {
		int mid = Partition(arr, low, hight);
		Qsort(arr, low, mid - 1);// 左边区域继续划分
		Qsort(arr, mid + 1, hight);// 右边区域继续划分
	}
}

void printArr(int arr[],int arrLength) {
	for (int i = 0; i < arrLength; i++){
		printf("%4d",arr[i]);
	}
	printf("\n");
}


int main() {
	int arr[10] = {7,2,6,3,4,6,9,0,-1,100};
	printf("排序前：");
	printArr(arr, 10);// 排序前
	printf("排序后：");
	Qsort(arr,0,9);
	printArr(arr, 10);
	return 0;
}

1.2 二分查找

#include <stdio.h>

int BinarySearch(int arr[],int key,int length) {
	int low = 0,hight = length-1,mid;
	while (low <= hight) {// 左右指针不重合，开始二分查找
		mid = (low+hight)/2;// 中间坐标为mid
		if (arr[mid] == key) {// 如果中间值与目标值相等，则返回下标
			return mid;
		}else if (arr[mid] < key) {// 如果中间值在key左边，往右继续查找
			low = mid + 1;
		}else{// 如果中间值在key右边，往左继续查
			hight = mid - 1;
		}

	}
	return -1;
}

void main() {
	int arr[5] = {4,6,8,9,12};
	printf("%d", BinarySearch(arr,7,5));


}