常见排序算法
这几天做题，做到了数组排序这一题，顺便复习了几种典型排序算法。
以下排序算法默认将从小到大排序。如果想要更详细的说明，可以看链接中的动图演示。
排序的稳定性：数组中数值相等的两个元素，其排序前后的相对位置不变。
冒泡排序
冒泡排序的基本思想是，从前往后对数组进行两两比较，将较大者放在后面，这样，每进行一轮的遍历，都会将数组中的最大值放到最后面。
下一轮遍历，遍历长度就可以-1，因为最后的位置已经放了最大值了。
时间复杂度O(n^2)，空间复杂度O(1)。
稳定，因为在交换是相邻交换，交换过程中只有严格大于才交换，等于时不交换。
void bubbleSort(vector<int>& nums){
int length = nums.size();
//外层循环，每一轮将最大值放在最后
//i的值表示内层循环的次数
for(int i=length-1;i>0;i--){
//内层循环，负责两两比较
for(int j=0;j<i;j++){
if(nums[j]>nums[j+1])
swap(nums[j], nums[j+1]);
}
}
}
选择排序
选择排序思想是，每次外层遍历都选出最小值，下一次遍历在最小值以外的部分进行。
时间复杂度O(n^2)，空间复杂度O(1)。
不稳定，因为要进行最小值与首项的交换，交换过程可能会破坏稳定性，比如最小值与首项之间存在一个与首项相等的值，交换之后顺序就变了。
vector<int> selectSort(vector<int>& nums) {
int min_idx;//记录最小值的下标
int length = nums.size();
//外层循环，每次循环找出当前的最小值
//i的值表示内层循环的范围
for(int i=0; i<length; i++){
min_idx = i;//最小值的下标初始化
//内层循环
for(int j=i+1; j<length; j++){
if(nums[j] < nums[min_idx]) min_idx = j;
}
swap(nums[i], nums[min_idx]);
}
return nums;
}
插入排序
插入排序的思想类似于打牌时边摸牌边排序的思路，从前往后对子数组进行排序，每轮排序完都能得到一个长度+1的有序的子数组。
每轮遍历，将无序部分的值一个个按顺序插入有序部分中。
时间复杂度O(n^2)，空间复杂度O(1)。
稳定，因为交换是相邻交换，同冒泡排序。
插入排序应当是三种O(n^2)复杂度的排序中表现最好的。
vector<int> insertSort(vector<int>& nums) {
int length = nums.size();
//外层循环，i表示已经排序好的子数组的长度
for(int i=1; i<length; i++){
//内层循环，从后向前遍历给后续来的元素找到合适的位置
for(int j=i; j>0; j--){
if(nums[j]<nums[j-1])
swap(nums[j], nums[j-1]);
else//由于局部的有序性，后面的元素一定更小
break;
}
}
return nums;
}
插入排序有可以优化的空间，主要在于swap操作比较耗时，可以用赋值代替交换：
vector<int> insertSort(vector<int>& nums) {
int length = nums.size();
int cur ,j;
for(int i=1; i<length; i++){
cur = nums[i];//记录当前值
for(j=i; j>0; j--){
if(nums[j-1] > cur){//如果下一个数大于当前值
nums[j] = nums[j-1];//用赋值代替交换
//相当于把数往后移了一位，前面会空出来
}
else//如果前面的数已经不大于当前值，就可以跳过
break;
}
nums[j] = cur;//把当前值插入空位
}
return nums;
}
由于插入排序对近乎完全有序的数列的排序效率最高。
归并排序
利用递归的思想，将数组用二分的方式进行切分和排序，然后再将排序好的两个部分进行归并。
时间复杂度O(n*log(n))，因为递归层数为log(n)，每层要处理n个数据。 空间复杂度O(n)，归并过程需要额外的暂存数组。
稳定，因为归并的过程可以控制左边的数据放在前面。
void mergeSort(vector<int>& arr, int l, int r){
//归并范围[l...r]
//事实上在小数据量的情况下，插入排序效率优于归并排序
//可以考虑用插入排序代替一部分递归
//如：if(r - l < 16) {insertSort(arr,l,r);return;}
if(l>=r) return;//递归结束条件
int mid = (l + r) / 2;//切分位置。应当注意的是l+r可能整型溢出，可以采用l+(r-l)/2
mergeSort(arr, l, mid);//进行递归
mergeSort(arr, mid+1, r);
//归并
if(arr[mid]>arr[mid+1])//优化，当有序的时候就不需要归并了
merge(arr, l, r, mid);
}
void merge(vector<int>& arr, int l, int r, int mid){
vector<int> temp(r - l + 1);//临时空间
// 0 t_idx r-l
//[l... mid][mid+1...r]
// i j
int i = l, j = mid + 1;
int t_idx = 0;
while(i<=mid && j<=r){
if(arr[i]<arr[j]){
temp[t_idx++] = arr[i++];
}
else{
temp[t_idx++] = arr[j++];
}
}
//尾部数据处理
while(j<=r){
temp[t_idx++] = arr[j++];
}
while(i<=mid){
temp[t_idx++] = arr[i++];
}
//将归并好的数据放回原数组
for(int k=0; k < r-l+1; k++){
arr[l+k] = temp[k];
}
}
快速排序
快速排序是最经典的排序算法，也是在一般情况下效率最高的排序算法。主要思想是先在数组中选定一个基准点，按照基准点将数组分为大于基准点和小于等于基准点的两部分，再递归地对两边的数据进行同样的操作。
但是在数组近乎有序，以及数组中有大量重复元素的情况下，复杂度可能会退化到O(n^2)。
- 可以进行优化，譬如使用随机化基准点，使用三路快排等。
时间复杂度O(n*log(n))，因为递归层数为log(n)，每层要处理n个数据。 空间复杂度O(log(n))，就地排序不需要额外数组，但函数递归需要额外空间。
不稳定，因为基准点的选择和交换会破坏稳定性。
void quickSort(vector<int>& arr){
int length = arr.size();
_quickSort(arr, 0, length-1);
}
void _quickSort(vector<int>& arr, int l, int r){
//在小数据量情况下，插入排序优于递归的排序，可以以此优化
if(l >= r) return;
//分割点的选取
int j = _partition(arr, l, r);
_quickSort(arr, l, j-1);//j-1也可以，因为j本身是有序的
_quickSort(arr, j+1, r);
}
//将[l...r]分成[l...j][j+1...r]两部分，返回j下标
int _partition(vector<int>& arr, int l, int r){
//在近乎有序的数组中，原始的快排算法会出现复杂度退化成O(n^2)的情况
//随机化基准点，避免出现最差情况
swap(arr[l], arr[rand()%(r-l+1)+l]);
//令j为分割点的下标，左边是小于等于arr[j]的值，右边是大于arr[j]的值
int j = l;//初始化j，由于l是基准，这里的j相当于-1
for(int i=l+1;i<=r;i++){
//遍历数据，将小于基准的值换到前面
if(arr[i] <= arr[l]){
//发现小于等于基准的值
//j++并交换，表示左边部分扩大
j = j + 1;
swap(arr[j], arr[i]);
}
}
swap(arr[j], arr[l]);//！！将基准交换到分割点位置！！
return j;
}
评论区