12.常用排序与查找.md

常用排序和查找

排序：

• 冒泡
• 插入
• 选择
• 快速排序
• 并归排序

排序和查找的关系

排序是查找的前提，排序是重点。

快速排序

# include <stdio.h>

/**
 * 第二个参数表示第一个参数的下标
 * 第三个参数表示最后一个参数的下标
 */
void quickSort(int *, int, int);

int findPos(int *a, int low, int high);

void main() {
	int a[6] = {2, 1, 0, 5, 4, 3};
	quickSort(a, 0, 5);
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

void quickSort(int *a, int low, int high) {
	if (low >= high) return;
	int pos;
	if (low < high) {
		pos = findPos(a, low, high);
		quickSort(a, low, pos-1);
		quickSort(a, pos+1, high);
	}
}

int findPos(int *a, int low, int high) {
	int val = a[low];
	while (low < high) {
		while (low < high && a[high] >= val) {
			high --;
		}
		a[low] = a[high];
		while (low <high && a[low] <= val) {
			low++;
		}
		a[high] = a[low];
	}
	a[low] = val;
	return low; // 或return high;
}