算法刷题总结(五)排序

2021/6/20 22:27:56

本文主要是介绍算法刷题总结(五)排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

常见的排序算法

在这里插入图片描述

下面介绍各排序算法的思路和代码,其中快速排序和归并排序的代码可以在 leetcode. 912 排序数组 里进行测试。

快速排序(QuickSort)

快速排序从数组中随机挑一个数(叫做pivot),把比它小的数放到它左侧,把比它大的数放到它右侧,再对它左侧和右侧的子数组分别重复这个操作。

快排分三步:(1)停止条件;(2)partition函数找到pivot应该在的位置;(3)对pivot左右part分别递归。快排最关键的是partition函数,它将pivot放到该在的位置并返回这个位置。partition函数有lomuto、hoare、经典快排三种实现方式,下面分别给出这三种实现。

1. lomuto partition

把随机选出的pivot放到末尾,用j往右遍历整个数组,遍历过程中将比pivot小的元素换到前面,用i来标记已知的小元素在的区间[1, i)。等j遍历完,位置i上的元素就是第一个>=pivot的元素,把pivot换到这个位置上去。
优点:不易出错,单向遍历(适合链表的快排)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        quickSort(nums, 0, nums.size() - 1); //左闭右闭的写法,左右区间都能取到
        return nums;
    }

    void quickSort(vector<int>& nums, int low, int high)
    {
        if(high <= low) return; //迭代终止条件:没有元素(<)或只有一个元素(=)
        int p = partition(nums, low, high);
        quickSort(nums, low, p - 1);
        quickSort(nums, p + 1, high);
    }

    int partition(vector<int> &nums, int low, int high)
    {
        //partition的Lomuto实现方式
        int pivot = low + rand() % (high - low + 1); //随机选取一个数字作为pivot。也可以直接取开头或结尾的数字,但遇到不好的case会超时
        swap(nums[pivot], nums[high]); //把pivot放在结尾,会好写一点
        int i = low;
        for(int j = i; j < high; ++j)
        {
            if(nums[j] < nums[high])
            {
                swap(nums[i], nums[j]);
                ++i;
            }
        }
        swap(nums[i], nums[high]); // [1, i)是所有小于pivot的元素,pivot在结尾,把i位置的元素跟pivot换一下就行了
        return i;
    }
};

2. hoare partition

把中间的元素当做pivot,用i和j分别从左侧和右侧向中间遍历数组,i记录比pivot小的,j记录比pivot大的,如果不满足条件就交换i和j的元素。注意pivot可能会被换位置,返回的j只能保证pivot在[low, j]区间内,但不一定在位置j上,所以迭代时要取到p。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        quickSort(nums, 0, nums.size() - 1); //左闭右闭的写法,左右区间都能取到
        return nums;
    }

    void quickSort(vector<int>& nums, int low, int high)
    {
        if(high <= low) return; //迭代终止条件:没有元素(<)或只有一个元素(=)
        int p = partition(nums, low, high);
        quickSort(nums, low, p); //hoare partition时,locPivot位置并非一定是pivot所在的位置,pivot在[low, p]内任一位置,所以这里取到了p、不是取到p-1
        quickSort(nums, p + 1, high);
    }

    int partition(vector<int> &nums, int low, int high)
    {
        //partition的hoare实现方式
        int p = low + (high - low) / 2;
        int pivot = nums[p]; //hoare partition时,一开始选的pivot可能会被换位置,所以要跟pivot的值比较,不能跟nums这个位置上的的数字比较
        int i = low, j = high;
        while(true)
        {
            while(nums[i] < pivot) ++i;
            while(nums[j] > pivot) --j;
            if(i >= j) return j;
            swap(nums[i], nums[j]);
            ++i;
            --j;
        }
    }
};

3. 经典快排

对hoare partition的改进,减少交换次数。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        quickSort(nums, 0, nums.size() - 1); //左闭右闭的写法,左右区间都能取到
        return nums;
    }

   void quickSort(vector<int> & nums, int low, int high)
    {
        if(low >= high) return;
        int locPivot = partition(nums, low, high);
        quickSort(nums, low, locPivot); // 取到了locPivot
        quickSort(nums, locPivot + 1, high);
    }

    int partition(vector<int> & nums, int low, int high)
    {
        int p = rand() % (high - low + 1) + low;
        int pivot = nums[p];
        swap(nums[p], nums[low]);
        while(low < high)
        {
            while(low < high && nums[high] >= pivot) --high; //注意>=
            nums[low] = nums[high];
            while(low < high && nums[low] <= pivot) ++low; //注意<=
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }
};

