一.冒泡排序 Bubblesort(升序为例)理解冒泡排序就要明白每次从头到尾进行相邻元素两两之间的比较交换最后都会让本轮数组中最大的数走到数组的最后(有隐形收束边界的意味)当待排数组只剩一个数时冒泡排序就完成了。(很多人说冒泡排序很好理解但我觉得其实理解挺有难度的)1代码实现//升序为例 void Bubblesort(int* arr,int n) { for(int j 0;jn-1;j) { int i 0; int flag 1; for(i 0;in-1-j;i) { if(arr[i]arr[i1]) { Swap(arr[i],arr[i1]; flag 0; } } if(flag) break; } }2细节理解内外层循环各自代表了什么循环条件又有什么样的含义红色循环条件相邻两两元素之间的比较由于我写的是i和i1位置上的元素之间的比较为了不让i1越界所以i首先要小于n-1其次由于没进行完一次从头至尾的相邻两两元素之间的比较就会有一个数据走到了数组后方的正确位置上(以升序为例)所以不需要把正确排序位置上的数据再拉进排序的比较行列中体现在代码上就是in-1-j。绿色循环条件总共要进行n-1次的从头至尾的相邻两两元素之间的比较这样才能确定n-1个数据的正确位置当然也可以排n趟但是没有必要当n-1个数据都已经到了它们的正确位置之后最后一个数据自然就到了它的正确位置。二.快速排序 Quicksort一递归版快速排序1hoare法以升序为例取数组第一个数据下标为key定义begin为数组第一个数据的下标end为数组最后一个数据的下标先判断end对应数据和key对应数据的大小关系如果是key对应数据更大就不要动end如果end对应数据更大就让end--(向前走一步)继续与key对应数据进行大小比较出现key对应数据更大的情况后就去看begin。同样也要判断begin对应数据的下标和key对应数据的大小如果是begin对应数据更小那就不要动begin如果是key对应数据更小那就begin(向后走一步)继续与key对应数据进行大小比较直到出现key对应数据更小的情况再将对应end和begin位置的数据进行交换则比key大的数据走到了数组的后方比key小的数据走到了数组的前方重复上述操作等begin和end相遇之后再将相遇位置的数据和key位置的数据进行交换就能实现数组的升序。这就是hoare法的快速排序。注意可能存在begin、end相遇前并没有进行过一次交换的情况那这就是直接让相遇位置的数据和key位置的数据进行交换就好。1-1.朴素版void Quicksort(int* arr,int left,int right) { //递归结束的条件 if(leftright) return; int begin left; int end right; int key left; while(beginend) { while(beginend arr[key]arr[end]) end--; while(beginend arr[key] arr[begin]) begin; //都找到了要交换的数据 Swap(arr[begin],arr[end]); } //相遇后要和key位置上的数据交换 Swap(arr[begin],arr[key]); key begin; //完成了第一次排序确定了key位置上的数据的正确位置 //递归 Quicksort(arr,left,key-1); Quicksort(arr,key1,right); }1-2.三数取中有时候取得key位置上的值太大了或者太小了就会导致递归时栈太深有栈溢出的风险为了优化这种情况我们可以在头尾和中间的数据中取一个中间值作为arr[key]尽量避免选到太大或太小的数这就是三数取中。int GetMid(int* arr,int left,int right) { int mid (leftright)/2; if(arr[left]arr[mid]) { if(arr[mid]arr[right]) //leftmidright return mid; else { if(arr[left]arr[right]) //leftrightmid return right; else //rightleftmid return left; } } else { if(arr[left]arr[right]) //midleftright return left; else { if(arr[mid]arr[right] //midrightleft return right; else //rightmidleft return mid; } } }void Quicksort(int* arr,int left,int right) { //递归结束的条件 if(leftright) return; int begin left; int end right; //三数取中 int key GetMid(arr,left,right); Swap(arr[begin],arr[key]); key begin; while(beginend) { while(beginend arr[key]arr[end]) end--; while(beginend arr[key] arr[begin]) begin; //都找到了要交换的数据 Swap(arr[begin],arr[end]); } //相遇后要和key位置上的数据交换 Swap(arr[begin],arr[key]); key begin; //完成了第一次排序确定了key位置上的数据的正确位置 //递归 Quicksort(arr,left,key-1); Quicksort(arr,key1,right); }将key位置上的数据和begin位置上的数据交换使key位置还是数组的首位置这样while循环的逻辑就不用改变注意除了要交换数据外还要将begin的值赋给key。1-3.小区间优化快排的递归过程很像二叉树的前序遍历由此我们能大概知道处理最后的一些小区间(叶子)会占到程序执行时间的一半左右如果我们让小区间不再走递归那一套而是直接进行现有的排序(堆排序、插入排序、希尔排序等等)时不时就能实现快排的优化呢实际上确实是这样的。void Quicksort(int* arr,int left,int right) { //递归结束的条件 if(leftright) return; //小区间优化 if((right-left-1) 10) Insertsort(arrleft,right-left1); else { int begin left; int end right; //三数取中 int key GetMid(arr,left,right); Swap(arr[begin],arr[key]); key begin; while(beginend) { while(beginend arr[key]arr[end]) end--; while(beginend arr[key] arr[begin]) begin; //都找到了要交换的数据 Swap(arr[begin],arr[end]); } //相遇后要和key位置上的数据交换 Swap(arr[begin],arr[key]); key begin; //完成了第一次排序确定了key位置上的数据的正确位置 //递归 Quicksort(arr,left,key-1); Quicksort(arr,key1,right); } }1-4.自省排序细节理解①为什么刚好begin和end相遇的位置是小于arr[key]的(先不解释为啥升序是end先走后面自会有详细解释)相遇无非就两种情况要么begin遇到end要么end遇到begin。a.begin遇到endend先走begin遇到end那说明end肯定是停在了某个需要交换数据的位置上也就是end找到了比key位置上的数据要小的数据begin和end的相遇位置就是end停着的那个位置也就是说相遇位置的数据是比key位置数据更小的数据。b.end遇到beginend先走直到遇见begin都没有找到需要交换的数据由于每次都是end先走begin后走等begin停下了了就说明begin和end位置上的数据要交换了则新一轮end遇到的begin是上一轮已经交换过数据的的beginbegin位置上是比key位置更小的数据所以在end遇到begin的情况下相遇的位置的数据还是比key位置的数据要小。②为什么升序需要end先走(先进行判断)降序呢先明确一下什么叫先走(先判断)即先判断end位置上的数据和key位置上的数据的大小关系。让end先走先判断就是为了让end掌握主动权在每一轮比较的开始这样无论是begin遇到找到小数据需要交换的end还是end遇到上一轮已经变成小数据的begin都能保证begin和end相遇位置的数据比key位置数据要小交换后才符合升序的题目要求。如果是降序就应该让begin先走先判断这样begin掌握主动权在每一轮比较的开始当begin遇到end时就是begin遇到上一轮已经换成大数据的end当end遇到begin时就是end遇到找到大数据需要交换的begin了这样才能保证begin和end相遇位置的数据是比key位置的数据大再交换后才能满足题目降序的要求。③为什么内层循环的两个循环条件都带有等号begin从key位置出发会出现key位置的数据在begin和end相遇前被提前换走的情况吗(如何避免)可能乍一想两边的判断都加很奇怪当两边的判断都加上时key位置的数据还能被交换到正确位置上吗?其实是可以的。数组现在的构成是[小于等于arr[key] arr[key] 大于等于arr[key]]arr[key]所处的位置是合适的等排好[小于等于arr[key]]和[大于等于arr[key]]两部分后数组就能成为升序或降序。那可以两边都不加吗不行。有一个特殊的情况当数组的每个值都一样时如果两边的判断都没有加上那么就会陷入死循环。譬如数组[3,3,3,3]begin0key0end3在判断的时候arr[end]3不大于arr[key]需要交换则end停在下标为3的位置arr[begin]3不小于arr[key]需要交换则begin停在下标为0的位置Swap之后arr[end]3和arr[begin]3依旧那么还是不用end--、begin还是继续交换可是交换后只会是无穷的交换这就是陷入了死循环。那可以一边有一边没有吗理论是可以的一边有等号遇到和arr[key]相等的数据时不会停下但另一边没有等号遇到和arr[key]相等的数据时会停下等交换后和arr[key]相等的数据被换到了有等号的那边进入循环进行自减或自增就跳过了与arr[key]相等的数据不会陷入死循环。但这里还有一个问题begin从key位置出发会出现key位置的数据在begin和end相遇前被提前换走的情况吗我们是通过什么来避免的先说结论这个问题确实是会发生的可我们能通过下面的红色语句来避免也就是在比较时加上等号。在begin比较时加上等号这样从下标为0位置开始的begin遇到和arr[key]数据相等的数据时就可以进入循环begin跳过第一个值这样就不会存在key位置的数据在begin和end相遇前被提前换走的情况了。所以结论是不管end如何begin这一端一定要加上等号。④为什么内层循环的循环条件还有与一个beginend?如果不与上beginend那么到执行交换的语句的条件是end和begin都找到了要交换的数据那么就不能处理begin和end相遇的情况当begin遇到end时end停在了大于arr[key]的位置可begin不会停下而是会直接路过end向后走。所以需要与beginend。⑤为什么是定义数组首元素的下标为key而不是数组首元素的值为key呢需要能真正交换数组内的数据就不能是对临时变量进行交换所以是下标而不是拷贝了数组值的临时变量有点传值调用传址调用的意味。⑥为什么递归的结束条件是leftright?等于比较好想就是区间内只有一个数据此时直接return但leftright其实可以假定keyright在进入新的函数后leftkey1right原1rightright原那么就有leftright了这种情况也是不用再排序了递归了直接return就好。2前后指针法(升序为例)如上图的初始情况判断arr[cur]和arr[key]的大小如果arr[cur]大于arr[key]那就直接让cur向前走一步如果arr[cur]小于arr[key]那就让prev向前走一步然后交换pcur和prev位置的数据再让cur向前走一步直到pcur走出边界外最后再将prev位置的数据和key位置的数据进行交换就行。2-1 代码实现void Quicksort(int* arr,int left,int right) { //递归的结束条件 if(rightleft) return; //小区间优化 if((right-left1) 10) Insertsort(arrleft,right-left1); else { //三数取中 int mid GetMid(arr,left,right); Swap(arr[left],arr[mid]); int key left; //前后指针法 int prev left; int pcur prev1; while(pcurright) { if(arr[pcur]arr[key]) { prev prev1; Swap(arr[prev],arr[pcur]); pcur pcur1; } else pcur pcur1; } Swap(arr[key],arr[prev]); key prev; //确定好了key位置对应的数据的位置 //递归 Quicksort(arr,left,key-1); Quicksort(arr,key1,right); } }2-2 细节分析①前后指针是怎么实现升序的过程是prev从数组第一个位置开始pcur从数组的第二个位置开始判断arr[pcur]和arr[key]的大小如果arr[pcur]更大则只让pcur向下走一步这样大于arr[key]的数也被夹在prev和pcur之间如果arr[pcur]更小则prev先向下走一步(prev走到了prev和pcur之间夹的大于arr[key]的数据)再交换prev和pcur对应数据这样小于arr[key]的数据就被换到了prev的位置上大于arr[key]的数据就被换到了pcur的位置上再让pcur走一步这样大于arr[key]的数又被夹在了prev和pcur之间。按照这个过程进行下去当pcur走出边界时prev和pcur之间夹的是大于arr[key]的数据prev位置的数据是小于arr[key]的最后再交换prev和key位置的数据就能让key走到它的正确位置。此时数组的构成就是[小于等于arr[key] arr[key] 大于等于arr[key]]。等排好各个区间的顺序之后就能实现升序。②代码还能实现优化吗当pcur和prev之间没有夹数据时pcur遇到比arr[key]小的数据时prev向后走一步则prev和pcur指向了数组的同一位置那么prev和pcur的数据交换就是pcur自个之间的交换这步其实是可以省略的两个分支下都需要进行pcurpcur1那就不用单独写else了直接把pcurpcur1提出来。最终的优化代码如下while(pcurright) { if(arr[pcur]arr[key] prev ! prur) //前置prev后与pcur进行大小比较 //如果不相等才进入if语句进行交换 Swap(arr[prev],arr[pcur]); pcur pcur1; }3挖坑法(升序为例)取arr[key]arr[0]数组的第一个位置形成坑位end从数组最后先往前走找比arr[key]小的数据找到后填入数组的首位置(也就是坑位)那end停下的位置就是新的坑位begin从数组前方向后找比arr[key]大的数据找到后填入坑位然后begin停下的位置就是新的坑位了直到begin、end相遇再将arr[key]填入begin、end坑位里。4三路划分当待排数组中的数据大量重复且选中的key坐标对应数据就是这些重复值时递归形成的二叉树就非常不匀称这样排序的性能就会从O(NlogN)退化向O(N^2)这里我们介绍一种可以解决此类问题的思路——三路划分。无论是在hoare还是前后指针的方法中我们都没有考虑和arr[key]相等的数据的位置即不会主动去改变和arr[key]相等的数据的位置这就会导致只在一边拼命递归从而降低了排序的效能。所以三路划分和上面两种方法不同的是它考虑了和arr[key]相等的数据的位置的排放。(以升序为例)即实现一轮排序让和arr[key]相等的数据全部放在中央比arr[key]小的放左侧比arr[key]大的放右侧这三段就是三路划分。如下图所示4-1 思路分析在三路划分中key记录的是数组最左侧的元素的值而非最左侧元素的下标至于为什么也很好理解。在前面的方法中记录最左侧元素的下标既可以找到key位置对应的值(最后才改变数组最左侧的元素所以比较的数据一直都是arr[key])又能顺利实现arr[]begin]/arr[end]和arr[key]的交换。而在三路划分中数组最左侧的元素从一开始就可能发生位置交换那么记录下标就需要频繁地变动下标的值很麻烦再加上我们只是需要一个用于与arr[cur]比较的数值key每次交换的是arr[left]和arr[right]而不是arr[key]所以不如直接记下元素的值。当面对有大量跟key相同的值时三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段【比key小的值】【跟key相等的值】【比key大的值】所以叫做三路划分算法。步骤①key默认取left位置的值该用三数取中的依旧继续交换位置②left指向区间最左边right指向区间最后边cur指向left1位置③-1cur遇到比key小的值后跟left位置交换换到左边leftcur③-2cur遇到比key大的值后跟right位置(不管right位置的值大小如何)交换换到右边right--③-2交换后并不改变cur的值因为我们并不知道和cur交换位置的right位置的数据是大于、等于还是小于key所以还需要继续判断cur和key位置的值的大小关系。归根结底只有当cur位置的值等于key的时候才会cur③-3cur遇到跟key相等的值后cur④直到cur right结束一轮排序⑤递归。4-2 代码实现void Quicksort(int* arr,int left,int right) { //递归的结束条件 if(rightleft) return; //小区间优化 if((right-left1) 10) Insertsort(arrleft,right-left1); else { //三数取中 int mid GetMid(arr,left,right); Swap(arr[left],arr[mid]); int key arr[left]; //直接记录数值 int begin left; int end right; int cur left1; while(curright) { if(arr[cur] key) { //大于key Swap(arr[cur],arr[right]); right--; } else if(arr[cur] key) { //小于key Swap(arr[cur],arr[left]); cur; left; } else { //等于key cur; } } //[begin,left-1] [left,right] [right1,end] //递归 Quicksort(arr,begin,left-1); Quicksort(arr,right1,end); } }二非递归版快速排序快速排序最关键的是每次排序时的边界left、right(begin、end)只要每次都知道边界其实排序并不难要能存储边界值又要能模拟体现递归的过程我们可以利用栈实现快速排序的非递归。1代码实现void QuicksortNonR(int* arr,int n,int left,int right) { ST st; STInit(st); STPush(st,right); STPush(st,left); while(!STEmpty(st)) { int begin STTop(st); int begin0 begin; STPop(st); int end STPop(st); int end0 end; STPop(st); //三数取中 int mid GetMid(arr,begin,left); Swap(arr[begin],arr[mid]); int key begin; //三法取一 while(beginend) { while(beginend arr[key]arr[end]) end--; while(beginend arr[key] arr[begin]) begin; //都找到了要交换的数据 Swap(arr[begin],arr[end]); } //相遇后要和key位置上的数据交换 Swap(arr[begin],arr[key]); key begin; //右区间[key1,end0] //左区间[begin0,key-1] if(key1end0) { STPush(st,end0); STPush(st,key1); } if(begin0key-1) { STPush(st,key-1); STPush(st,begin0); } } STDestroy(st); }也可以小区间优化。2细节理解栈是如何模拟实现递归的过程的栈是先进后出则我们先存右边界再存左边界这样取出来就是先得到左边界再得到右边界为了模拟递归的过程那排序也是要先处理好左区间再看右区间那么入栈应该是是入右区间的右左边界再入左区间的右左边界这样才能先取出左边界如果左边界还能细分就继续入栈小边界的边界值就不会立刻取出右边界处理右区间的排序而是先深入处理完左区间这和递归的过程是相同的。——end——