常见排序算法实现（TS版）个人文章

//sorting/bubble-sort/BubbleSort.tsimport{TypeCompareParam}from'../../utils/comparator/Comparator'importSort,{ICallbacks}from'../../utils/sort/Sort'import{swap}from'../../utils/swap/swap'exportdefaultclassBubbleSortextendsSort{constructor(originalCallbacks:ICallbacks){super(originalCallbacks)}sort(originalArray:TypeCompareParam[]){//Flagthatholdsinfoaboutwhethertheswaphasoccurornot.letswapped=false//Cloneoriginalarraytopreventitsmodification.constarray=[...originalArray]for(leti=1;i

动画演示：

//sorting/selection-sort/SelectionSort.tsimport{TypeCompareParam}from'../../utils/comparator/Comparator'importSort,{ICallbacks}from'../../utils/sort/Sort'import{swap}from'../../utils/swap/swap'exportdefaultclassSelectionSortextendsSort{constructor(originalCallbacks:ICallbacks){super(originalCallbacks)}sort(originalArray:TypeCompareParam[]){//Cloneoriginalarraytopreventitsmodification.constarray=[...originalArray]for(leti=0;i

比较的总数是：

通过等差数列求和得到：

稳定性分析：

选择排序是不稳定的。

算法的稳定性定义为，对于待排序列中相同项的原来次序不能被算法改变则称该算法稳定。比如待排序列为:(2)36[2]45...序列中的(2)排在[2]前面，不能因为算法把[2]排到(2)前面。

选择排序算法，举个简单的例子，就知道它是否稳定。例如:(7)25934[7]1...当我们利用选择排序算法进行升序排序时候，(7)和1调换，(7)就跑到了[7]的后面了，原来的次序改变了，这样就不稳定了。

复杂度：

//sorting/insertion-sort/InsertionSort.tsimport{TypeCompareParam}from'../../utils/comparator/Comparator'importSort,{ICallbacks}from'../../utils/sort/Sort'import{swap}from'../../utils/swap/swap'exportdefaultclassInsertionSortextendsSort{constructor(originalCallbacks:ICallbacks){super(originalCallbacks)}sort(originalArray:TypeCompareParam[]){constarray=[...originalArray]//Gothroughallarrayelements...for(leti=1;i

//sorting/heap-sort/HeapSort.tsimportMinHeapfrom'../../data-structures/heap/MinHeap'import{TypeCompareParam}from'../../utils/comparator/Comparator'importSort,{ICallbacks}from'../../utils/sort/Sort'exportdefaultclassHeapSortextendsSort{constructor(originalCallbacks:ICallbacks){super(originalCallbacks)}sort(originalArray:TypeCompareParam[]){constsortedArray=[]constminHeap=newMinHeap(this.callbacks.compareCallback)//Insertallarrayelementstotheheap.originalArray.forEach((element)=>{//Callvisitingcallback.this.callbacks.visitingCallback(element)minHeap.add(element)})//Nowwehaveminheapwithminimalelementalwaysontop.//Let'spollthatminimalelementonebyoneandthusformthesortedarray.while(!minHeap.isEmpty()){constnextMinElement=minHeap.poll()//Callvisitingcallback.this.callbacks.visitingCallback(nextMinElement)sortedArray.push(nextMinElement)}returnsortedArray}}复杂度分析：

步骤是：

这里展示两种实现方式。

工作原理：

Forourexampleandeaseofunderstanding,wetaketheintervalof4.Makeavirtualsub-listofallvalueslocatedattheintervalof4positions.Herethesevaluesare{35,14},{33,19},{42,27}and{10,44}:

Wecomparevaluesineachsub-listandswapthem(ifnecessary)intheoriginalarray.Afterthisstep,thenewarrayshouldlooklikethis:

Then,wetakeintervalof2andthisgapgeneratestwosub-lists{14,27,35,42},{19,10,33,44}:

Wecompareandswapthevalues(usesinsertionsort),ifrequired,intheoriginalarray.Afterthisstep,thearrayshouldlooklikethis:

Finally,wesorttherestofthearrayusingintervalofvalue1.Shellsortusesinsertionsorttosortthearray.