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.最佳归并树

（有代码的已学。