插入排序 计数排序 包括 代码 时间复杂度 空间复杂度 稳定性 是否能对代码进行提升

插入排序

代码：

void insertsort(vector<int>&v){
  int n=v.size();
  for(int i=0;i<n;i++){
    int j=i-1;
    temp=v[i];
    for(;j>=0;j--){
      if(v[j]>temp){
        v[j+1]=v[j];
      }
      else{
        break;
      }
    }
     v[j+1]=temp;
  }
}
int main(){
  vector<int>&v{1,2,3,4,2,3,4};
  insertsort(v);
  for(int i=0;i<v.size();i++){
    cout<<v[i]<" ";
  }
  return 0;
}

平均时间复杂度：o（n2）

最好时间复杂度（全部有序）：o（n）

比较n-1趟每一趟比较一次，不移动元素，最好时间复杂度为o（n）

最坏时间复杂度（全部逆序）：o（n2）

空间复杂度：o（1）

稳定性：稳定

计数排序：

代码：

#include<iostream>
#include<vector>
using namespace std;
int maxval(vector<int>& v) {
	int n = v.size();
	int max = v[0];
	for (int i = 1; i < n; i++) {
		if (v[i] > max) {
			max = v[i];
		}
	}return max;
}
void bucketsort(vector<int>& v) {
	int n = v.size();
	int max = maxval(v);
	vector<int>bucket(max + 1);
	for (int i = 0; i < n; i++) {
		bucket[v[i]]++;

	}
	int index = 0;
	for (int i = 0; i < max + 1; i++) {
		while (bucket[i]--) {
			v[index++] = i;
		}
	}
}
int main() {
	vector<int>v{ 89,67,355,445,20,46 };
	bucketsort(v);
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	
	return 0;
}

平均时间复杂度：o（n）

空间复杂度：o（n）

稳定性：稳定