AK F.*ing leetcode 流浪计划之快速排序

LightningBilly · 2021 年4 月 24 日 11:17

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

快速排序是一种交换排序，其原理是选定一个基准，对数组进行partition操作，使得数组的左边都小于等于该基准，右边都大于等于该基准，然后以该基准为中心分成2段再对2段分别进行上述操作。c++排序就是快速排序的一种实现，在面试中也经常被问到其原理，甚至会让手写快速排序。partition操作本身也能解决很多算法题。学习与解理快速排序算法原理，不管是对于语言排序源码的理解，还是解决算法题都是非常有帮助的。防止在面试时眼高手低。

由于快速实现在各语言中都有，这里主要以int为例，讲解原理，以及排序的实现。最后结合题目讲解快速排序的应用。

本文中快排原理参照严版《数据结构与算法》，公众号内回复“数据结构”可以获取pdf电子版。

二、基本概念

快速排序是一种交换排序, 定义为QSort(arr, low, high)

每次先用partition，找到mid, 再对左右部分分别进行排序 QSort(arr, low, mid-1), QSort(arr, mid+1, high)。

其核心算法是partition算法partition(arr, low, high)。

其作用是以pivot=arr[low]为基准，将arr[low]到arr[high]进行重排，使得pivot所在位置的左边都小于等于pivot, 右边都大于等于pivot。

利用上述算法可以快速将pivot放到最终有序的正确位置。

利用上述性质可以快速找到数组中第K大（小）的数。

三、作用

对元素进行排序。
取集合中前K大元素。
查找第K大数。
通过定义多维条件，快速选择第K最优解。

四、方法定义及算法

方法定义

    // 主要操作：
    Partition(arr, low, high) // 核心调整算法
	  QuickSort(arr, low, high) // 快速排序

算法描述

图1 partition算法过程

partition过程实现的方法不止一种，我这边里采用的是严版数据结构里的算法。

调整后6放到了正确位置，左边的数字都小于或等于6，右边的数字大于或等于6.

Partition(arr, low, high): // partition算法, 如图动画，调整后pivot左边都小于等于pivot, 右边都大于等于
	pivot <- arr[low]
	while (low<high) {
		while (low<high && arr[high] >= pivot) {high--}// 一定要有等于判断，否则会死循环
		arr[low]<-arr[high]
		while (low<high && arr[low] <= pivot) {low++} // 一定要有等于判断，否则会死循环
		arr[high]<-arr[low]
	}

	arr[low]<-pivot
	return low

QuickSort(arr, low, high): // 快速排序
	if low>=high { // 少于一个元素，不用排序
		return
	}

	mid <- Partition(arr, low, high) // 取到中间点
	QuickSort(arr, low, mid-1) // 排序左边
	QuickSort(arr, mid+1, high) // 排序右边

五、具体实现

package main

import (
	"fmt"
)


func Partition(arr []int, low, high int) int {
	pivot := arr[low]
	for low<high {
		for low<high && arr[high] >= pivot {high--}// 一定要有等于判断，否则会死循环
		arr[low]=arr[high]
		for low<high && arr[low] <= pivot {low++} // 一定要有等于判断，否则会死循环
		arr[high]=arr[low]
	}

	arr[low]=pivot
	return low
}

func QuickSort(arr []int, low, high int) {
	if low>=high { // 少于一个元素，不用排序
		return
	}

	mid := Partition(arr, low, high) // 取到中间点
	QuickSort(arr, low, mid-1) // 排序左边
	QuickSort(arr, mid+1, high) // 排序右边
}


func main() {
	arr := []int{10,6,7,12,18,12,1,2,4,3}
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)

	arr = []int{1,1,1,1,1}
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)


	arr = []int{}
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)

	arr = []int{1}
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

复杂度分析，QuickSort最多递归log(n) 层, 每层Partition就是遍历整个数组，整体复杂度O(nlog(n))。

以上代码只是为了理解快速排序原理作的简单实现，扩展性不好，实际应用可以直接使用go语言库。

