3.14学习总结 排序算法

插入排序：

1.直接插入排序

维护一个有序区，把元素一个个插入有序区的适当位置，直到所有元素都有序为止。

for (int i = 0;i < n - 1;i++) {//升序
	int end = i;
	int temp = k[end + 1];
	while (end >= 0) {
		if (temp < k[end]) {
			k[end + 1] = k[end];
		}
		else {
			break;
		}
		end--;
	}
	k[end + 1] = temp;
}

2.折半插入排序  二分法查找插入位置

3.希尔排序

void shellsort(int* arr, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 2;
		for (int i = 0;i < n - gap;i++) {
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0) {
				if (tem < arr[end]) {
					arr[end - gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

交换排序：

1.冒泡排序

for (int i = 0;i < n - 1;i++) {//从小到大排序
	for (int j = 0;j < n - 1 - i;j++) {
		if (a[j] > a[j + 1]) {
			t = a[j];
			a[j] = a[j + 1];
			a[j + 1] = t;
		}
	}
}

2.快速排序

int a[1000], n;//需要排序的数，以及总数
void quicksort(int left, int right) {
	int i, j, t, temp;
	if (left > right) {
		return;
	}
	temp = a[left];
	i = left;
	j = right;
	while (i != j) {
		while (a[j] >= temp && i < j) {
			j--;
		}
		while (a[i] <= temp && i < j) {
			i++;
		}
		if (i < j) {
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	a[left] = a[i];
	a[i] = temp;
	quicksort(left, i + 1);
	quicksort(i + 1, right);
	return;
}

选择排序：

1.简单选择排序

2.树形选择排序

3.堆排序

归并排序：

基数排序：

1.多关键字排序

2.链式基数排序

外部排序：

1.外部排序的基本办法

2.多路平衡归并的实现

3.置换—选择排序

4.最佳归并树

（有代码的已学。