算法刷题总结（五）排序

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

常见的排序算法

下面介绍各排序算法的思路和代码，其中快速排序和归并排序的代码可以在 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的《数据结构与算法之美》课程插图。

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