折半插入排序算法实现-加岗哨

//待排序数组

          var sortArray = [10,1,100,10,200,34,25,46,299,100,400,40];

          //为待排序数组增加一个“监听哨”(就是一个存放当前要排序数据的位置)

          sortArray.insert(0, 0);

          //打印待排序数组

          print(sortArray);

          //折半插入排序

          var mid;//折半排序的中间点位置

          var low;//折半排序的低位置

          var high;//折半排序的高位置

          //现在的数组i=0是存取临时保存的数据，i=1开始才是需要排序的数据

          //从第二个数开始取数据，因为第一个数据就相当于排好序数据的第一个数,所以不用取

          for (var i = 2; i < sortArray.length; i++) {

            /*取出当前需要插入的数据,

            i位前边的数据是已经排好序的，

            后边的数据是没有排序的数据*/

            sortArray[0] = sortArray[i];

            low = 1;//设置折半排序的低位，因为从第一个数据开始，所以为1

            high = i-1;//设置折半排序的高位，是当前要排序数据的前一位，所以是i-1

            while (low <= high) {//设置条件，低位<=高位满足折半查找的条件

              mid = (low+high) ~/ 2;

              if (sortArray[i] >= sortArray[mid]) {

                //说明当前需要插入的数据比有序列表中取出的数据大或者相等

                low = (mid + 1);//需要在有序数组的右边去数据，所以要把低位移到mid+1的位置

              } else {

                high = (mid - 1);//需要在有序数组的左边取数据，所以要把高位移到mid-1的位置

              }

            }/*比较完以后high+1的位置是要插入的位置,

            所以从high+1位开始，到i位之前的数据都要向前移动一位

            （high+1位的数据移动到high+2位...i-1位的数据移动到位）*/

            for (var j = i; j >= high+1; --j) {

              sortArray[j] = sortArray[j-1];

            }

            //最后把要插入的数据(就是之前从0位取出的数据sortArray[0])放到high+1的位置

            sortArray[high+1] = sortArray[0];

          }

          //删除“监听哨”

          sortArray.removeAt(0);

          print("排完序的数组${sortArray}");