区块链技术博客
www.b2bchain.cn

数据结构与算法-排序(五)快速排序(Quick Sort)求职学习资料

本文介绍了数据结构与算法-排序(五)快速排序(Quick Sort)求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

摘要

快速排序和归并排序有一些相似的地方,就是在中间位置拆分成两部分,分别做处理。

这里也是用到递归思想,但是与归并排序的先拆分再排序处理的思想不同,快速排序是先处理排序,然后再拆分。

本质

每一次确定一个轴点元素,然后和序列中的其他元素比较,放在元素的左右任何位置位置,完成之后,这个轴点元素的位置就明确了。

理解这个快速应该就是去搞定一个元素的位置,不管其他元素元素位置,就少了比较处理(因为绝情,所以快吗?- 我的理解

逻辑

  1. 序列中选择一个元素,设置为轴点元素(pivot)
  2. 利用 pivot将序列分割成两个子序列
    • 把小于 pivot 的元素放在序列的左侧
    • 把大于 pivot 的元素放在序列的右侧
    • 把等于 pivot 的元素可以放在左侧或者右侧都可
  3. 将子序列继续进行如上 1 2 的操作,直到无法再进行分割为止

流程

  1. 以 0 坐标为轴点,随机获取轴点元素,和 0 位置元素更换
  2. 序列头尾元素交替和轴点元素比较和调整替换,将小于轴点元素放在轴点坐标左侧,大于轴点元素放在轴点坐标右侧。
  3. 以轴点元素为中线,分割成两个子序列,继续 1 2 操作(递归性质)
  4. 直到首尾坐标相等(即序列中只有一个元素)为止

实现

将序列分为子序列的递归方法。凡是递归方法,必须要有终止递归的判断条件,否则会造成死循环,需要特别注意

    /**      * 在 [begin, end) 范围内进行比较      * @param begin      * @param end      */     private void sort(int begin, int end) {         if ((end - begin) < 2) return;          int mid = pivotIndex(begin, end);         // 分割为两个子序列         sort(begin, mid);         sort(mid+1, end);     }

以轴点坐标分割线,调整序列中的的元素,并返回新的轴点坐标。当已经比较交换完成轴点坐标时,一定要将轴点元素赋值到新的轴点坐标中

这里的代码有一个巧妙的点,就是比较并交换头尾位置

这里用大循环嵌套两个小循环的方式,达到头部和尾部交替和轴点元素比较并交换位置,这个方式非常巧妙。

首先咱要明确目的,就是序列中小于轴点的元素放在它的左边,大于轴点的元素放在它的右边。在不增加额外内存空间的情况下,就可以用这样的方式去处理。

具体的逻辑可以着重看一下代码,这里说几个需要注意的点

  1. 这里的比较是首尾交替比较,用三个 while 循环达到这样的目的
  2. begin 和 end 就相当于两个指针,通过交换之后就变换比较的方向,这一点非常巧妙。

“`java
/**
* 在 [begin, end) 返回内构造轴点坐标
* @param begin

摘要

快速排序和归并排序有一些相似的地方,就是在中间位置拆分成两部分,分别做处理。

这里也是用到递归思想,但是与归并排序的先拆分再排序处理的思想不同,快速排序是先处理排序,然后再拆分。

本质

每一次确定一个轴点元素,然后和序列中的其他元素比较,放在元素的左右任何位置位置,完成之后,这个轴点元素的位置就明确了。

理解这个快速应该就是去搞定一个元素的位置,不管其他元素元素位置,就少了比较处理(因为绝情,所以快吗?- 我的理解

逻辑

  1. 序列中选择一个元素,设置为轴点元素(pivot)
  2. 利用 pivot将序列分割成两个子序列
    • 把小于 pivot 的元素放在序列的左侧
    • 把大于 pivot 的元素放在序列的右侧
    • 把等于 pivot 的元素可以放在左侧或者右侧都可
  3. 将子序列继续进行如上 1 2 的操作,直到无法再进行分割为止

流程

  1. 以 0 坐标为轴点,随机获取轴点元素,和 0 位置元素更换
  2. 序列头尾元素交替和轴点元素比较和调整替换,将小于轴点元素放在轴点坐标左侧,大于轴点元素放在轴点坐标右侧。
  3. 以轴点元素为中线,分割成两个子序列,继续 1 2 操作(递归性质)
  4. 直到首尾坐标相等(即序列中只有一个元素)为止

实现

将序列分为子序列的递归方法。凡是递归方法,必须要有终止递归的判断条件,否则会造成死循环,需要特别注意

    /**      * 在 [begin, end) 范围内进行比较      * @param begin      * @param end      */     private void sort(int begin, int end) {         if ((end - begin) < 2) return;          int mid = pivotIndex(begin, end);         // 分割为两个子序列         sort(begin, mid);         sort(mid+1, end);     }

以轴点坐标分割线,调整序列中的的元素,并返回新的轴点坐标。当已经比较交换完成轴点坐标时,一定要将轴点元素赋值到新的轴点坐标中

这里的代码有一个巧妙的点,就是比较并交换头尾位置

这里用大循环嵌套两个小循环的方式,达到头部和尾部交替和轴点元素比较并交换位置,这个方式非常巧妙。

首先咱要明确目的,就是序列中小于轴点的元素放在它的左边,大于轴点的元素放在它的右边。在不增加额外内存空间的情况下,就可以用这样的方式去处理。

具体的逻辑可以着重看一下代码,这里说几个需要注意的点

  1. 这里的比较是首尾交替比较,用三个 while 循环达到这样的目的
  2. begin 和 end 就相当于两个指针,通过交换之后就变换比较的方向,这一点非常巧妙。

“`java
/**
* 在 [begin, end) 返回内构造轴点坐标
* @param begin

摘要

快速排序和归并排序有一些相似的地方,就是在中间位置拆分成两部分,分别做处理。

这里也是用到递归思想,但是与归并排序的先拆分再排序处理的思想不同,快速排序是先处理排序,然后再拆分。

本质

每一次确定一个轴点元素,然后和序列中的其他元素比较,放在元素的左右任何位置位置,完成之后,这个轴点元素的位置就明确了。

理解这个快速应该就是去搞定一个元素的位置,不管其他元素元素位置,就少了比较处理(因为绝情,所以快吗?- 我的理解

逻辑

  1. 序列中选择一个元素,设置为轴点元素(pivot)
  2. 利用 pivot将序列分割成两个子序列
    • 把小于 pivot 的元素放在序列的左侧
    • 把大于 pivot 的元素放在序列的右侧
    • 把等于 pivot 的元素可以放在左侧或者右侧都可
  3. 将子序列继续进行如上 1 2 的操作,直到无法再进行分割为止

流程

  1. 以 0 坐标为轴点,随机获取轴点元素,和 0 位置元素更换
  2. 序列头尾元素交替和轴点元素比较和调整替换,将小于轴点元素放在轴点坐标左侧,大于轴点元素放在轴点坐标右侧。
  3. 以轴点元素为中线,分割成两个子序列,继续 1 2 操作(递归性质)
  4. 直到首尾坐标相等(即序列中只有一个元素)为止

实现

将序列分为子序列的递归方法。凡是递归方法,必须要有终止递归的判断条件,否则会造成死循环,需要特别注意

    /**      * 在 [begin, end) 范围内进行比较      * @param begin      * @param end      */     private void sort(int begin, int end) {         if ((end - begin) < 2) return;          int mid = pivotIndex(begin, end);         // 分割为两个子序列         sort(begin, mid);         sort(mid+1, end);     }

以轴点坐标分割线,调整序列中的的元素,并返回新的轴点坐标。当已经比较交换完成轴点坐标时,一定要将轴点元素赋值到新的轴点坐标中

这里的代码有一个巧妙的点,就是比较并交换头尾位置

这里用大循环嵌套两个小循环的方式,达到头部和尾部交替和轴点元素比较并交换位置,这个方式非常巧妙。

首先咱要明确目的,就是序列中小于轴点的元素放在它的左边,大于轴点的元素放在它的右边。在不增加额外内存空间的情况下,就可以用这样的方式去处理。

具体的逻辑可以着重看一下代码,这里说几个需要注意的点

  1. 这里的比较是首尾交替比较,用三个 while 循环达到这样的目的
  2. begin 和 end 就相当于两个指针,通过交换之后就变换比较的方向,这一点非常巧妙。

“`java
/**
* 在 [begin, end) 返回内构造轴点坐标
* @param begin

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 数据结构与算法-排序(五)快速排序(Quick Sort)求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们