這回要實作的部份是效能較為不佳、但也是最直觀好懂的幾個排序方法。分別為 Bubble, selection 和 insertion。
指令
|
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 75 76 77 78 79 |
/*基礎排序方法*/ function ArrayList(){ let array = [] let swap = (index1,index2) =>{ let aux = array[index1] array[index1] = array[index2] array[index2] = aux } this.insert = item =>{ array.push(item) } this.toString = () =>{ return array.join() } // bubbleSort(original) n^2 this.bubbleSort = () =>{ let arrayLength = array.length for( let i=0; i<arrayLength;i++){ for( let j=0; j<arrayLength-1;j++){ if(array[j]>array[j+1]){ swap(j,j+1) } } } } // bubbleSort(modified) n^2 this.modifiedBubbleSort = () =>{ let arrayLength = array.length for( let i=0; i<arrayLength;i++){ for( let j=0; j<arrayLength-1-i;j++){ if(array[j]>array[j+1]){ swap(j,j+1) } } } } // selectionSort n^2 this.selectionSort = () =>{ let arrayLength = array.length for(let i=0; i<arrayLength-1;i++){ let indexMin = i for(let j=i; j<arrayLength;j++){ if(array[indexMin]>array[j]){ indexMin = j } } if(i !== indexMin){ swap(i,indexMin) } } } // insertionSort n^2 this.insertionSort = () =>{ let arrayLength = array.length for(let i=1;i<arrayLength;i++){ let j = i let temp = array[i] while(j>0 && array[j-1] > temp){ array[j] = array [j-1] j-- } array[j] = temp } } } // tested Array function createNonSortedArray(size){ let array = new ArrayList() for (let i=size; i>0; i--){ array.insert(i) } return array } |
