常用的排序算法

总结常用的排序算法

主要包括冒泡排序、堆排序、归并排序、快速排序四个。

冒泡排序

冒泡排序是一种很简单的原地排序算法，在每一轮遍历都将最大的元素（或者最小）放在数组的末尾
过程为：

1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 重复步骤1~3，直到排序完成
   平均时间复杂度：O(n^2)

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

堆排序

堆排序是一种原地排序算法，依赖于堆实现
过程为：

1. 将原数组调整为大顶堆（或小顶堆）
2. 交换堆顶与数组末尾元素，再将剩余元素调整为大顶堆
3. 不断重复步骤2直到数组有序
   每次调整堆的时间复杂度位O(logn)，一共需要调整n次，总时间复杂度位O(nlogn)

void Heapfiy(vector<int>& nums,int n,int i)
{
    int largest=i;
    int left=2*i+1;
    int right=2*i+2;
    while (true) {
        if (left < n && nums[left] > nums[largest]) {
            largest = left;
        }

        if (right < n && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest == i) {
            break;
        }

        swap(nums[i], nums[largest]);
        i = largest;
        left = 2 * i + 1;
        right = 2 * i + 2;
    }
}

void HeapSort(vector<int>& nums)
{
    int n=nums.size();
    // 构造大顶堆
    // 从最后一个非叶子节点开始
    for(int i=n/2-1;i>=0;i--){
        Heapfiy(nums,n,i);
    }

    // 交换堆顶元素并调整堆
    for(int i=n-1;i>=0;i--){
        swap(nums[0],nums[i]);
        Heapfiy(nums,i,0);
    }   
}

归并排序

归并依赖于递归操作
过程为：

1. 将原数组分为左右两个子数组
2. 将数组递归分为左右两个子数组
3. 将左右两个子数组合并有有序数组
   评价时间复杂度为O(nlogn)

void Merge(vector<int>& nums,int left,int mid,int right)
{
    vector<int> temp(right-left+1);
    int i=left;
    int j=right;
    int k=0;
    while(i<=left && j<=right){
        // 将两个数组合并为一个有序数组
        if(nums[i]<=nums[j]){
            temp[k]=nums[i];
            i++;
        }else{
            temp[k]=nums[j];
            j++;
        }
        k++;
    }

    while(i<=left){
        temp[k++]=nums[i++];
    }

    while(j<=right){
        temp[k++]=nums[j++];
    }

    for(int t=0;t<k;t++){
        nums[left+t]=temp[t];
    }
}

void MergeSort(vector<int>& nums,int left,int right)
{
    if(left>=right){
        return;
    }
    int mid=left+(right-left)/2;
    MergeSort(nums,left,mid);
    MergeSort(nums,mid+1,right);
    Merge(nums,left,mid,right);
}

快速排序

快排是最常用的排序算法之一
过程为：

1. 选择一个基准值（一般为第一个或最后一个），将原数组分为两个数组
2. 比基准值小的元素放在基准值左边，比基准值大的元素放在右边
3. 递归调用左右两个子数组，重复上述步骤
   平均时间复杂度为O(nlogn)

int partition(vector<int>& nums,int left,int right)
{
    int base=nums[left];
    while(left<right){
        while(left<right && nums[right]>=base){
            right--;
        }
        nums[left]=nums[right];
        while(left<right && nums[left]<=base){
            left++;
        }
        nums[right]=nums[left];
    }
    nums[left]=base;
    return left;    
}


void QuickSort(vector<int>& nums,int left,int right)
{
    if(left<right){
        int pos=partition(nums,left,right);
        QuickSort(nums,left,pos-1);
        QuickSort(nums,pos+1,right);       
    }
}

• 本文作者： KongXinQing
• 本文链接： https://13114987559.github.io/2024/04/29/essay/常用的排序算法/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！