2回答

xiaobai00000

提问者

2020-09-26

用kotlin写的， 老师 看下  思路有没有问题。 主要是想解决 在选择排序中，数组插入元素时，之后的元素 都得右移的问题。

fun sortInsert(data1: Array<Int>): Array<Int> {     //采用降序排列

   var data = Array<Int>(data1.size) { data1[it] }

   var time = System.currentTimeMillis()

   if (data.isEmpty()) {
       e("--empty array---")
       return data
   }


   var baseValue = data[0]     //设置原点，每个要插入的数据 均和比较来 判断 是插入到它左边 还是 右边

   var baseIndex = 0

   var resultArray = ArrayList<Int>()

   resultArray.add(baseValue)      //先将第一个元素 加入空集合中

   var tempValue = 0

   for (i in 1 until data.size) {  //从第二个元素开始，一个个的参与 比较 最后 添加到集合中

       tempValue = data[i]     //将要插入的第i个元素

       if (tempValue >= baseValue) {       //比原点大，所以 插入到左边 （因为是降序）

           if (baseIndex == 0) {           //如果原点已经是头部了， 直接加到集合的 0 位置
               resultArray.add(0, tempValue)
               baseIndex++
               continue
           }

           for (j in (baseIndex - 1) downTo 0) {

               if (tempValue < resultArray[j]) {
                   resultArray.add(j + 1, tempValue)
                   baseIndex++
                   break
               }

               if (j == 0) {
                   resultArray.add(0, tempValue)
                   baseIndex++
               }
           }

       } else {

           if (baseIndex == resultArray.size - 1) {
               resultArray.add(tempValue)
               continue
           }


           for (j in (baseIndex + 1) until resultArray.size) {

               if (tempValue > resultArray[j]) {
                   resultArray.add(j, tempValue)
                   break
               }

               if (j == resultArray.size - 1) {
                   resultArray.add(tempValue)
               }
           }
       }
   }

   e("--insert-sort-duration ${System.currentTimeMillis() - time}")
   return resultArray.toTypedArray()
}

0

hiaobai00000

回复

hiuyubobobo

嗯，的确不是 原地排序，需要创建一个集合。 用相同的 10w个随机数 排序测试如下： --select-sort-3-duration 17132 --insert-sort-duration 8004 （使用我提到的 创建一个集合插入） --insert-sort-2-duration 15793 （使用插入排序的， swap） --insert-sort-3-duration 4521 （使用插入排序的 赋值） --system sort---duration:50 （使用系统的 Arrays.sort()） *******start to verify******** ****** both right, checking duration: 17 性能优于swap,但是 比不上 老师提到的 赋值 的方式.

h020-09-27

共2条回复

liuyubobobo

2020-09-26

其实我没有特别理解你的意思。把你的方法用代码表示出来，实际测试一下性能？

加油！：）

0