选择排序 冒泡排序

选择排序

思想：

1.遍历数组，找到数组最大值，记录最大值的下标，将最大值与最后一个值进行交换

2.将剩下的数组，重新找最大值，重复第一步，直到所有的数组排好顺序

代码：

void selectSort(vector<int>v){int n = v.size();for(int i=1;i<n;i++){int max_id = 0for(int j=1;j<n-i;i++){if(v[j]>v[max_id]) max_id=j;}swap(v[max_id],v[n-i]);}
}

时间复杂度 O(n2)

空间复杂度 O(1）

稳定性 不稳定

冒泡排序

思想：

1.从左到右，相邻两个数字进行比较，如果左边的数大于右边的数，则两个数字交换位置，确定该数组最大数字在最后一位

2.重复此操作直到全部数字排序完成

3.优化：如果数组在遍历过程中未发生交换，直接结束排序

代码：

void BubbleSort(vector<int>v{int n =v.size();for(int i=1;i<n;i++){bool flag = 1;for(int j=0;j<n-i;j++){if(v[j]>v[j+1]){swap(v[j],v[j+1]);flag = 0;}}if(flag) return;}
}

时间复杂度：O(n2)

空间复杂度：O(1)

稳定性： 稳定