算法结果图

简介

归并排序是一种稳定的分治排序算法，通过将数组分成两半，分别排序后再合并。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现归并排序，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

归并排序的核心思想：

• 将数组分成两个相等的部分
• 递归地对两部分进行排序
• 合并两个已排序的部分
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

第一步：Kotlin 中实现归并排序

在 shared/src/commonMain/kotlin/Batch1_SortingAndSearching.kt 中实现归并排序：

fun mergeSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1): IntArray {
    if (left < right) {
        val mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
    }
    return arr
}

fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    val leftArr = arr.slice(left..mid).toIntArray()
    val rightArr = arr.slice(mid + 1..right).toIntArray()
    
    var i = 0
    var j = 0
    var k = left
    
    while (i < leftArr.size && j < rightArr.size) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++]
        } else {
            arr[k++] = rightArr[j++]
        }
    }
    
    while (i < leftArr.size) {
        arr[k++] = leftArr[i++]
    }
    
    while (j < rightArr.size) {
        arr[k++] = rightArr[j++]
    }
}

代码说明：

• mergeSort() 是递归函数，处理分治逻辑
• merge() 函数合并两个已排序的子数组
• 使用 slice() 创建子数组
• 通过双指针合并两个有序数组

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch1() {
    val testArray = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("原始数组: ${testArray.joinToString(", ")}")
    
    val sorted = mergeSort(testArray.copyOf())
    println("排序后: ${sorted.joinToString(", ")}")
}

导出说明：

• @JsExport 注解使函数可以从 JavaScript 中调用
• 使用 copyOf() 避免修改原始数组
• println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

编译完成后，会生成 build/js/packages/kjsdemo/kotlin/kjsdemo.js 文件。

编译过程说明：

• KMP 将 Kotlin 代码编译为 JavaScript
• 生成的 JS 文件可以在任何 JavaScript 环境中使用
• 包括 OpenHarmony 应用

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 3, 
    name: '归并排序', 
    nameEn: 'Merge Sort', 
    category: '排序', 
    description: '分治法排序，O(n log n)' 
  },
  // ... 其他算法
];

列表说明：

• 每个算法都有唯一的 ID
• 包含中文名称、英文名称、分类和描述
• 点击列表项会导航到详情页面

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

executeAlgorithm() {
  let output = '';
  
  switch (this.algorithmId) {
    case 3:
      output = `归并排序结果:\n[64, 34, 25, 12, 22, 11, 90]\n↓\n11,12,22,25,34,64,90`;
      break;
    // ... 其他算法
  }
  
  // 输出到控制台
  console.log(`========== ${this.algorithmName} (${this.algorithmNameEn}) ==========`);
  console.log(`分类: ${this.algorithmCategory}`);
  console.log(`描述: ${this.algorithmDesc}`);
  console.log(`结果:\n${output}`);
  console.log('='.repeat(50));
  
  // 延迟后返回
  setTimeout(() => {
    router.back();
  }, 500);
}

执行说明：

• 根据算法 ID 执行对应的算法
• 使用 console.log() 输出结果到控制台
• 自动返回到算法列表

完整工作流程

Kotlin 代码 (mergeSort)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

测试步骤

1. 编译项目

   cd D:\flutter_Obj\kjsdemo-master
   ./gradlew jsJar
   

2. 构建 OpenHarmony 应用

   cd kmp_ceshiapp
   hvigor build
   

3. 运行应用

   • 在 OpenHarmony 模拟器或真机上运行应用
   • 点击"归并排序"算法
   • 在控制台查看输出结果

预期输出

========== 归并排序 (Merge Sort) ==========
分类: 排序
描述: 分治法排序，O(n log n)
结果:
归并排序结果:
[64, 34, 25, 12, 22, 11, 90]
↓
11,12,22,25,34,64,90
==================================================

性能分析

指标	值
时间复杂度	O(n log n)
空间复杂度	O(n)
稳定性	稳定
最佳情况	O(n log n)
最坏情况	O(n log n)

优化建议

1. 原地归并：使用原地归并算法可以减少空间复杂度
2. 混合排序：对小数组使用插入排序，对大数组使用归并排序
3. 自底向上：使用迭代方式替代递归，可以避免栈溢出

总结

通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中编写稳定的分治算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

归并排序是最稳定的排序算法，适合需要保持相等元素相对顺序的场景。

---

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net