[排序][常见三种][C++实现]

最近在慢慢梳理，对于常见的一些排序算法，简单的例如冒泡，插入，选择这种就不写了，这里写三种感觉有可能问到的：堆排，归并，快排

1.堆排

简单总结下堆排序的基本思路：

　　a.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

其中建堆的时间复杂度为O(n)，而排序时候与二叉树类似，它的最坏，最好，平均时间复杂度均为O(nlogn)，总体还是为O(nlogn)

#include <bits/stdc++.h>
using namespace std;

void adjust(vector<int>& nums,int size,int idx){ //堆的调整
    int left=idx*2+1;
    int right=idx*2+2;
    int max_idx=idx; //选定的最大节点的序号
    if(left<size && nums[left]>nums[max_idx]){
        max_idx=left;
    }
    if(right<size && nums[right]>nums[max_idx]){
        max_idx=right;
    }
    if(max_idx!=idx){ //如果此时进行过改变了
        swap(nums[max_idx],nums[idx]);
        adjust(nums,size,max_idx); //此时是需要进行调整子树中的所有节点，使得仍然满足开始时堆的条件
    }
}

void heap_sort(vector<int>& nums,int size,int idx){
    for(int i=idx;i>=0;--i){ //从后往前进行
        adjust(nums,size,i);
    }
    for(int i=size-1;i>=1;--i){ //因为至少要有1个节点，因此循环到i=1即停止
        swap(nums[i],nums[0]); //最大元素沉底
        adjust(nums,i,0); //此时进行的size大小需要修改为i，并且从根开始进行调整堆
    }
}



int main(){
    vector<int> nums{1,224,5,6,54,4,61,9,11,14,18};
    int size=nums.size();
    int idx=size/2-1; //这是从后往前的第一个非叶子节点的坐标
    heap_sort(nums,size,idx);
    for(int i=0;i<size;++i){
        cout<<nums[i]<<endl;
    }
    system("pause");
    return 0;
}

2.归并

典型的递归回溯，leetcode上也有很多类似题，基本思路为二分到只剩1个后进行合并，然后反着合并直到整体有序

总的时间复杂度O(nlogn)，其中merge的合并时间复杂度为O(n)，并且基归冒插，这是稳定的排序方法

class Solution{
public:
    int Merge_sort(vector<int>& nums,int first,int last){
    	if(first<last){
    		int mid=(last+first)/2;
    		Merge_sort(nums,first,mid);//左边有序
		Merge_sort(nums,mid+1,last);//右边有序
		merge(nums,first,mid,last);//将两个有序的数组进行合并 
	}
    }
    void merge(vector<int>& nums,int first,int mid,int last){
    	vector<int> res(last-first+1,0);//我每次在合并之前先申请相应长度的数组来存储
    	int l=first,r=mid+1,k=0;
    	while(l<=mid && r<=last){
    		if(nums[l]<=nums[r]){
    			res[k++]=nums[l++];
		}
		else{
			res[k++]=nums[r++];
		}
	}
	while(l<=mid){
		res[k++]=nums[l++];
	}
	while(r<=last){
		res[k++]=nums[r++];
	}
	//用合并完成的数组来覆盖原数组的值 
	for(int i=0;i<res.size();i++){
		nums[i+first]=res[i];
	    }
	}
};

3.快排

跟归并其实有点类似，也是递归进行。

基本思想就是挖坑+填坑，一般选取第一个数为基准。之后i,j从两头往中间走，首先观察j的一侧是否值比target小，如果是的话填到第一个位置去，之后从i开始走，找第一个大于target的值，填到前面j空出的位置，结束循环后，target填到最终间的位置，然后左右两部分递归进行，直到整体有序。

void quick_sort(int s[], int l, int r){
    if (l < r){
    //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换（如果要求以中间数作为基准数的话）
    int i = 0, j = r, x = s[0];
    while (i < j){
        while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
            j--;
        if(i < j)
            s[i++] = s[j];
        while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
            i++;
        if(i < j)
            s[j--] = s[i];
    }
    s[i] = x;
    quick_sort(s, l, i - 1); // 递归调用
    quick_sort(s, i + 1, r);
    }
｝