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

//待排序数组

          var sortArray = [1000,500,200,100,50,40,30,20];

          //打印待排序数组

          print(sortArray);

          //折半插入排序

          var replaceObject;//定义一个变量，存放当前要排序的数据

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

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

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

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

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

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

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

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

            replaceObject = sortArray[i];

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

            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) {

              if (j-1 < 0) {

                //不加岗哨会有这个问题

                /*处理数组越界问题,因为i=1时，如果sortArray[0] > sortArray[i]的话，

                high会等于-1,所以要判断一下这个*/

                break;

              }

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

            }

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

            sortArray[high+1] = replaceObject;

          }

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