快速排序

Word count: 470Reading time: 1 min

 2021/09/03 

题目是要找出数组中最小的k个数，那么肯定要涉及到排序。

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

很显然，这题只需要排序就行了，考察的就是八大排序算法。（除非你直接调sort(),当然这是面试官见打）
快排的思路为：将某一个元素作为枢纽，最简单的就是将第一个元素作为枢纽，然后通过一次划分算法，将数组划分为由枢纽隔开的两个子数组，枢纽左边的元素全部小于（或大于）枢纽，枢纽右边的元素全大于（或小于）枢纽，并通过递归对每个子数组进行快排。

划分的思路为：从右往左找到第一个小于枢纽的元素，并与枢纽交换，从左往右找到第一个大于枢纽的元素，并与枢纽交换。也就是要运用双指针

以下为代码

func quickSort(_ arr: [Int], _ l : Int, _ r : Int) -> [Int] {
        var num = arr
        if l < r {
            var i = l
            var j = r
            var x = num[i] 
            while (i < j) {
                while (i < j && num[j] >= x) { // 从右向左找到第一个比枢纽小的
                    j -= 1
                }
                if i < j {
                    num[i] = num[j]
                    //num.swapAt(i,j)
                    i += 1
                }

                while (i < j && num[i] < x) { // 从左向右找到第一个比枢纽大的
                    i += 1
                }
                if i < j {
                    //num.swapAt(i,j)
                    num[j] = num[i]
                    j -= 1
                }
            }
            num[i] = x
            num = quickSort(num,l,i-1)
            num = quickSort(num,i+1,r)
        }
        return num
    }

总结

八大排序算法是比较重要的知识点，需要多学习并且用语言实现出来，还要知道优化思路。

Next Post

一道经典的BFS
Previous Post

三数之和

CATALOG

1. 总结