合肥建行网站/网络营销教学网站

题目描述

给出一个数据序列，使用折半插入排序算法进行降序排序。

输入

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推 输出 对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

样例输入

2
5
111 22 6 444 333
8
30 13 70 85 39 42 6 20

样例输出

111 22 6 444 333
111 22 6 444 333
444 111 22 6 333
444 333 111 22 6

30 13 70 85 39 42 6 20
70 30 13 85 39 42 6 20
85 70 30 13 39 42 6 20
85 70 39 30 13 42 6 20
85 70 42 39 30 13 6 20
85 70 42 39 30 13 6 20
85 70 42 39 30 20 13 6

#include <iostream>
using namespace std;//输出每趟排序结果
void show(int arr[], int size)
{for (int k = 0; k < size; k++){cout << arr[k] << " ";}cout << endl;
}void Binsert_sort(int arr[], int size)
{int i, j, k, low, high, mid, temp;for (i = 1; i < size; i++){temp = arr[i];low = 0;high = i - 1;while (low <= high){mid = (low + high) / 2;if (temp <= arr[mid]){low = mid + 1;}else{high = mid - 1;}}//移位for (j = i - 1; j > high; j--){arr[j + 1] = arr[j];}arr[j + 1] = temp;show(arr, size);}
}int main()
{int t, size;cin >> t;while (t--){cin >> size;int arr[size];for (int i = 0; i < size; i++){cin >> arr[i];}Binsert_sort(arr, size);cout << endl;}return 0;
}