基础算法的常用模板【1】——排序算法

排序算法

快速排序算法模板

void quick_sort(vector<int>& q, int l, int r)
{
    if (l >= r) return;//元素个数只有一个或者没有
    //+-操作是为了先移动，可以指向真正的边界
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    //根据递归的边界选择
    //如果是quick_sort(q, l, j), quick_sort(q, j + 1, r);就不能选择x = q[r];
    //如果是quick_sort(q, l, i - 1), quick_sort(q, i, r);就不能选择x = q[l];
    //否则会死循环
    //x可以是
    //x = q[l]; x = q[r];
    //x = q[rand() % (r - l+ 1) + r; // 基于随机的原则;
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);//两个指针没有相遇，就交换一下
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序算法模板

void merge_sort(vector<int>& q, int l, int r)
{
    if (l >= r) return;//元素个数只有一个或者没有

    int mid = l + r >> 1;//找中点
    merge_sort(q, l, mid);//递归
    merge_sort(q, mid + 1, r);
    //归并两个有序序列变成一个有序序列
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
	//把两边没有循环的扫尾一遍
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
	//赋值回去
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

插入排序算法模板

void insert_sort(vector<int>& nums, int l, int r)
{
	for(int i = l; i < r; ++i)
	{
		int end = i;
		int temp = nums[i + 1];
		//end之前的为有序
		while(end >= l)
			if(temp < nums[end]) nums[end + 1] = nums[end--];
			else break;
		nums[end + 1] = temp;
	}
	return ;
}

堆排序算法模板

[leetcode912]试一下(https://leetcode.cn/problems/sort-an-array/submissions/)

//快排
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quikSort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void quikSort(vector<int>& nums, int l, int r)
    {
        if(l >= r)
            return;
        int i = l - 1, j = r + 1, x = nums[l + r >> 1];
        while (i < j)
        {
            do i ++ ; while (nums[i] < x);
            do j -- ; while (nums[j] > x);
            if(i < j)
                swap(nums[i], nums[j]); 
       }

        quikSort(nums, l, j);
        quikSort(nums, j + 1, r);
        return ;
    }

};

//归并,不太一样是因为temp大小复制成了和输入向量大小一致的向量
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        temp = nums;
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void merge_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        //归并
        int k = l, i = l, j = mid + 1;
        while(i <= mid && j <= r)
            if(nums[i] <= nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        while(i <= mid) temp[k++] = nums[i++];
        while(j <= r) temp[k++] = nums[j++];
        for(i = l; i <= r; i++)nums[i] = temp[i];
    }
    vector<int> temp;
};

//插入,超时
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        insert_sort(nums, 0, nums.size() - 1);
        return nums;
    }
    
    void insert_sort(vector<int>& nums, int l, int r)
    {
        for(int i = l; i < r; ++i)
        {
            int end = i;
            int temp = nums[i + 1];
            //end之前的为有序
            while(end >= l)
                if(temp < nums[end])
                {
                    nums[end + 1] = nums[end];
                    --end;
                } 
                else break;
            nums[end + 1] = temp;
        }
        return ;
    }
};