好程序员python学习路线分享实现快速排序算法 - 编程思维

  好程序员Python学习路线分享实现快速排序算法快速排序算法是一种基于交换的高效的排序算法,由C.R.A.Hoare于1962年提出,是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide and conquer algorithm)。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

  • 先找到一个基准点(一般指数组的中部),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。
  • 左右分别用一个空数组去存储比较后的数据。
  • 最后递归执行上述操作,直到数组长度 <= 1;

代码实现


def quick_sort(lists, left, right):

    '''快速排序'''

    # 跳出递归判断

    if left >= right:

        return lists

 

    # 选择参考点,该调整范围的第1个值

    key = lists[left]

    low = left  

    high = right

 

    # 循环判断直到遍历全部

    while left < right:

        # 从右边开始查找大于参考点的值

        while left < right and lists[right] >= key:

            right -= 1

        lists[left] = lists[right]  # 这个位置的值先挪到左边

 

        # 从左边开始查找小于参考点的值

        while left < right and lists[left] <= key:

            left += 1

        lists[right] = lists[left]  # 这个位置的值挪到右边

 

    # 写回改成的值

    lists[left] = key

 

    # 递归,并返回结果

    quick_sort(lists, low, left - 1)    # 递归左边部分

    quick_sort(lists, left + 1, high)   # 递归右边部分

    return lists

 

numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5]

quick_sort(numbers,0,len(numbers)-1)

assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://segmentfault.com/a/1190000020348778

合并二叉树(python3) - 编程思维

题目要求:给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。 解决思想:遇到二叉树,首先想到的是递归实现。为了降低空间消耗,两个

汉明距离(python3) - 编程思维

问题提出:两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离。注意:0 ≤ x, y < 2^31。 解题思路:对两数进行二进制求解(使用递归算法),然后从两个二进制的末尾比较每一位是否相等,如果其中一个二进制数全部遍历,判断另一个二进制数是否遍历

翻转二叉树(python3) - 编程思维

提出问题:翻转一棵二叉树。(除根结点以外)原始二叉树: 新二叉树: 解题思路:遇见二叉树先想到递归。从最下层的叶子结点开始置换左右子节点,一直置换到到最上层的根结点的左右节点为止。 代码如下( ̄▽ ̄): # Definition for a binary tree node. # class TreeNode: #

来谈谈贪心算法 - 编程思维

前言 之前讲了动态规划,在翻阅资料的时候看到了不少谈论贪心算法的,这两种算法也很有相似之处,正好最近又做到了有关贪心的题,所以今天写篇文章来谈一谈。 贪心算法(英语:greedy algorithm),又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。

滑动窗口算法 - 编程思维

参考文章:leetcode438题解答 0x00:前言 leetcode上有好几道个子字符串有关的题目,两天前看到一题要求找到字符串中所有字母异位词,题目大致意思是有s和p两个字符串,找出s中和p字母相同但顺序可以不相同的子字符串,并返回这些子串的起始索引。 例子:输入:s: "cbaebabacd" p: "abc

leetcode 1:两数之和 - 编程思维

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + n

像sql中的order语句来对数组排序 - 编程思维

经常遇到这样的场景,要根据不同字段的排序条件,输出符合要求的列表信息。经常我们把排序的逻辑写在sql语句中。如今,我有需要去验证数据的排序是否符合要求,所以要通过给你的数据,去验证它的排序逻辑。单个字段的排序还好,如果是多个字段,就会麻烦一些。晚上的思路比较活跃。果果和果妈已熟睡。代码如下,可以像sql一样的order

python自学日记9——选择数据结构 - 编程思维

1.编写一个程序从文件中读入一个单词列表,并打印出所有是回文的单词集合 这次的回文和以前理解的回文不一样,例子如下: ['deltas','desalt','lasted','salted','slated','staled'] ['retainers','ternaries'] 只要都是相同字母组成的单词都算在回文的

八大排序算法使用python实现 - 编程思维

一、冒泡排序 冒泡排序算法的运作如下: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。以上节选自维基百

记一次xx前端面试 - 编程思维

前因,没有比摸鱼有趣的事了 距离自己被外派(俗称外包)出去,已经过了快五个月,工作的话,很闲。人啊,一定保持好的习惯,懒惰是会上瘾,日常摸鱼,怀疑人生,我是谁,我在哪,我要干什么。 中午吃饭的时候,收到了boss直聘的一条消息,XX发来一个信息,是一个前端职位,问我是否感兴趣,讲道理,我还是很诧异的,一是我BOSS直聘