-
排序1：快速排序(三种)、归并排序、计数排序
快排
1. hoare法
- 思路：
- 每次确定一个key【首元素】位置，从此分了两个区间：【0，key-1】，【key+1，end】。
- 每个内部排序是双循环：取第一个为key，R先走，R找小，L找大，注意不要越界。每次循环内部做交换，为交换大小值。最后外面再交换的是相遇位置和keyi做交换。
- 分析：L、R相遇位置是否永远能keyi做交换。即是否相遇位置永小于key。
如果L先遇R：因为R先起步，R位置停在小于key处，可以交换。
如果R先遇L：因为上次L交换完R，L处已经是小于key的值了。 - 总之，以R先找小的快排，最后直接交换相遇位置和keyi。
代码分析：
- 局部Sort的参数：需要给L、R区间范围，已经数组名。
递归或非递归总体：需要给L、R、数组名，所以两个函数的参数一样。 - 出错：递归的出口应该在快排本身上
- 每个partSort()中没有递归，只是在不断交换做key的定位。
- R先行，找小，（等于也略过。） 先写越界判断再比较值，因C语言错误读不报错。
- 递归出口：快排是不断在以key为间隔的两个区间做排序。递归出口是：L>=R。什么时候可能：L>=R：如果经过一轮快排，key定在末尾，那么右区间【key+1, end】，此时key+1>end。，且左区间是:【L，keyi-1】，**不小心当然多写一个成【L,keyi】也没事。
- 代码：
int partSort_hoare(int* a, int L, int R) { int keyi = L; int key = a[L]; while (L < R) { while (L< R && a[R] >= key) R--; while (L < R && a[L] <= key) L++; Swap(&a[L], &a[R]); } // 此时，两个应该相遇了，直接交换 int meeti = L; Swap(&a[keyi], &a[L]); return meeti; } void quickSortBy_hoare(int* a, int L, int R) { if (L >= R) return; int keyi = partSort_hoare(a, L, R); quickSortBy_hoare(a, L, keyi-1); quickSortBy_hoare(a, keyi + 1, R); } int main() { int a[] = { 3, 2, 2, 11, 3, 44, 0, 7, 66}; quickSortBy_hoare(a, 0, sizeof(a) / sizeof(int)-1); PrintArray(a, sizeof(a) / sizeof(int)); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 时间复杂度分析：
每次分为两个区间，时间复杂度是：树的深度次局部sort()，而每层接近堆n个数做排序移动，所以总体是O(NlogN)。
- 空间复杂度：
因为做栈递归，需要参数使用函数栈帧，也就是上面说的递归树的深度次，O(logN)。
- 稳定性分析：
不稳定。比如 5， 5 ，6 ，7 ,1，2, 3 做快排，第一个5因为选为k，最后会在中间，和第二个5相对位置发生了改变。
- 犯过的错：
- 要交换的是&a[keyi]，而不是key值，我为了比较方便写了key变量。
- 递归是在Quick函数中，每次的partSort不做递归。
当快排面对基本有序时，选取的数字过于小，每次做完，分的区间不够均匀，可能某一边过多、过少。
2. 三数取中的挖坑法
- 三数取中：
注意是要拿数组下标，所以传入数组。
int getMidIndex(int* a, int l, int r) { int mid = (l + r) / 2; if(a[l]>a[r]) { if (a[r] > a[mid]) return r; // mid > r else if (a[l] < a[mid]) return l; else return mid; } // l- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 挖坑法快排：
- 代码：
int getMidIndex(int* a, int l, int r) { int mid = (l + r) / 2; if(a[l]>a[r]) { if (a[r] > a[mid]) return r; // mid > r else if (a[l] < a[mid]) return l; else return mid; } // l- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 代码分析：
挖坑法和霍尔方法非常相似，但是记得要等号也要跳过，递归给出口，时刻要更新坑位。找到一个值后，把这个值填入上一个坑，随后坑位做更新。
且先取中间。
R找小，找到小，就填坑。
L找大 填坑。
最外面，相遇位置，填入key。
因为一开始keyi位置空出来了，把R找到小的填过来，小的前去了，之后L找到的大的，填到之前R找到的位置，R在后面，所以使得大的后去了- 遇到的BUG问题：
- 卡在指针挪不到后面了：F5按，L和R都卡着不动了。查旧的记录才反应过来，其实仔细想想，肯定是指针挪动的条件不符合了，我忽略了等于号。
相等也应该掠过。
相等也应该掠过。
相等也应该掠过。
2. 还是卡着不动
递归没有出口：太阳你个麻麻，找了半个小时。
快排是递归，要有出口，所有递归都要有出口
快排是递归，要有出口，所有递归都要有出口
快排是递归，要有出口，所有递归都要有出口3. 前后指针法【也利用三数取中】
思路：【也先做三数取中】描述：prev和cur一开始挨着，且prev处是key值，cr找到大于等于key的值，就继续往后走，prev不动。【因为希望prev和cur之间夹着大于或等于key的值】cur找到小于，就和prev的下一个交换。总之，cur找到小就让prev++做交换。
- 使用指针：prev、cur。
- prev一开始是keyi，cur是prev的下一个
- cur遍历【1，R】，寻找所有小于key的位置。
- 当a【cur】>=key，就略过，做加加：cur++，因为cur要找小。此时，prev和cur中间夹着大于和等于的值。
- 如果a【cur】
- 最后做keyi与prev的交换。且返回prev，因为位置固定了。
代码（普通版本）
int partSort_frontAback(int* a, int L, int R) { int key = a[L]; int keyi = L; int cur = L + 1; int prev = L; while (cur <= R) { while (cur<=R && a[cur]>=key) { cur++; } if (cur <= R && a[cur] < key) { prev++; Swap(&a[cur], &a[prev]); cur++; } } Swap(&a[prev], &a[keyi]); return prev; } void quickSortBy_frontAback(int* a, int L, int R) { if (L >= R) return; int keyi = partSort_frontAback(a, L, R); quickSortBy_frontAback(a, L, keyi-1); quickSortBy_frontAback(a, keyi+1, R); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
代码（升级版）
改进思路：- cur处不管大于还是小于key都要往后走。
- 如果cur到了小于位置，但prev和cur挨着【prev下一位是cur】，那就prev只往后走【因为prev和cur之间只能夹着大于等于，小于要略过】，prev加加就行。
// 不管咋样，cur++。内部只有在cur小于时，才有prev的操作 // 最后prev是小于位置 int partSort_frontAback(int* a, int L, int R) { int mid = getMidIndex(a, L, R); Swap(&a[mid], &a[L]); int key = a[L]; int keyi = L; int prev = L; int cur = L + 1; while (cur<=R) { if (a[cur] < key) { prev++; Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); return prev; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 代码分析：
总之，改进就是cur一直++，只有cur在小于key位置，才动prev，让prev++，再交换。最后再prev一定是小于位置，与开头交换。再返回prev。
快排的非递归写法
- 思路：需要借助栈。把以前递归做的左右区间排序交给了栈去做，利用栈去存参数，然后取出去做排序。
- 注意点：
- 如图，参数别混。我犯了错
- 可以判断一下，该区间是否只有一个值。
- 时间复杂度：
树的深度是logN次，而每次共n个数。总之O(NlogN)。 - 空间复杂度：
在栈递的调用上，需要树的深度层：O(logN)。
归并排序
- 整体流程：
先递归拆分到只剩下一个值或没有值。将序列拆到每个数字一组（每个数字看作已有序的数组），然后两两合并，不断两两合并。
每个数字一组时的归并：第一组：比较两个数组的头进行比较，选取较小的，放到头部，发现左边已经空了，把右边依次放进去。第二组：同第一组。
两个数字一组时的归并：
第一组：左序列和右序列头部左比较，右边头更小则挪到新数组中。如下挪9后，右序列头部变成了17，此时还是右边头更小，当一个序列（这里是右序列）空了后，把左边依次挪到到新数组中。
但是有多余剩下了两组数据。
最后做两组的归并，还是比两个有序序列的头部，然后挪动到新数组。
递归思路：
所有子区间有序才可以做归并，所以递归拆到每个数组只剩下一个数
做法：每次取中，然后从拆开。借助第三方数组做归并，归并到第三方数组，再把归并结果拷贝回原数组。再对原数组做归并。
什么时候是大于等于。- 代码：
void _mergeSort(int* a, int* tmp, int left, int right) { if (left >= right) { if(left>right) printf("存在大于情况\n"); return; } int mid = (left + right) / 2; _mergeSort(a, tmp, left, mid); _mergeSort(a, tmp, mid+1, right); int begin1 = left; int end1 = mid; int begin2 = mid+1; int end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; while (begin1 <= end1) tmp[i++] = a[begin1++]; while(begin2<=end2) tmp[i++] = a[begin2++]; for (int j = left; j <= right; j++) a[j] = tmp[j]; } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) printf("malloc fail\n"); _mergeSort(a, tmp, 0, n-1); free(tmp); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 代码分析：
// 归并的核心：需要一个临时数组上做归并，再把结果返回给原始数组。
// 归并需要两个有序的区间，且两个区间都有序所以一开始拆到单个数字【因为算有序】才行
// 以mid拆，拆两个区间。
// 递归不能一直这样下去，需要出口：left>=right，=时，是只有一个数字，大于不存在。
// 第一次下到这里来说明两个区间有序了。
// 两个区间开始比较，比较需要两个都存在。
// 在tmp上做归并：给tmp赋值，需要从left开始。
// 赋值过程中已经做了++。所以while就够了
// 最后再把归并结果给a：
最后注意参数：给的是n
MergeSort(a, sizeof(a) / sizeof(int))。此外，所有递归且需要分区间去做的这种，都需要写一个核心递归子函数。
- 过程的部分描述：
递归中，归并的两个区间，不一定长度一样，但是都一定有序。
- 过程的部分描述： 比如这里这一部分，看出，对于【0,4】=>【0,2】【3,4】，其中【0,2】=>【0，1】，【1，2】，其中【0,1】=>【0，0】、【1,1】。
此时，【0,0】为参数调用merge_sort直接返回了，然后来到【1,1】，【1，1】也返回，来到了【0,1】这一段就往下走，排序好00和11。以【0,1】为左区间的【0,2】做完第一行递归。然后它继续做【2,2】，然后【2,2】直接有序，随后递归返回，做的是【0,2】的【0,1】和【2,2】的归并。
这里发现归并的递归实现，左右区间不一定等长，且不用担心左区间存在而右区间不存在，因为每次都会取中做拆分。
非递归的归并排序
归并简单来说：
如下图，从a中取数字做归并拷贝到tmp中，再拷贝回a，再重复之前操作。
- 非递归写法：
引言： 递归写法中，因为每次对区间求mid，然后分左右区间，所以所有区间都不是单一存在的，有一个区间就有另外一个和要做归并的区间。但是如果利用非递归写法，从【1,1】归并，然后【2,2】归并，最后【4，4】，过程中借助gap变量。而这样的缺点就是： 需要判断归并整体能否按当前的gap完美划分。
总之，利用gap的变化，然后通过i控制第几组做归并，一组有两个区间，因为gap固定，gap是一个区间的数数量，因为递归有出口，判断到left>=right会return，而非递归gap固定，会面临：
- 第二个区间不够
- 第二个区间不存在
- 第一个区间不完整
以上三个情况，第二个和第三个都可以停止归并，而第一个需要修改end2的区间末尾。所以2、3情况合并后，可以写成 begin2>=n。直接break。但是写end1>=n不能包括第二个不存在的情况。所以写begin2>=n。
如果是区间2不完整，因为经过了上面的begin2>=n判断，没有做break。那么是end2>=n后，做end2的修改：end2=n-1;继续做merge即可。 - 递归和非递归的表面区别是：非递归一次性做1个组的两个区间一般长度一致，而递归中1组的两个区间不一定长度一致。
- 代码：
void merge_NoR(int* a, int* tmp, int begin1, int end1, int begin2, int end2) { int i = begin1; int j = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; } while (begin1 <= end1) tmp[i++] = a[begin1++]; while (begin2 <= end2) tmp[i++] = a[begin2++]; for (; j <= end2; j++) a[j] = tmp[j]; } // 思路是：对一个数组，gap个为1组，每两个gap，做归并。 // 归并区间：0组：【0，0】和【1，1】，1组:【2,2】【3,3】 // 和下面对应起来了 i=0,【0，0】，【1，1】之后，第二组，i=1时，【2,2】【3,3】 // gap 一开始是1，第0组，区间1：[i, i+gap-1], 区间2[i+gap, i+2*gap-1]， // 做第二组归并，i+=2gap：原因如下： // 而i的范围：i不可以超过n-1，现在我不确定，i只小于n-1，那加上gap会不会超， // 所以用i- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 犯的错：
如下图：我犯了的错，发现排序结果数组a没有改变，调试F11发现每趟归并时，tmp改变了而a没有变，然后代码运行中最下面的赋值循环没进去，所以断定是范围给错了，最后再查，发现是赋值的时候，使用j=i，不能在for下面定义，此时i已经变了，int j = begin1应该放在最开始。
- 归并时间复杂度：
从递归上理解，相当于每次做n个数的排序，然后做logn层。所以是Onlogn。
- 归并空间复杂度：
递归的栈调用相当于树的深度：O(logn)。 - 归并的稳定性：
归并是稳定的，因为归并两个区间都是挨着的，可以让相等情况不挪动，能保证稳定。
内排序和外排序
- 内排序：在内存中就可以排序。
- 外排序：数据量较大，比如有10亿个整数，内存中放不下，数据在磁盘文件中，需要外排序。
归并排序既适应外排序、又适应内排序。 - 场景：
分析：10亿整数，40亿字节（10亿字节=1G），数据4G，内存512M，需要切8份数据。
做法：可以切文件，但是切到每份文件1个再排序太费劲了。所以可以对该文件每次读1/8，然后先对这1/8做排序，再存为一个文件。最后得到8个排序好的子文件。
如下图：得到8个有序小文件。
接着，小文件两两归并：生成大小为2倍的当中进行归并。
其中A1、A2做归并，并不会直接将两个512MB的文件读入到内存，而是从两个文件中每次读取一个数字进内存，然后进行比较，小的再写入归并后的文件。
之后操作1G文件，读取也只是从两个1G文件中读取1个数字，512MB内存没问题，并不是一次性打开1G文件。（打游戏同理，并不是直接在内存中打开几十G的游戏文件）
比较排序
- 介绍：这是一种统计密集数据的计数方式。适合比较数据较密集的数组。
- 思想：先创建临时数组count，数量与待排序的a同为n，且利用memset把数组初始化为0。第一次对待排序数组a遍历找出【a】max、min。第二次遍历时用每个a【i】- min，得到差j，在差位置j处做++，该数字有几个，就会加几次。最后，通过遍历count数组，如果当前cout【j】不是0，说明有值，且因为j是数组中数字与min的差，所以通过遍历count【j】先遍历到的，就是a中的较小小值，加上min，就是原始值。
- 注意点：
巧妙之处：
- 存count时，给下标为a【i】-min位置做++。这样在当前数与min的差值处存了值，且count【j】值++次数数字表示有几个数相同。此外，做a【i】- min时已经在做排序了。
- 在给a返值时，通过遍历count【j】，此外用while【count–】，可以对a赋值相同数字次数。给a值时，用j+min，得到原始值。
void CountSort(int* a, int n) { int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; int* count = malloc(sizeof(int)*range); memset(count , 0, sizeof(int)*range); for (int i = 0; i < n; i++) { count[a[i] - min]++; } int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j+min; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
时间复杂度分析：
归并排序：
宏观上，虽然每一层的区间数量不同，但是每层总共对N个数字做归并，高度是LogN，所以总时间复杂度：O(NlogN)。
希尔排序：
时间复杂度O(n^1.3)
缺点：需要O(N)时间复杂度注意快排和归并排序传入的参数大小不一样。
稳定性分析
冒泡、插入、归并是稳定的，剩下都不稳定
冒泡
void BubbleSort(int*a, int n) { for (int i = 0; i < n - 1; i++) { for (int j = n-1; j >= i ; j--) { if (a[j] < a[j - 1]) Swap(&a[j], &a[j-1]); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
思路：
每次让最大或最小的下去或上去，且遍历范围每次要少1。所以必须双层循环。- 双层循环外层控制每次固定的位置，范围：i：【0, n-2】，因为n个数，做n-1次排序即可。剩余一个绝对有序。
- 内层循环，j = i，相当于依次固定【0，n-1】中第一个，让小于上浮，让j减减，所以j>=i，不必>= 0，因为每次固定最上面一个。
稳定性分析：
冒泡排序是稳定的，因为遇到等于情况，可以不做交换。
-
相关阅读:
【MFC】tab控件 仿任务管理器 枚举窗口和进程
【python基础】字典和集合
《011.SpringBoot之餐厅点餐系统》
OKHttp请求上传文件
.Net CLR GC动态获取函数头地址，C++的骚操作（慎入）
在Linux上安装部署JDK和Tomcat（超级详细）
使用指纹的锁屏解锁流程
Factory Method
【Hadoop】第一个MapReduce程序 - WordCount - Windows本地运行
[Python]Django 学习笔记目录
- 原文地址：https://blog.csdn.net/myscratch/article/details/126566664
