idioms/idiom/assets/core/util/ArrayUtil.ts

export default class ArrayUtil {
    /**随机打乱一个数组 */
    public static  shuffleArray<T>(array: T[]): T[] {
        let currentIndex = array.length;
        let temporaryValue;
        let randomIndex;
      
        // While there remain elements to shuffle...
        while (currentIndex !== 0) {
          // Pick a remaining element...
          randomIndex = Math.floor(Math.random() * currentIndex);
          currentIndex--;
      
          // And swap it with the current element.
          temporaryValue = array[currentIndex];
          array[currentIndex] = array[randomIndex];
          array[randomIndex] = temporaryValue;
        }
        return array;
    }
    // Fisher-Yates 洗牌算法
    //const originalArray = [1, 2, 3, 4, 5];  
    //const shuffledArray = shuffleArray([...originalArray]);
    public static shuffleArray2<T>(array: T[]): T[] {  
        for (let i = array.length - 1; i > 0; i--) {  
            // 生成一个随机索引  
            const j = Math.floor(Math.random() * (i + 1));  
            // 交换元素  
            [array[i], array[j]] = [array[j], array[i]];  
        }  
        return array;  
    }  
    /**合并两个数组元素，移除相同的 */
    public static MergeAndRemoveDuplicates<T>(arr1: T[], arr2: T[]): T[] {
        const merged = [...arr1, ...arr2]; // 合并两个数组
        const uniqueValues = Array.from(new Set(merged)); // 去重
        return uniqueValues;
    }
    /**排除数组1在数组2里有的元素，返回新数组*/
    public static ExcludeElements<T>(array1:T[],array2:T[]):T[]{
        const set = new Set(array2); // 将 array2 转换为 Set
        return array1.filter(item => !set.has(item));
    }
    /**检测数组元素是否能满足顺序的组合*/
    public static checkSequentialCombination(arr: number[]): number[] {
        const sortedArr = arr.slice().sort((a, b) => a - b);
        for (let i = 0; i < sortedArr.length - 1; i++) {
            if (sortedArr[i] + 1 !== sortedArr[i + 1]) {
                return [];
            }
        }
        return sortedArr;
    }
    /**从一个数组中找出是否有连续的组合*/
    public static findSequentialCombinations(arr: number[]): number[][] {
        const result: number[][] = [];
        arr.sort((a, b) => a - b);
        let currentSequence: number[] = [];
        for (let i = 0; i < arr.length; i++) {
            if (currentSequence.length === 0 || arr[i] === currentSequence[currentSequence.length - 1] + 1) {
                currentSequence.push(arr[i]);
            } else {
                if (currentSequence.length > 1) {
                    result.push(currentSequence);
                }
                currentSequence = [arr[i]];
            }
        }
        if (currentSequence.length > 1) {
            result.push(currentSequence);
        }
        return result;
    }
    /*eg:const arr = [2, 4,2, 5, 3, 6, 9,9,10,11,];
    const combinations = this.findSequentialCombinations(arr);
    
    if (combinations.length > 0) {
        console.log("所有可能的连续顺序组合为:");
        combinations.forEach(combination => {
            console.log(combination);
        });
    } else {
        console.log("无法找到连续顺序组合");
    }*/

    /**数组中删除一个合条件的*/
    public static DeleteOneItem<T>(list:Array<T>,check:(item:T)=>boolean):T|null{
        let length=list.length;
        for(let i:number=0;i<length;i++){
            if(check(list[i])){
                return list.splice(i,1)[0];
                //i--;
                //length--;
            }
        }
        return null;
    }