特殊case处理，当遇到 [1，2，3，4，5]这样有序的数组时，Partition每次返回的mid就是low, 导致递归层数为O(n) 最后复杂度为O(n^2)。优化方案，Partition 时，随机一个数index, swap(arr[low], arr[index]). 然后继续Partition过程，c++中快速排序就是采用的随机方案。

六、牛刀小试

练习1 验证代码是否正确，排序应用

题目链接力扣

题目大意

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

题目解析

原意是希望选手使用链表，这里是为了验证本文代码正确性。先转化成数组，然后利用快速排序，再赋值回链表。

AC代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */


func Partition(arr []int, low, high int) int {
	pivot := arr[low]
	for low<high {
		for low<high && arr[high] >= pivot {high--}// 一定要有等于判断，否则会死循环
		arr[low]=arr[high]
		for low<high && arr[low] <= pivot {low++} // 一定要有等于判断，否则会死循环
		arr[high]=arr[low]
	}

	arr[low]=pivot
	return low
}

func QuickSort(arr []int, low, high int) {
	if low>=high { // 少于一个元素，不用排序
		return
	}

	mid := Partition(arr, low, high) // 取到中间点
	QuickSort(arr, low, mid-1) // 排序左边
	QuickSort(arr, mid+1, high) // 排序右边
}



func sortList(head *ListNode) *ListNode {
	arr := []int{}
	for t:=head;t!=nil;t=t.Next {
		arr  = append(arr, t.Val)
	}

	QuickSort(arr, 0, len(arr)-1)
	for t:=head;t!=nil;t=t.Next {
		t.Val = arr[0]
		arr = arr[1:]
	}

	return head
}

练习2 利用partition取集合中前K小个元素

题目链接：力扣

题目大意

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

题目解析

根据partition作用的描述，最终会使pivot左边都小于pivot, 右边都大于pivot，说明pivot经过一次patition后会落在最终正确的位置上。那么可以根据返回的mid, 判断pivot是否在前k数字里。

AC代码

func Partition(arr []int, low, high int) int {
	pivot := arr[low]
	for low<high {
		for low<high && arr[high] >= pivot {high--}// 一定要有等于判断，否则会死循环
		arr[low]=arr[high]
		for low<high && arr[low] <= pivot {low++} // 一定要有等于判断，否则会死循环
		arr[high]=arr[low]
	}

	arr[low]=pivot
	return low
}

func QuickSort(arr []int, low, high int) {
	if low>=high { // 少于一个元素，不用排序
		return
	}

	mid := Partition(arr, low, high) // 取到中间点
	QuickSort(arr, low, mid-1) // 排序左边
	QuickSort(arr, mid+1, high) // 排序右边
}

func getLeastNumbers(arr []int, k int) []int {
	low, high := 0, len(arr)-1
	for k>0 {// k 有可能为0
		mid := Partition(arr, low, high) // 对当前low, high进行排序，看mid-low与k的关系
		preNum := mid-low+1
		if  preNum == k { // arr[low, mid] 刚好满足K个元素
			return arr[:mid+1] // arr[mid]是最后一个元素 slice是前闭后开
		} 
		
		if preNum >k{ // 数量太多了mid往后的不用考虑了
			high = mid-1
		} else {
			low = mid+1
			// arr[low, mid] 已经被选中，k要减少
			k -= preNum
		}
	}
	
	return nil
}

练习3 利用partition取集合中第K大元素

题目链接：力扣

题目大意

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题目解析

根据partition作用的描述，最终会使pivot左边都小于pivot, 右边都大于pivot，说明pivot经过一次patition后会落在最终正确的位置上。那么可以根据返回的mid, 判断pivot是否在前k数字里。

AC代码

func Partition(arr []int, low, high int) int {
	pivot := arr[low]
	// 取第K大，需要把判断每件改一下
	for low<high {
		for low<high && arr[high] <= pivot {high--} // 大的排前面
		arr[low]=arr[high]
		for low<high && arr[low] >= pivot {low++}
		arr[high]=arr[low]
	}

	arr[low]=pivot
	return low
}

