void insertion_sort(vector<int> &num){
for(int i = 1; i < num.size(); i++){
int j = i-1;
int val = num[i];
while(j>=0 && num[j] >= val){
num[j+1] = num[j];
j--;
}
num[j+1] = val;
}
}
每次迭代时,将num[i] 作为key值。且前子数组[0,i-1] 构成已排好序。每次与左边的数比較。未满足条件。则进行右移
//降序
void insertion_sort(vector<int> &num){
for(int i = 1; i < num.size(); i++){
int j = i-1;
int val = num[i];
while(j>=0 && num[j] < val){
num[j+1] = num[j];
j--;
}
num[j+1] = val;
}
}
效率分析:
最优情况:
原数列已排好序,即不进行while循环,效率为 n
最差情况:
原数列为逆序,则每次迭代要进行i-1次循环,则效率为 n方