题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
include [HTML_REMOVED]
using namespace std;
const int M=1e5+10;
//insertion sort
void trace(int A[], int N) {
int i;
for (int i = 0; i < N; i++)
cout << A[i] << ” “;
cout << endl;
}
void InsertionSort(int A[], int N) {
int i, j, v;
// 最开始的时候是从第二个位置开始和第一位置的数进行比较
for (int i = 1; i < N; i++) {
v = A[i]; //用于insert的数
j = i - 1;
while (j >= 0 && A[j] > v) {
A[j + 1] = A[j];
j--;
}
//退出循环后,我们得到的j所对应的值要不就是小于0 要不就是小于等于v了
//所以 j的后一位,也就是j+1位才是we should insert 的位置
A[j + 1] = v;
// trace(A, N);
}
}
int main() {
int N, i, j;
// int A[100];
int A[M];
cin >> N;
for (int i = 0; i < N; i++)
cin >> A[i];
//trace(A, N);
InsertionSort(A, N);
trace(A, N);
return 0;
}
blablabla