func findKthLargest(nums []int, k int) int {
	low, high := 0, len(nums)-1
	for  { // 肯定有答案最终会直接返回
		mid := Partition(nums, low, high) // 对当前low, high进行排序，看mid-low与k的关系
		preNum := mid-low+1
		if  preNum == k { // mid 正好是第K个，mid之前的元素都是比arr[mid]大
			return nums[mid] 
		}

		if preNum >k{ // arr[low:mid] 已经有K个元素了，后面了不用考虑了
			high = mid-1
		} else {
			low = mid+1
			// arr[low, mid] 已经被去除了，k要减少
			k -= preNum
		}
	}

	return 0
}

练习4 通过定义多维条件，快速选择前K个最优解

题目链接：力扣

题目大意

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

（这里，平面上两点之间的距离是欧几里德距离。）

你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。

示例 1：

输入：points = [[1,3],[-2,2]], K = 1
输出：[[-2,2]]
解释：
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], K = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

题目解析

设有2点p1,p2, 重定义判断条件为 sqrt(p1[0]^2+p1[1]^2) 与sqrt(p2[0]^2+p2[1]^2) ，直接比较浮点数不精确要优化。由于大家都开根号，同时取平方大小关系不变，所以就判断p1[0]^2+p1[1]^2 与p2[0]^2+p2[1]^2 关系就可以。

根据partition作用的描述，最终会使pivot左边都小于pivot, 右边都大于pivot，说明pivot经过一次patition后会落在最终正确的位置上。那么可以根据返回的mid, 判断pivot是否在前k数字里。

AC代码

/* -1 :<
0:=
1:>
 */
func PointRelation(p1, p2 []int) int {
	s1, s2 := p1[0]*p1[0] +p1[1]*p1[1], p2[0]*p2[0] +p2[1]*p2[1]
	if s1>s2 {return 1}
	if s1==s2 {return 0}
	return -1
}
func Partition(arr [][]int, low, high int) int {
	pivot := arr[low]
	for low<high {
		for low<high && PointRelation(arr[high], pivot) >= 0 {high--}// 一定要有等于判断，否则会死循环
		arr[low]=arr[high]
		for low<high && PointRelation(arr[low], pivot)  <= 0 {low++} // 一定要有等于判断，否则会死循环
		arr[high]=arr[low]
	}

	arr[low]=pivot
	return low
}

func kClosest(points [][]int, k int) [][]int {
	low, high := 0, len(points)-1
	for k>0 {// k 有可能为0
		mid := Partition(points, low, high) // 对当前low, high进行排序，看mid-low与k的关系
		preNum := mid-low+1
		if  preNum == k { // arr[low, mid] 刚好满足K个元素
			return points[:mid+1] // arr[mid]是最后一个元素 slice是前闭后开
		}

		if preNum >k{ // 数量太多了mid往后的不用考虑了
			high = mid-1
		} else {
			low = mid+1
			// arr[low, mid] 已经被选中，k要减少
			k -= preNum
		}
	}

	return nil
}

七、总结

主要内容：

快速排序是一种交换排序，其原理是选定一个基准，对数组进行partition操作，使得数组的左边都小于等于该基准，右边都大于等于该基准，然后以该基准为中心分成2段再对2段分别进行上述操作。
介绍了patition算法原理。
作用：1）对元素进行排序。2）取集合中前K大元素。3）查找第K大数。4）通过定义多维条件，快速选择第K最优解。

笔者水平有限，有写得不对或者解释不清楚的地方还望大家指出，我会尽自己最大努力去完善。

下面我精心准备了几个流行网站上的题目（首先AK F.*ing leetcode），给大家准备了一些题目，供大家练习参考。干他F.*ing (Fighting?)。

八、实战训练

代码基础训练题

光说不练假把式，学完了怎么也要实操一下吧，快快动用把刚才那4题A了。

排序应用力扣
利用partition取集合中前K小个元素：力扣
利用partition取集合中第K大元素：力扣
通过定义多维条件，快速选择前K个最优解: 力扣

AK leetcode

leetcode相关题目都在下面了，拿起武器挨个点名呗。

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

在这里插入图片描述