插入排序，选择排序，希尔排序

一、插入排序

从头开始依次选取一个元素，和他前面的数比较，

先把值存为 c ，这样就不用交换值了

若比前面的元素大，就让 qq + 1的位置的值改为前面的数，qq 往前移一位

若前面的数小，就把 qq + 1的位置的值改为c

void cha_ru(int* arr, int n) { for (int q = 1; q < n; q++) { int c = arr[q]; int qq = q-1; while (qq >= 0) { if (arr[qq] > c) { arr[qq + 1] = arr[qq]; qq--; } else { break; } } arr[qq + 1] = c; } return; }

二、选择排序

从前往后遍历，最小的放前面，最大的放后面，缩小范围，

若最大的数在最前面，判断一下，因为最小的数交换时把最大的数换到其他位置了

很简单。。。

void xuan_ze(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; ++i) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } int c = a[begin]; a[begin] = a[mini]; a[mini] = c; if (maxi == begin) { c = a[mini]; a[mini] = a[end]; a[end] = c; } else { c = a[maxi]; a[maxi] = a[end]; a[end] = c; } ++begin; --end; } }

三、希尔排序

分为两步

1.预排序

2.插入排序

预排序的目的是

使数组更加接近有序

步骤

设置一个变量值gap

把数组分为gap组

每个元素和他相距 gap-1 距离的元素为一组，就是+gap或-gap得到同组元素

通过插入排序把每组数据顺序排列

最后预排序完成，最后一遍插入排序，得到有序数组

void Shell_pai(int* arr, int n) { int gap = n; while (gap > 1) { gap = gap / 3 + 1; for (int st = 0; st < n - gap; st++) { int s = arr[st+gap]; int qq = st; while (qq >= 0) { if (arr[qq] > s) { arr[qq + gap] = arr[qq]; qq -= gap; } else { break; } } arr[qq + gap] = s; } } return; }