归并排序(MergeSort)

归并排序将数组分成两个子数组,分别对两个子数组排序,然后合并这两个有序数组。

归并排序有递归和迭代两种写法,下面分别给出这两种实现方式。归并排序最重要的合并两个有序数组的merge函数。

1. 递归(Recursive):自上而下

class Solution {
public:
    // 归并排序方法一:递归recursive,自上而下
    // 分三步:(1)终止条件;(2)把当前序列平分成两个子序列,分别进行递归排序;(3)用双指针对两个递增子序列的结果进行merge
    vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        vector<int> tmp(nums.size(), 0); //需要一个额外的辅助空间
        mergeSortRecursive(nums, 0, nums.size() - 1, tmp);
        return nums;
    }

    // 通用的merge函数:对nums[low,...,mid]和nums[mid+1,...,high]两个递增数组进行合并
    void merge(vector<int> & nums, int low, int mid, int high, vector<int> & tmp)
    {
        int i = low, j = mid + 1, k = low; // i是子序列1的起始位置,j是子序列2的起始位置,k是暂存数组tmp的索引
        while(i <= mid && j <= high)
        {
            if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= high) tmp[k++] = nums[j++];
        for(int p = low; p <= high; ++p)
        {
            nums[p] = tmp[p];
        }
    }
    
    void mergeSortRecursive(vector<int>& nums, int low, int high, vector<int> & tmp)
    {
        if(low >= high) return ; //没有元素,或只有一个元素
        int mid = low + (high - low) / 2;
        mergeSortRecursive(nums, low, mid, tmp);
        mergeSortRecursive(nums, mid + 1, high, tmp);
        merge(nums, low, mid, high, tmp);
    }
};

2. 迭代(Iterative):自下而上

class Solution {
public:
    // 归并排序方法二:迭代iterative,自下而上
    // 分两步:(1)对子序列长度len从1开始进行2倍递增;(2)根据当前len计算得到相邻两个子序列的low、mid、high,进行merge;
    vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        vector<int> tmp(nums.size(), 0); //需要一个额外的辅助空间
        int n = nums.size();
        for(int len = 1; len < n; len *= 2) //len表示两两merge的子序列中,一个子序列的长度。从1,2,4,8这样两倍变化
        {
            for(int low = 0; low < n; low += 2*len) //low表示每两两merge的子序列中,第一个子序列的起始位置
            {
                int mid = min(low + len - 1, n - 1); // mid表示每两两merge的子序列中,第一个子序列的结束位置
                int high = min(low + 2 * len - 1, n - 1); //high表示每两两merge的子序列中,第二个子序列的结束位置
                merge(nums, low, mid, high, tmp);
            }
        }
        return nums;
    }

    // 通用的merge函数:对nums[low,...,mid]和nums[mid+1,...,high]两个递增数组进行合并
    void merge(vector<int> & nums, int low, int mid, int high, vector<int> & tmp)
    {
        int i = low, j = mid + 1, k = low; // i是子序列1的起始位置,j是子序列2的起始位置,k是暂存数组tmp的索引
        while(i <= mid && j <= high)
        {
            if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= high) tmp[k++] = nums[j++];
        for(int p = low; p <= high; ++p)
        {
            nums[p] = tmp[p];
        }
    }
};

插入排序(InsertionSort)

插入排序时,i从左到右遍历整个数组,将nums[i]插入到[0, i-1]的已排序区间里该在的位置。插入方法是倒着交换过去。
在这里插入图片描述

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

冒泡排序(BubbleSort)

从左到右遍历数组,对相邻的两个元素进行比较,看是否左<=右,如果不满足就让它俩互换。一次冒泡会让最大的放到最后面,重复 n 次,就完成了 n 个数据的排序工作。当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不用再继续执行后续的冒泡操作。
一次冒泡:
在这里插入图片描述
n次冒泡:
在这里插入图片描述

void bubbleSort(vector<int> & nums)
{
	bool swapped;
	for(int i = 1; i < nums.size(); ++i)
	{
		swapped = false;
		for(int j = 1; j < nums.size() - i + 1; ++j)
		{
			if(nums[j] < nums[j - 1])
			{
				swap(nums[j], nums[j - 1]);
				swapped = true;
			}
		}
		if(!swapped)
		{
			break;
		}
	}
}

选择排序(SelectionSort)

选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

在这里插入图片描述

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

K-th element相关题目

leetcode 215. 数组中的第K个最大元素

leetcode 347. 前 K 个高频元素

本文的配图摘自极客时间APP的《数据结构与算法之美》课程插图。



这篇关于算法刷题总结(五)排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程