怎么用百度云做网站空间,海外网站加速免费,电子商务概论知识点,源码网站程序关于快速排序#xff0c;网上#xff0c;和维基都有完成的解释#xff0c;他们都是。。。。。。#xff0c;俺觉得都是#xff0c;太过于总结话语在概述一些东西#xff1b; 而我却从最本质的东西#xff0c;一步一步的深入#xff1b;在深入的学习过程中#xff0c;我…关于快速排序网上和维基都有完成的解释他们都是。。。。。。俺觉得都是太过于总结话语在概述一些东西 而我却从最本质的东西一步一步的深入在深入的学习过程中我得到如下非代码层面上的感悟 A.一个完整的模式代码或者其他东西都是通过没有part0part1part2version0viersion1.......versionNperfect 最后达到一个完成的形式 如果你只是去学习和体会最后的那一个完成的版本而没有经历整个探索的过程你的体会也不会太多 B.有时候要学会抽象化和跳跃化的去思考问题而不是step by step这有点不具体下次我结合具体的实例来解释 C.帮助别人解决问题并不是直接给出问题的答案或者结果而是给别人一些引导和资源让他自己去解决这点来自使用stackoverflow提问的感受 D.还有第四点要学会从特殊具体到一般抽象的探索过程比如我们可以先总结出满足大于零的规律然后是小于零的规律然后是等于零的规律这些都是特殊或者你可以理解成具体从这些特殊规律总结出一般性通用性的规律 E.还有当研究出了算法之后要学会如何去验证自己的一般性规律在我们的code就是要学会写测试用例进行验证 好了废话不多了直接从代码开始开始之前想尝试做下面的practice; 1.选择数组的第一个data(target)将数组分成两部分满足: minArrtargetmaxArr; 2.选择数组的第一个data(target)将数组分成两部分满足: minArrtargetmaxArr; 并将target 放入数组“中间位置“满足 target greater than left data and less than right data; 3.找出value 在有序数组中的位置 4.找出value 在无序数组中的位置这个位置应该满足它在有序数组中应该具有的位置greater than left data and less than right data; 5.在不开辟内存的情况下使用新的数组来存储值完成问题2 6.关于递归的学习和使用具体看这篇文章的后半部分http://www.cnblogs.com/mc67/p/5114008.html 7.三种方式来实现我们的额快速排序本质的区别只有两种 8.通过Unit Test 来验证我们的代码 关于前面的 5个问题我就直接上代码你细细品味建议在没有看代码前完成上面的问题 /// summary/// 最基本的将数组分成两部分一部分比target小一部分比target大/// /summary/// param namearr/paramstatic void SplitArray(int[] arr){int len arr.Length;int target arr[0];Listint min new Listint(len); //为了方便这里我使用ListListint max new Listint(len); //为了方便这里我使用Listfor (int i 1; i len; i) //从第二个元素开始查找{if (arr[i] target){min.Add(arr[i]);}else{max.Add(arr[i]); // as euqual condition,I put it into max;}}}/// summary/// split the arr and put the target in the right position(greater than left ,less than right)/// /summary/// param namearr/paramstatic void SplitArray1(int[] arr){int len arr.Length;int target arr[0];Listint min new Listint(len); //为了方便这里我使用ListListint max new Listint(len); //为了方便这里我使用Listfor (int i 1; i len; i) //从第二个元素开始查找{if (arr[i] target){min.Add(arr[i]);}}//put it in the last of min, that can make sure target greater than min(left)min.Add(target);for (int i 1; i len; i) //从第二个元素开始查找{if (arr[i] target){max.Add(arr[i]);}}min.AddRange(max); //that can make sure mintargetmax}/// summary/// optimze the SplitArray1/// 上面的代码还是有问题的如果有重复的值那么将在判断max的时候丢掉/// 那么问题来了如果相等的如何判断呢;/// /summary/// param namearr/paramstatic void SplitArray2(int[] arr){int len arr.Length;int target arr[0];Listint min new Listint(len); //为了方便这里我使用ListListint max new Listint(len); //为了方便这里我使用Listfor (int i 1; i len; i) //从第二个元素开始查找{if (arr[i] target){min.Add(arr[i]);}}//put it in the last of min, that can make sure target greater than min(left)min.Add(target);for (int i 1; i len; i) //从第二个元素开始查找{if (arr[i] target) //我们把等于符号加上就解决问了 对于本例子是从arr[0] 开始的//那如果是从别的位置开始呢{max.Add(arr[i]);}}}/// summary/// start from random index;/// /summary/// param namearr/paramstatic void SplitArray3(int[] arr){int len arr.Length;int randomIndex 2;int target arr[randomIndex]; //假设我们从index2 开始这里我们肯定满足arr.length2;
Listint min new Listint(len); //为了方便这里我使用ListListint max new Listint(len); //为了方便这里我使用Listfor (int i 0; i len; i) //这里我们就要从0 开始了遍历整个数组{if (arr[i] target){min.Add(arr[i]);}}min.Add(target);for (int i 0; i len; i) //这里我们就要从0 开始了遍历整个数组{if (arr[i] target i ! randomIndex) //加上这个条件我们就可以过滤到我们的 randomIndex 避免重复添加的问题 {max.Add(arr[i]);}}//最后我们的数组就是符合我们要求的数组}//上面的做法可以满足 mintargetmax/// summary/// 我们来找出元素所在的位置 index 首先是我们的有序数组中/// 通过值相等来进行判断的话可以满足/// 不管值有序 还是 无序的值/// /summarystatic void FindIndex(int[] arr, int value){int len arr.Length;int index -1;for (int i 0; i len; i){if (arr[i] value){index i;break;}}}/// summary/// 两种思维方式/// 两种思维方式第二种更接近普通人的表达方式/// /summary/// param namearr/param/// param namevalue/paramstatic void FindIndex1(int[] arr, int value){int len arr.Length;int index;bool isExist false;for (int i 0; i len; i){if (arr[i] value){index i;isExist true;break;}}if (isExist false) { index 1; }}/// summary/// 上面的方法是找到value在数组中的第一个index 值 不管它是否有序/// 现在我们要找一个元素在有序列表中的应该插入的值,但是我们不插入/// /summarystatic void FindIndex2(int[] arr, int value){int len arr.Length;int index -1;for (int i 0; i len; i){//你可以这么想//如果找到大于大的数就停止否则就继续if (arr[i] value) //考虑到取等情况{index i; //这个时候我们的数据就可以插入在改元素的的后面index index - 1; //这样就返回了可以直接插入的位置//并且停止我们的循环break; //前提是有序的数组列表中}}//在插入的时候就必须把后面的元素往后面挪动//插入的时候}/// summary/// 上面的方法是找到value在数组中的第一个index 值 不管它是否有序/// 现在我们要找一个元素在有序列表中的应该插入的值,但是我们不插入/// 2 和 3 两种不同的想法写出来的code 就不太一样/// /summarystatic void FindIndex3(int[] arr, int value){int len arr.Length;int index -1;for (int i 0; i len; i){//我们可以可以这么想 if (arr[i] value){index; //小于它的值我们的index 就 keep move forward; 还没考虑我们取等的情况滴呀}else{//遇到不满足的情况我们就退出//原本的我们的index 是落后于我们的i出去的时候再加一次index;break;}}//这样就找到了我们的index在一个可以插入的位置}/// summary/// 先这样来想找出小于 value的count那么value在的位置应该就是在我们的count1;/// /summary/// param namearr/param/// param namevalue/paramstatic void FindCountLessThan(int[] arr, int value){int len arr.Length;int count 0;for (int i 0; i len; i){if (arr[i] value){count;}}//这样我们就能够找出小于count的数量那么 我们value所在的位置就是我们count1}/// summary/// 关键的来了找到value 应该在的位置在一个无序的数组中/// /summary/// param namearr/param/// param namevalue/paramstatic void FindIndexInUnSortArr(int[] arr, int value){int len arr.Length;int rightPosition 0; //初始化默认我们的指针在0位置for (int i 0; i len; i){//通过遍历来查找if (arr[i] value){rightPosition;}}}/// summary/// 找到index在的位置并将小于value的数据放在左边大于value的数据放在右边/// /summary/// param namearr/param/// param namevalue/paramstatic void FindeAndSwap(int[] arr){int len arr.Length;int middleIndex 1;int value arr[0];//target;// i 能找到一个小于value的值//middleIndex 始终指向一个大于或等于 value的值for (int i 1; i len; i){if (arr[i] value) //当找到一个小于value的值之后进行交换和那个值进行交换呢原则小的值移动到左边大的值移动到右边{ //现在我们找到了小的值那么大的值呢if (i middleIndex){//不进行交换 keep move}else{Swap(arr, middleIndex, i);}middleIndex;}}//最后出来后我们要将第一个元素和中间的元素进行交换也就是讲value放在middle的位置Swap(arr, 0, middleIndex - 1);}/// summary/// 上面的代码基本上已经满足了我们额基本要求/// 完美的代码解决了这个问题/// /summary/// param namearr/paramstatic int FindeAndSwap1(int[] arr, int start, int end){int middlePosition start 1;int pivot arr[start];for (int i start 1; i end; i){if (arr[i] pivot){if (i middlePosition){//there is need to swap }else{Swap(arr, middlePosition, i);}middlePosition;}}//put the arr[start] in middle position(greater than left,less than right)int position middlePosition - 1;Swap(arr, arr[start], position);return position;}/// summary/// 同样我们又第二种方式来实现/// /summary/// param namearr/param/// param namelow/param/// param namehigh/paramstatic void FindeAndSwap2(int[] arr, int low,int high){int l low-1; //make sure pointer move firstly (before take value from arr to compare with pviot)int h high1; //make sure pointer move firstly (before take value from arr to compare with pviot)int pviot arr[low]; while (lh){while (arr[--h] pviot) //find some value less than pvoit{}while (arr[l] pviot) //find some value greater than pvoit we use instead of ;beacause we dont let arr[start] swap {}if (l h){Swap(arr, h, l); //swap}} Swap(arr, low, h); //put the povit in the middle Position
}/// summary/// 同样我们也有第三种写法/// /summary/// param namearr/param/// param namelow/param/// param namehigh/paramstatic int FindeAndSwap3(int[] arr, int low, int high){int l low;int h high;int pviot arr[low];while (l h){while (arr[h] pviot) //chose instead of ; beca if the first value arr[h] equal pviot ,this will enter endless loop(dont enter {} do h--;){h--;}while (arr[l] pviot) //we chose instead of to make sure pviot dont take part in swap, we will swap in the last step with middle position{l;}if (l h)break;Swap(arr,l,h);}int middlePosition h;Swap(arr,low, middlePosition);return middlePosition;}/// summary/// 当然就有了我们的第四种方法/// 你会发现前面的方法都是先找到一个小于的index high 然后找到一个大于的index low/// 然后进行交换/// 然后有没有其他的方式呢 /// 答案是有的/// 而且你会发现我们的额pvoit 是没有参与swap的直到我们的最后一步然后将起放在 middle position这一步是不可避免滴呀/// /summary/// param namearr/param/// param namelow/param/// param namehigh/param/// returns/returnsstatic int FindeAndSwap4(int[] arr, int low, int high){int pviot arr[low];while (low high){while(arr[high]pviot low high){high--;}//一旦找到了我们就替换arr[low] arr[high]; //这样会覆盖我们的第一个值不过在最后我们会将第一个值放在“中间”位置while (arr[low] pviot low high){low;} //这样做的话在没有进行到最后一步数组中会有一个重复的值不过我们最后将被我们pviotarr[high] arr[low];}arr[low] pviot;return high;}//到了这一步我们的基本核心的单元算是基本基本完整了//然后我们这里再实现三个版本的快速排序方法/// summary/// 交换/// /summary/// param namearr/param/// param namei/param/// param namej/paramstatic void Swap(int[] arr, int i, int j){int temp arr[i];arr[i] arr[j];arr[j] temp;} 1.然后是快速排序的第一种实现方式从两端申明指针然后开始查找 这个算法是有问题的to do.....做单元测试来一步一步的发现问题 /// summary/// 第一种实现方式从两边开始查找/// 还有一个值得考虑问题就是等于的数据如何处理呢从我们的代码看出等于pviot的数据没有参与到交换中/// 第一次交换之后将流在我们的 两端参与下一次的交换/// /summary/// param namearr/param/// param namelow/param/// param namehigh/param/// returns/returnsstatic int QuickSortUnit(int[] arr, int low, int high){ int pviotarr[low]; //we chose the first value as pivot;while (low high){while (arr[high] pviot lowhigh) // instead of because: if the arr[high] less than pviot,that will result in endless loop(high index never do high--;){high--; //start search from high address}while (arr[low] pviot lowhigh) // instead of becuase:we can make sure arr[first] didt involve the whole swap until the ending{low; //start search from low address}//we both chose equal,after first loop,the equivalent will remianing the origial positon and take part in next sort; that doest affect the final result;if (low high)break;Swap(arr, low, high);}//because we firstly star from high; so the last value that must less than pviot;so high is our middle position;int middlePosition high; //make the code easy to read;Swap(arr,middlePosition,low);return high;}/// summary/// recurion to resolve the same problem;/// /summary/// param namearr/param/// param namelow/param/// param namehigh/paramstatic void QuickSort(int [] arr,int low,int high){if (low high) //make sure recusion can stopreturn;int middlePositonQuickSortUnit(arr,low,high);//star from left;QuickSort(arr,low, middlePositon-1);//star from rightQuickSort(arr, middlePositon1,high);} 2.然后是快速排序的第二种实现方式本质上和第一种方式一样的只不过写法想法略有不同一旦找到元素就开始覆盖指定位置的值这样每次都会有一个重复的值不过这个重复的值最后会被我们的pivot给占据 /// summary/// /// /summary/// param namearr/param/// param namelow/param/// param namehigh/paramstatic int QuickSortUnit(int[] arr, int low, int high){int pviot arr[low];while (low high){while (arr[high] pviot lowhigh){high--;}arr[low] arr[high]; //once find the value less than pviot ,put it in low address;while (arr[low] pviot low high){low;}arr[high] arr[low]; //once find the value greater than pviot, put it in high address;}int middlePositon high;arr[low] pviot; return middlePositon;}/// summary/// use recursion to resovle the same problem;/// /summary/// param namearr/param/// param namelow/param/// param namehigh/paramstatic void QuickSort(int [] arr,int low,int high){if (low high)return;int middlePosition QuickSortUnit(arr,low,high);QuickSortUnit(arr, low, middlePosition-1);QuickSortUnit(arr, middlePosition1, high);} 思考 最后一步交互为哈一定要取low呢debug 一下这个 var arr new[] { 7, 8, 7 }; 第三种方式其实本质是一样不过这种方式不用从两端申明pointer去查找伴随着两个while循环这里我们用一个循环还是两个pointer不过他们的出发位置就有所不同了都从左边开始 提现了不同的思路去解决问题 最后一种我们就直接给链接吧 https://www.hackerearth.com/zh/practice/algorithms/sorting/quick-sort/tutorial/ 非常好的网站 这里我们再来总结一下整个执行过程 1设置两个变量i、j排序开始的时候i0jN-1 2以第一个数组元素作为关键数据赋值给key即keyA[0] 3从j开始向前搜索即由后开始向前搜索(j--)找到第一个小于key的值A[j]将A[j]和A[i]互换 4从i开始向后搜索即由前开始向后搜索(i)找到第一个大于key的A[i]将A[i]和A[j]互换 5重复第3、4步直到ij (3,4步中没找到符合条件的值即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值使得jj-1ii1直至找到为止。找到符合条件的值进行交换的时候i j指针位置不变。另外ij这一过程一定正好是i或j- 最后就是要通过写单元测试来assert我们的值 转载于:https://www.cnblogs.com/mc67/p/8259734.html
