直接插入排序
思路： 我们要记得[0,end]是有序的,我们要把tmp的值插入到[0,end]就要进行判断,直到tmp等于数组的长度结束,这个过程中我们要注意到我们把tmp插入到[0,end] 是要遍历[0,end]的当我们判断当前的元素大于tmp,就把这个元素往后移动,我们就要往后一个元素比较,直到碰见比tmp小的元素,并再该元素后面插入,如果碰见了在[0,end]都没有小于tmp的元素,我们就要在下标为0的地方插入,
void InsertSort(int* a, int n) { //[0,end] int i = 0; for (i = 0; i < n-1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[end] > tmp) { //往后移动 a[end + 1] = a[end]; end--; } else { break; } } //这个写法一箭双雕,一来可以防止end为-1的情况不用去判断,二来可以插入到a[end + 1] a[end + 1] = tmp; } }
冒泡排序
// 冒泡排序 void Bubblisort(int* a, int n) { int i = 0; for (i = 0; i < n - 1; i++) { //如果该数组是一个有序数组,只需遍历一遍下面的就可以了,时间复杂度为O(N) bool excheng = false; int j = 0; for (j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int c = a[j]; a[j] = a[j + 1]; a[j + 1] = c; excheng = true; } } if (excheng == false) break; } }
时间复杂度是O(N^2), 最好的情况就是O(N)
希尔排序
分成两步:
1.预排序 (接近有序)
2.直接插入排序
思路:
相同颜色的框进行插入排序,因为多少种颜色是有gap的数值决定的,每一种颜色对应的是整个数组的一部分
//预排序 int gap = 3; int i = 0; //有gap个数组 for (i = 0; i < gap; i++) { //每个数组进行插入排序 int sub = i; while (sub <= n - 1 - gap) { int end = sub; int top = a[end + gap]; while (end >= 0) { if (top < a[end]) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = top; sub += gap; } }
上面这种是一组组进行插入排序.如果是多组进行插入排序
思路就是我们仍然采用上面的方法,但是我们是多组进行插入排序,仍然是相同颜色的进行插入排序
//预排序 int gap = 3; int i = 0; //有gap个数组 for (i = 0; i <= n - 1 - gap; i++) { //每个数进行插入排序 int end = i; int top = a[end + gap]; while (end >= 0) { if (top < a[end]) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = top; }
预排序的特点:
gap越大,大的值更快调到后面,小的值可以更快的调到前面,越不接近有序
gap越小,跳得越慢,但是越接近有序,如果gap == 1就是直接插入排序
最终代码为
//希尔排序 void ShellSort(int* a, int n) { //预排序 int gap = 3; int i = 0; //有gap个数组 for (i = 0; i <= n - 1 - gap; i++) { //每个数进行插入排序 int end = i; int top = a[end + gap]; while (end >= 0) { if (top < a[end]) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = top; } //直接插入排序 InsertSort(a, n); }
但是我们可以简化一下
我们可以抓住gap=1为直接插入排序
//希尔排序 void ShellSort(int* a, int n) { //预排序 int gap = n; while (gap > 1) { //一来gap等于1时,就是直接插入排序,二来就是gap是随n增大的, //再还有就是gap越小,就越接近有序 gap = gap / 3 + 1; int i = 0; //有gap个数组 for (i = 0; i <= n - 1 - gap; i++) { //每个数进行插入排序 int end = i; int top = a[end + gap]; while (end >= 0) { if (top < a[end]) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = top; } } }
时间复杂度O（N ^1.3）,这个有点难算,我们只需要理解大概就行
直接选择排序
思路：从开头开始找，找到最小的，然后进行和开头交换，然后再从剩下的后面继续寻找最小的，依次往后插入
思路图1：这个思路是很多人能想出来的
思路图2：
这里我是使用了两边，左边插入最小的，右边插入最大的，插入好后，begin往前 ，end往后，直到begin等于end，就停止了
void excheng(int* a, int* b) { int c = *a; *a = *b; *b = c; } //直接选择排序 void SelectSrot(int* a, int n) { int min = 0, max = 0; //找出最大和最小 int begin = 0, end = n - 1;// 在最大和最小的位置插入 for (int i = begin + 1; i <= end; i++) { int idx = i; while (idx <= end) { //找出最小的值 if (a[min] > a[idx]) min = idx; //找到最大值 if (a[max] < a[idx]) max = idx; idx++; } excheng(&a[begin], &a[min]); //防止开头就是最大值,一旦最小值交换,就乱了 if (max == begin) max = min; excheng(&a[end], &a[max]); begin++; end--; } }
时间复杂度是 O（N^2）
堆排序
大家可以观看这部博客
//堆排序 typedef int Heapdata; void exchange(Heapdata* a, Heapdata* b) { Heapdata e = *a; *a = *b; *b = e; } void Heapsort(Heapdata* heap, int size) { //建大堆 int i = 0; for (i = 1; i < size; i++) { //向上调整 int child = i; int parent = (child - 1) / 2; while (child > 0) { if (heap[child] > heap[parent]) { //交换 exchange(&heap[child], &heap[parent]); child = parent; parent = (child - 1) / 2; } else break; } } //开始升序排序 while (size > 0) { // 根节点和最后一个叶节点交换 exchange(&heap[0], &heap[--size]); //向下调整 int parent = 0; int child = parent * 2 + 1; while (child < size) { if (child + 1 < size && heap[child] < heap[child + 1]) { child += 1; } if (heap[child] > heap[parent]) exchange(&heap[child], &heap[parent]); else break; parent = child; child = parent * 2 + 1; } } }
数据结构第六课 -----排序-2
