公共模塊
export enum Compare {
LESS = -1,
EQUAL = 0,
GREATER = 1
}
// 比較大小的方法
export function defaultCompareFunction<T>(a: T, b: T){
if(a === b){
return Compare.EQUAL
}
return a > b ? Compare.GREATER : Compare.LESS;
}
// 陣列元素交換的方法
export function swap<T>(arr:Array<T>, beginIndex:number , endIndex:number){
[arr[beginIndex], arr[endIndex]] = [arr[endIndex], arr[beginIndex]]
}
冒泡排序
比較所有相鄰的兩個項,如果第一個比第二個大,則交換它們.元素向上移動到正確的位置,就好像氣泡升至表面一樣,冒泡排序因此得名
let arr = [9,5,4,5,4,8,4,2,45,1,5,41];
import {defaultCompareFunction, Compare ,swap} from "./common"
export function sortArray<T>(arr: Array<T>, compareFn: Function = defaultCompareFunction){
let len = arr.length;
for (let i = 0; i < len; i++) {
// 冒上去的元素都不需要在做比較,所以這里的
for (let j = 0; j < len - 1 - i; j++) {
// 前一個元素
const before = arr[j];
// 后一個元素
const after = arr[j + 1];
// 如果前一個元素比后一個元素的大，交換位置
if(compareFn(before, after) === Compare.GREATER){
swap(arr, j , j + 1);
}
}
}
}
sortArray(arr)
console.log(arr);
性能差: 需要雙回圈
- 外回圈保證回圈次數足夠
- 內回圈調換相鄰元素的位置
注意點:
- 已經冒到水面的元素(已排好的元素),不需要在做比較 [每次必定會有一個最大值到最后]
- 是前一個元素和后一個元素的比較大小,所以外層回圈只是為了保證回圈次數
插入排序
將當前陣列的劃分成兩部份,前部分為已排序部分 , 后部分為未排序部分,然后將后部分資料一個一個的向前部分插入
let arr = [9,5,4,5,4,8,4,2,45,1,5,41];
import {defaultCompareFunction, Compare ,swap} from "./common"
function sortArray<T>(arr:Array<T>, compareFn:Function = defaultCompareFunction){
for (let i = 0; i < arr.length; i++) {
let current = i;
// 注意回圈從i開始，0結束，注意要從后面開始交換，這樣子才能做到一步一步的向前挪
// 如果從0開始，向后的話 會把當前資料移動回來
for (let j = i; j >= 0; j--) {
const external = arr[current];
const within = arr[j];
// 比較外層的值是否小于當前值
if(compareFn(external, within) === Compare.LESS){
// 交換位置
swap(arr, current, j);
// 并更新當前min指標
current = j;
}
}
}
}
sortArray(arr)
console.log(arr)
第一個元素默認有序
后面的元素需要從有序部分的尾部插入
注意交換位置后要追蹤當前元素
選擇排序
找到資料中最小值并將其放置在第一位,接這找第二小的值,放在第二位 ....
let arr = [9,5,4,5,4,8,4,2,45,1,5,41];
import {defaultCompareFunction, Compare ,swap} from"./common"
function sortArray<T>(arr:Array<T>, compareFn:Function = defaultCompareFunction){
for (let i = 0; i < arr.length; i++) {
// 記錄當前為最小下標
let min = i;
for (let j = i + 1; j < arr.length; j++) {
const external = arr[min];
const within = arr[j];
// 比較最小的與當前大小 ，如果最小的值比
if(compareFn(external, within) === Compare.GREATER){
// 將最小值轉為當前下標
min = j;
}
}
// 如果最小下標不等于當前下標 ，就交換位置
if(min !== i)swap(arr, min, i);
}
}
sortArray(arr);
console.log(arr)
定義最小的位置,然后記錄下其下標
外層回圈代表著順序(第幾小的數)
找到最小下標后,與外層的下標交換(不相同的情況,相同交換沒有意義)
歸并排序
歸并使用的是分而治之的思想,將一個大陣列分成n個小陣列,當分成一個元素的時候就相當于默認有序,然后將有序的陣列進行合并排序,最后達到排序的效果
import {defaultCompareFunction, Compare } from "./Common"
// 拆分
export function sortArray<T>(arr: Array<T>, compareFn: Function = defaultCompareFunction) {
const len:number = arr.length;
if(len > 1){
// 算出中位數
let middle = Math.floor(len / 2);
// 拆分左邊 注意slice分割陣列是不會改變陣列本身的
let left = sortArray(arr.slice(0, middle), compareFn)
// 拆分右邊
let right = sortArray(arr.slice(middle, len), compareFn)
// 將左右倆個陣列歸并, 并排序, 然后回傳回去
arr = mergeSort(left , right , compareFn);
}
return arr;
}
// 歸并
function mergeSort<T>(leftArr: Array<T>,rightArr: Array<T>, compareFn: Function = defaultCompareFunction):Array<T> {
let result = [];
// 左邊陣列指標
let left = 0;
// 右邊陣列指標
let right = 0;
// 不管左右陣列那邊越界都結束回圈
while(left < leftArr.length && right < rightArr.length){
// 如果左邊小(大)就將左邊丟入陣列中,并左陣列指標+1, 反之亦然
// 這里注意一定要指標變化
result.push(compareFn(leftArr[left], rightArr[right]) === Compare.LESS ? leftArr[left++] : rightArr[right++])
// if(compareFn(leftArr[left], rightArr[right]) === Compare.LESS){
// result.push(leftArr[left]);
// left++;
// }else{
// result.push(rightArr[right]);
// right++;
// }
}
return result.concat(left < leftArr.length ? leftArr.slice(left) : rightArr.slice(right));
}
先切割陣列
后合并并排序這個兩個陣列
注意的是這個里面涉及到一個有序的陣列的排序
排序使用雙指標,然后如果左指標的值(對應做邊陣列)小于右指標的值(對應右邊陣列),那么就添加左邊陣列的值到新陣列中,并且左指標+1,但是右指標不動,直到最后那邊指標出界,但是兩個都是有序的陣列,所以直接拼接上去即可
快速排序
快速排序也是使用了分而治之的思想,但是并不會真的切分(指標上的區分)
import {defaultCompareFunction, Compare ,swap} from "./Common"
export function sortArray<T>(arr: Array<T>, compareFn: Function = defaultCompareFunction){
quickSort(arr, 0, arr.length - 1, compareFn)
}
function quickSort<T>(arr: Array<T>, left:number, right:number, compareFn: Function) {
// 最小陣列和最大陣列的中界線
let index:number;
// 當前陣列長度大于1個
if(arr.length > 1){
// 獲取劃分的界限 左邊為最小值 右邊為最大值
index = partition(arr, left ,right, compareFn);
if(left < index - 1){
// 快排左部分
quickSort(arr, left, index - 1, compareFn);
}
if(index < right){
// 快排右部分
quickSort(arr, index, right, compareFn)
}
}
//當前陣列長度等于1 一個元素是有序的 直接回傳
return arr;
}
// 劃分
function partition<T>(arr:Array<T>, left:number, right:number, compareFn:Function):number {
// 選擇主元的位置 :這里選取陣列中的中間值
const pivotIndex = Math.floor((left + right) / 2)
//取主元 具體值
const pivot = arr[pivotIndex];
// 當左右兩邊交叉的時候結束
while(left <= right){
// 左邊值大于(等于)主元的時候結束回圈 = 得到左邊大于主元的值
while (compareFn(arr[left] , pivot) === Compare.LESS){
left++;
}
// 右邊值中有值小于(等于)主元的時候結束回圈 = 得到右邊小于主元的值
while (compareFn(arr[right] , pivot) === Compare.GREATER){
right--;
}
// 當left小于right 就交換
if(left <= right){
// 將元素進行交換
swap(arr, left , right);
// 左指標 +1 縮小范圍
left++;
// 右指標 -1 縮小范圍
right--;
}
}
return left;
}
let arr = [1,2,54,8,45,7, 45,9,8,452,35,754,127,6,21,124,454]
sortArray(arr)
// @ts-ignore
console.log(arr)
從陣列中選擇一個值作為主元,也就是陣列中間的那個值
創建兩個指標,左邊指向陣列的第一個值,右邊指向陣列的最后一個值.移動左邊的指標直到找到比主元小的值,然后移動右邊的指標,找到比主元小的值,然后交換位置,重復該程序,直到左指標超過了右指標.這個程序將使比主元小的值集中在主元的左邊,比主元大的值集中在主元的右邊.這一步叫做劃分
演算法對劃分后的小陣列,繼續上面的步驟,直到陣列完全有序
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/230960.html
標籤：其他
上一篇：JS 異步編程與Promise，還有async與await實體
下一篇：博客中css樣式的正確設定