    /**插入排序(适用于差异不会很大，相对有序的数据)Array.sort() 快速排序 算法更适用于混乱无章的数据 */
    public static InsertionSort(array:any[]):void{
            const count = array.length;
            if(count<=1)return;
            let t1:any;
            let t2:any;
            for(let i=1;i<count;i++){
                t1 = array[i];
                let j:number;
                for(j=i;j>0 && t1.sortValue>(t2=array[j-1]).sortValue;j--){
                    array[j]=t2;
                }
                array[j]=t1;
            }
    }
    // 元素排序
    /*示例
     负数在前
    const checkMinusNumber = function (val: number) {
            return val > 0;
    };
    const arr = [2, 4, 5, 6, 7, -8, -10 - 12, -2];
    adjustArrayOrder.reorder(arr, checkMinusNumber);
    console.log(arr);
    */
    public static reorder(arr: Array<number>, checkFun: (checkVal: number) => boolean): void {
         let end = arr.length - 1;
         let begin =0;
         while (begin < end) {
               // 向后移动begin
               while (begin < end && !checkFun(arr[begin])) {
                     begin++;
               }
               // 向前移动end
               while (begin < end && checkFun(arr[end])) {
                   end--;
               }
               // begin与end都指向了正确的位置
               if (begin < end) {
                    // 交换两个元素的顺序
                    [arr[begin], arr[end]] = [arr[end], arr[begin]];
               }
          }
    }
    //冒泡排序
    /// <summary>
	/// 各种类型冒泡排序比
	 /// </summary>/// 例子:
                      /// CommonSort<int>(new int[]{2,3,1,45,123,4},compare)
                      /// bool compare(int a,int b){
                      ///    	 if(a>b)return true;
                      ///   	 reutn false;
                      /// }
	/// <param name="sortArray"></param>
	/// <param name="compareMethod"></param>
	/// <typeparam name="T"></typeparam>
	static  CommonSort<T>(sortArray:Array<T>, compareMethod:(a:T,b:T)=>boolean):void
	{
		let swapped = true;
		do
		{
			swapped = false;
			for (let i = 0; i < sortArray.length - 1; i++)
			{
				if (compareMethod(sortArray[i], sortArray[i + 1]))
				{
					let temp = sortArray[i];
					sortArray[i] = sortArray[i + 1];
					sortArray[i + 1] = temp;
					swapped = true;
				}
			}
		} while (swapped);
    }
    /**归并排序 */
    /*var arr: number[] = [];
	for (var i: number = 0; i < 1000; i++) {
	    arr.push(Math.floor(1000 - i));//生成降序的数组
	}
	MergeSort(arr, 0, arr.length);//调用归并排序算法*/
    //拆分数组  分
    static MergeSort(arr: number[], lo: number, hi: number): void {
        if (hi - lo < 2) return;//单个元素无需考虑
        var mi: number = (lo + hi) >> 1;//已中点为界 或者改成Math.floor((lo + hi) / 2)
        this.MergeSort(arr, lo, mi);//对左边排序
        this.MergeSort(arr, mi, hi);//对右边排序
        this.merge(arr, lo, mi, hi);//归并
    }
    //归并算法实现 合
    private static  merge(arr: number[], lo: number, mi: number, hi: number): void {
        var A: number[] = arr.slice(lo, hi);//A[lo, hi)=arr[lo, hi)
        var lb: number = mi - lo;
        var B: number[] = new Array(lb);
        for (var i = 0; i < lb; B[i] = A[i++]);//复制左子向量B[0, lb) = arr[lo, mi)
        var lc: number = hi - mi;
        var C: number[] = arr.slice(mi, hi);//后子向量C[0,lc) = arr[mi, hi)
        for (var i = 0, j = 0, k = 0; j < lb;) {//反复冲B和C中取出更小者
            if (k < lc && C[k] < B[j]) {//将其归入A中
                A[i++] = C[k++];
            }
            if (lc <= k || B[j] <= C[k]) {
                A[i++] = B[j++];
            }
        }
        for (var i = 0; i < A.length; arr[lo + i] = A[i++]);//把A中的值赋给原来的数组
        B.length = 0;
        C.length = 0;
        A.length = 0;
    }
}