//待排序數(shù)組
? ? ? ? ? var sortArray = [10,1,100,10,200,34,25,46,299,100,400,40];
? ? ? ? ? //為待排序數(shù)組增加一個(gè)“監(jiān)聽哨”(就是一個(gè)存放當(dāng)前要排序數(shù)據(jù)的位置)
? ? ? ? ? sortArray.insert(0, 0);
? ? ? ? ? //打印待排序數(shù)組
? ? ? ? ? print(sortArray);
? ? ? ? ? //折半插入排序
? ? ? ? ? var mid;//折半排序的中間點(diǎn)位置
? ? ? ? ? var low;//折半排序的低位置
? ? ? ? ? var high;//折半排序的高位置
? ? ? ? ? //現(xiàn)在的數(shù)組i=0是存取臨時(shí)保存的數(shù)據(jù)，i=1開始才是需要排序的數(shù)據(jù)
? ? ? ? ? //從第二個(gè)數(shù)開始取數(shù)據(jù)，因?yàn)榈谝粋€(gè)數(shù)據(jù)就相當(dāng)于排好序數(shù)據(jù)的第一個(gè)數(shù),所以不用取
? ? ? ? ? for (var i = 2; i < sortArray.length; i++) {
? ? ? ? ? ? /*取出當(dāng)前需要插入的數(shù)據(jù),
? ? ? ? ? ? i位前邊的數(shù)據(jù)是已經(jīng)排好序的熟丸，
? ? ? ? ? ? 后邊的數(shù)據(jù)是沒有排序的數(shù)據(jù)*/
? ? ? ? ? ? sortArray[0] = sortArray[i];
? ? ? ? ? ? low = 1;//設(shè)置折半排序的低位诈闺，因?yàn)閺牡谝粋€(gè)數(shù)據(jù)開始狸窘，所以為1
? ? ? ? ? ? high = i-1;//設(shè)置折半排序的高位茬底，是當(dāng)前要排序數(shù)據(jù)的前一位克婶，所以是i-1
? ? ? ? ? ? while (low <= high) {//設(shè)置條件，低位<=高位滿足折半查找的條件
? ? ? ? ? ? ? mid = (low+high) ~/ 2;
? ? ? ? ? ? ? if (sortArray[i] >= sortArray[mid]) {
? ? ? ? ? ? ? ? //說明當(dāng)前需要插入的數(shù)據(jù)比有序列表中取出的數(shù)據(jù)大或者相等
? ? ? ? ? ? ? ? low = (mid + 1);//需要在有序數(shù)組的右邊去數(shù)據(jù)扛芽，所以要把低位移到mid+1的位置
? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? high = (mid - 1);//需要在有序數(shù)組的左邊取數(shù)據(jù)，所以要把高位移到mid-1的位置
? ? ? ? ? ? ? }
? ? ? ? ? ? }/*比較完以后high+1的位置是要插入的位置,
? ? ? ? ? ? 所以從high+1位開始积瞒，到i位之前的數(shù)據(jù)都要向前移動(dòng)一位
? ? ? ? ? ? （high+1位的數(shù)據(jù)移動(dòng)到high+2位...i-1位的數(shù)據(jù)移動(dòng)到位）*/
? ? ? ? ? ? for (var j = i; j >= high+1; --j) {
? ? ? ? ? ? ? sortArray[j] = sortArray[j-1];
? ? ? ? ? ? }
? ? ? ? ? ? //最后把要插入的數(shù)據(jù)(就是之前從0位取出的數(shù)據(jù)sortArray[0])放到high+1的位置
? ? ? ? ? ? sortArray[high+1] = sortArray[0];
? ? ? ? ? }
? ? ? ? ? //刪除“監(jiān)聽哨”
? ? ? ? ? sortArray.removeAt(0);
? ? ? ? ? print("排完序的數(shù)組${sortArray}");
