AcWing 3477. 简单排序
原题链接
简单
C++ 代码
//直接插入排序,寻找元素时用二分查找
#include<stdio.h>
using namespace std;
const int N = 1000;
int arr[N],cnt;
int l,r;
void binaryInsertSort(int n){
for(int i = 1; i < n; i++){
int temp = arr[i];
l = 0;
r = i - 1;
while(l < r){//找第一个大于它的值
int mid = (l+r)/2;
if(arr[mid] >= temp+1) r = mid;
else l = mid+1;
}
if(arr[l]>temp){//如果找不到那么,就是l = n-1,此时arr[l]可能就不是要找的值,所以要判断下
for(int j = i - 1; j >= l; --j){
arr[j+1] = arr[j];
}
arr[l] = temp;
}
}
}
int main(){
int n;
int b[N] = {0};
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%d",&arr[i]);
}
binaryInsertSort(n);
for(int i = 0; i < n; i++){
b[arr[i]]++;
}
for(int i = 0; i < n; i++){
if(b[arr[i]]==1) printf("%d ",arr[i]);
else if(b[arr[i]]>1){
printf("%d ",arr[i]);
b[arr[i]] = 0;
}
}
return 0;
}