//待排序数组
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}");
