SCAU8639--折半插入排序

8639 折半插入排序

时间限制:1000MS  代码长度限制:10KB
提交次数:1738 通过次数:1371

题型: 编程题   语言: G++;GCC

Description

用函数实现折半插入排序，并输出每趟排序的结果.

 

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

 

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

 

输入样例

10
5 4 8 0 9 3 2 6 7 1

 

输出样例

4 5 8 0 9 3 2 6 7 1
4 5 8 0 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 3 4 5 8 9 2 6 7 1
0 2 3 4 5 8 9 6 7 1
0 2 3 4 5 6 8 9 7 1
0 2 3 4 5 6 7 8 9 1
0 1 2 3 4 5 6 7 8 9

#include <iostream>
#include <vector>
using namespace std;// 折半插入排序函数
void binaryInsertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int left = 0;int right = i - 1;// 折半查找插入位置while (left <= right) {int mid = (left + right) / 2;if (key < arr[mid])right = mid - 1;elseleft = mid + 1;}// 移动元素给 key 腾位置for (int j = i - 1; j >= left; --j) {arr[j + 1] = arr[j];}arr[left] = key;// 输出当前排序状态for (int k = 0; k < n; ++k) {cout << arr[k];if (k < n - 1) cout << " ";}cout << endl;}
}int main() {int n;cin >> n;vector<int> arr(n);// 读入数组for (int i = 0; i < n; ++i) {cin >> arr[i];}// 调用排序函数binaryInsertionSort(arr);return 0;
}