排序
确实要总结一下，因为下面写完就忘了上面的一些排序是什么了了，最好就是先写一个简单的描述，用来快速回顾。
考研之前的知识点类似，进过三次变换之后排序变成什么样。请问符合什么排序。所以我们要知道这些排序的特点
默认都是从小到大排序的讲
前置知识点
对于每一个可以排序的值，它不止是一个int，还有其他内容，所以提前定义。
#pragma once typedef int keytype; typedef struct { keytype key; int* data; }element; typedef struct { element* data; int lenght; }sorttable; void insertsort(sorttable* table);排序的依据就是这些元素之间的关键字，key
插入排序
算法本身和两个优化思路
稳定性： 稳定
原始算法
简单描述一下：
就是按从小到大遍历，
如果这个值小于前一个值的话，就临时存储这个值，然后令i-1的值为j，就让这个i值的数一直和j的值比，如果还是小的话就让对应的j指的值后移并使j++（到下一个数），直到i的值是大的，就让临时值放在j+1的位置。
如果这个值本来就是大于i-1的，那就不用动
代码部分:
void insertsort(sorttable* table) { element temp; for (int i = 1; i < table->lenght; i++) { if (table->data[i].key < table->data[i - 1].key) { temp = table->data[i]; int j = i - 1; for (j = i - 1; j >= 0 && table->data[j].key > temp.key; j--) { table->data[j + 1] = table->data[j]; } table->data[j + 1] = temp; } } for (int i = 0; i < table->lenght; i++) { printf("%d ", table->data[i].key); } } 交换排序
和选择排序的思路是一样的，所以就直接省略，直接就用交换排序
冒泡排序
稳定性：稳定
简单描述一下：
冒泡排序之神降下了他的仁慈，让饱受排序之苦之人献上最甜美的佳酿（狗头）。
就是双重遍历，外层负责为内层加上一个范围的限制而已，
内层负责比较和交换，如果发现j的值比j+1的值还要大，就交换他们，j++后这个值指的就是这个较大值了，然后重复比较，使得最大的值放在最后面。下一次的范围就排除最后一个，重复这个操作知道只剩下一个数。
代码部分
（这里简单贴一下只是用int数组的）
int a[] = { 5,9,77,36,8,45 }; int t = 0; int n = sizeof(a) / sizeof(a[0]); for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j + 1] < a[j]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } for (int i = 0; i < n; i++) { printf("%d ", a[i]); } }优化思路：
如果只有后面的极少部分是乱序的，但是前面都是有序的，那么每次遍历的话就会浪费时间，所以提出以下优化。
如果遍历一遍，发现没有交换，就说明这次遍历的范围已经是有序的，就不用再排了，直接break跳出循环。
⼀次优化是为了避免数组有序
void test02() { int a[] = { 1,2,3,4,5,6 }; int t = 0; int n = sizeof(a) / sizeof(a[0]); for (int i = 0; i < n; i++) { /**/ int issort = 1; for (int j = 0; j < n - i - 1; j++) { if (a[j + 1] < a[j]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; /**/ issort = 0; } } /**/ if (issort) { break; } } for (int i = 0; i < n; i++) { printf("%d ", a[i]); } }/**/下面的对比有变化的部分
优化二：
这个是解决只是中间或较前面是乱的，但是其他是有序的情况下
我们加入了一个挡板，每当做出一次交换，挡板就会指向i+1的部分，挡板最后就会停留在最后一次交换，即说明挡板的后面就是有序的，减少了遍历的次数。
否能够确定出已经有序部分和⽆序部分的边界
void test03() { int a[] = { 5,9,77,36,8,45 }; int t = 0; int n = sizeof(a) / sizeof(a[0]); int index = 0; do { index = 0; for (int i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; index = i + 1; } } n = index; } while (index > 0); for (int i = 0; i < sizeof(a) / sizeof(a[0]) ; i++) { printf("%d ", a[i]); } }快速排序
稳定性：不稳定
双边快速排序
运用递归的思想，定义三个指针，即left,right,和pivot，每次都将pivot做为分割，pivot前面的是比pivot小的，pivot后面的是比pivot大的，直到分成分成最小的两个一组，就是left大于等于right的时候
更加具体一点的步骤：就是每次都取这个区间的第一个(或者最后，中间，随机)作为pivot，首先先让right指的值与pivot的值作比较，如果大的话，就继续right--，如果发现比他小的话就是已经发现了一个不应该放在右边的东西，然后使得left的和pivot的比，如果是小的话就一直++，如果是大的话就和right的交换，又从新从right比较开始。（如果一直都是left++，直到right==left也没有关系，因为还是 要进行left和pivot的交换，还是会使这个较小值放在pivot的左边）
代码部分：
代码部分分成三个部分：对外接口的部分，递归部分，核心函数的部分：
对外接口的部分：仅仅提供要排序的表的部分作为参数
void quickSortV1(SortTable* table) { quickSort1(table, 0, table->length - 1); }递归部分，自顶向下的递归思想，不断把一个大人物拆成小任务，先排pivot左边的部分，在排pivot右边的部分，直到这个区间只剩下一个元素就是排好了，用代码表示就是left>=right;
static void quickSort2(SortTable *table, int startIndex, int endIndex) { if (startIndex >= endIndex) { return; } // 找到犄点 int pivot = partitionSingle(table, startIndex, endIndex); quickSort2(table, startIndex, pivot - 1); quickSort2(table, pivot + 1, endIndex); }核心函数：思路就是上面描述的部分
static int partitionSingle(SortTable *table, int startIndex, int endIndex) { keyType tmpValue = table->data[startIndex].key; int mark = startIndex; for (int i = startIndex + 1; i <= endIndex; i++) { if (table->data[i].key < tmpValue) { mark++; swapElement(&table->data[i], &table->data[mark]); } } swapElement(&table->data[startIndex], &table->data[mark]); return mark; }单边快速排序
算法思路:就是分格点边成了mark指针，保证mark 的左边比他小，他的右边比他大，然后对mark和pivot的进行交换。
具体步骤：
令i不断往前++，如果是大于mark的就继续走，如果发现比他小的，就先让mark++ 这时mark指的值已经是确定比pivot大的，而i当前指的值一定是比pivot小的然后交换mark和i 的值，那么mark一直指的就是小于等于pivot的，i最后遍历完之后，在再交换mark和pivot（指向的是第一个，（最后一个，随机））就可以保证前面的是小的，后面的是大的。后面重复这个操作。
对外接口
void quickSortV2(SortTable* table) { quickSort2(table, 0, table->length - 1); }递归的部分：
static void quickSort2(SortTable *table, int startIndex, int endIndex) { if (startIndex >= endIndex) { return; } // 找到犄点 int pivot = partitionSingle(table, startIndex, endIndex); quickSort2(table, startIndex, pivot - 1); quickSort2(table, pivot + 1, endIndex); }核心部分;
static int partitionSingle(SortTable *table, int startIndex, int endIndex) { keyType tmpValue = table->data[startIndex].key; int mark = startIndex; for (int i = startIndex + 1; i <= endIndex; i++) { if (table->data[i].key < tmpValue) { mark++; swapElement(&table->data[i], &table->data[mark]); } } swapElement(&table->data[startIndex], &table->data[mark]); return mark; }堆排序
从1开始
稳定性：不稳定
简单描述一下
堆排序就是依赖类似完全二叉树的逻辑结构，分成小顶堆（根小于左右孩子）和大顶堆（根大于左右孩子）。这里默认写一个小顶堆。主要逻辑，就是分为建堆和排序。
堆的操作可以分为创造 释放 插入 提取
代码部分
创造：在内存中开辟一个空间并初始化一个完全二叉树
miniheap* creatheap(int n) { miniheap* heap= malloc(sizeof(miniheap)); if (heap == NULL) { return NULL; } heap->data = malloc(sizeof(keyType) * (n + 1)); // 完全二叉树从1号下标开始存储 if (heap->data == NULL) { free(heap); return NULL; } heap->capcity = n; heap->len = 0; return heap; }释放：释放空间
void releasemini(miniheap* heap) { if (heap) { if (heap->data) { free(heap->data); heap->data = NULL; } free(heap); } }插入：逻辑上插入元素的时候都是插在了对应完全二叉树的最后一个节点，这就导致了插入这个元素可能会导致这个不符合完全二叉树的性质。
这时候我们就要内置一个上浮函数，让这个值放到他正确位置。逻辑：如果他比他的爸还要小，那么久交换他和他的爸的位置。
void insert(miniheap* heap, keyType e) { /*少考虑了边界的情况，就是如果已经满了就不能插入了*/ if (heap->len + 1 > heap->capcity) { return; } heap->data[++heap->len] = e; up(heap, heap->len); }static void up(miniheap* heap,int k) { /*既然是上浮那么就是找爸,这个k就是这个根节点的下标*/ keyType t; while (k > 1&&heap->data[k] < heap->data[k / 2]) { t = heap->data[k]; heap->data[k] = heap->data[k / 2]; heap->data[k / 2] = t; k /= 2; } } 提取：这里我们都是从小到大的排序，所以我们要提取根元素，但是直接取走，逻辑上根的位置就位空了。所以我们将最后的元素放在第一个保证他们是完整的，然后用下沉函数调整位置。
下沉函数：选择这两个孩子中较小的那一个，然后交换。
keyType extra(miniheap* heap) { if (heap->len <= 0) { return 0; } keyType ret = heap->data[1]; heap->data[1] = heap->data[heap->len--]; shiftDown(heap, 1); return ret; } /*上浮*/ static void up(miniheap* heap,int k) { /*既然是上浮那么就是找爸,这个k就是这个根节点的下标*/ keyType t; while (k > 1&&heap->data[k] < heap->data[k / 2]) { t = heap->data[k]; heap->data[k] = heap->data[k / 2]; heap->data[k / 2] = t; k /= 2; } } 归并排序
稳定性：不稳定
简单描述一下：
利用递归的思想，不断分成最小的部分（仅有一个元素），然后合并左右集合。集合合并的方法，分别产生左右两个集合的临时数组，和分别的指针指向他们的第一个元素，比较大小，然后不小的那个放在原来的数组空间上，小的那个数组向前移动。直到其中一个数组遍历完了，另一个数组是已经排好序了，那么直接将这个数组放在原来的数组后面就行了。
代码部分：
#include"mergesort.h" #include<stdlib.h> /*递归*/ static void merge(SortTable* table, int left,int mid,int right) { /* *1.脑测步骤：先开两个数组 别用i j 表示是两个数组当前指的下标 * * */ int n1 = mid - left + 1; int n2 = right - mid; Element* leftauto = malloc(sizeof(Element) * n1); Element* rightauto = malloc(sizeof(Element) * n2); if (leftauto == NULL) { return ; } if (rightauto == NULL) { free(leftauto); return ; } for (int i = 0; i < n1; i++) { //因为这个不只是前面的那一个 leftauto[i] = table->data[left+i]; } for (int i = 0; i < n2; ++i) { rightauto[i] = table->data[mid + 1 + i]; } int i = 0; int j = 0; int k = left; while (i < n1 && j< n2) { if (leftauto[i].key <= rightauto[j].key) { table->data[k] = leftauto[i++]; } else { table->data[k] = rightauto[j++]; } k++; } while (i < n1) { table->data[k++] = leftauto[i++]; } while (j < n2) { table->data[k++] = rightauto[j++]; } free(leftauto); free(rightauto); } /*这里拆分已经做好，然后就是合并的环节了*/ static void loop(SortTable* table, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; loop(table, left, mid); loop(table, mid + 1, right); merge(table, left, mid, right); } /*归并排序，递归和并*/ void mergeSort(SortTable* table) { loop(table, 0, table->length - 1); } 统计（基数）排序
上面的排序都是基于比较
稳定性：不稳定
这个只能处理整数
简单描述一下：
就是对于一组要排序的数，遍历一次，建立一个数组，每遍历到一个数，就让这个数对应下标的数组++，最后遍历这个数组，输出结果即可。
桶排序
和统计排序差不多，就是把数组改成了一个个区间（桶）
下期更新二分查找和哈希表，喜欢的话记得点点关注，你的一个关注就是我更新的动力。
