快速排序的相关算法题(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/51299994

快速排序的相关算法题(java)

关于二分查找的,可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)

关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java)

转载请注明原博客地址:

源码下载地址:

最近在做各个大公司的笔试题 ,比如阿里,腾讯,cvte等等,经常会遇到关于快速排序的各种算法题,包括时间复杂度,空间复杂度的分析与计算等等,于是本人查阅了相关的资料,先总结如下

本篇博客主要讲解一下三点

  1. 快排是怎样实现的?
  2. 怎样用最快的速度找出数组中出现次数超过一半的数字
  3. 要求找出数组中最小的第k个数,时间复杂度最低

快排是怎样实现的?

举例说明一下吧,这个可能不是太好理解。假设要排序的序列为  2 2 4 9 3 6 7 1 5 1. 首先用2当作基准,使用i,j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。

  1. 首先比较2和5,5比2大,j左移 2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置,即 2 1 4 9 3 6 7 1 5 ;
  2. 接着比较2和4,4大于2,因此将4移动到后面。即2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变
  3. 4.经过第一轮的快速排序,元素变为下面的样子

[1] 2 [4 9 3 6 7 5]

之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。

下面我们来看一下源码是怎样实现的

1. 简单来说就是先找出一个索引,左边的数都比他小,右边的数都比他大 ,接着利用递归排列左边和右边的数,知道low>=high

private static void qSort(int[] data, int low, int high) {
    int pivot;
    if (low < high) {
        pivot = partition(data, low, high);
        qSort(data, 0, pivot - 1);
        qSort(data, pivot + 1, high);
    }
}

2. 下面我们来看一下partition函数式怎样实现的

  1. private static int partition(int[] data, int low, int high) {
  2. int pivotKey;
  3. pivotKey = data[low];
  4. // 将大于基准点的值得数放到后面
  5. while (low < high) {
  6. while (low < high && data[high] >= pivotKey) {//
  7. high--;
  8. }
  9. ArrayUtils.exchangeElements(data, low, high);
  10. // 将小于基准点的值得数放到前面
  11. while (low < high && data[low] <= pivotKey) {
  12. low++;
  13. }
  14. ArrayUtils.exchangeElements(data, low, high);
  15. }
  16. // 返回基准点的索引
  17. return low;
  18. }

到此快速排序的分析为止


2)数组中第K个 最小的数字

一、问题描述

给定一个数组,数组中的数据无序,在一个数组中找出其第k个最小的数,例如对于数组x,x = {3,2,1,4,5,6},则其第2个最小的数为2。

二、解题思路

本算法跟快排的思想相似,首先在数组中选取一个数centre作为枢纽,将比centre小的数,放到centre的前面将比centre大的数,放到centre的后面。如果此时centre的位置刚好为k,则centre为第k个最小的数;如果此时centre的位置比k前,则第k个最小数一定在centre后面,递归地在其右边寻找;如果此时centre的位置比k后,则第k个最小数一定在centre后面,递归地在其左边寻找。

三、代码

  1. package com.xujun.quicksort;
  2. import java.util.Collections;
  3. public class MinIndex {
  4. static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5, 20, -1 };
  5. public static void main(String[] args) {
  6. System.out.println("before sort");
  7. ArrayUtils.printArray(a);
  8. int k=8;
  9. int pivot = findMinIndexInArray(a, k);
  10. System.out.println("after sort");
  11. ArrayUtils.printArray(a);
  12. System.out.println("数组中最小的第"+k+"个数是 " + a[pivot]);
  13. }
  14. private static int findMinIndexInArray(int[] data, int k) {
  15. if (data == null || data.length < k) {
  16. return -1;
  17. }
  18. int start = 0;
  19. int end = data.length - 1;
  20. int pivot = partition(data, start, end);
  21. while (pivot != k - 1) {
  22. if (pivot < k - 1) {
  23. start = pivot + 1;
  24. pivot = partition(data, start, end);
  25. } else {
  26. end = pivot - 1;
  27. pivot = partition(data, start, end);
  28. }
  29. }
  30. return pivot;
  31. }
  32. private static int partition(int[] data, int low, int high) {
  33. int pivotKey;
  34. /*
  35. * pivotKey = data[low];// 选取low作为基准点,pivotKey为基准点的值
  36. */
  37. int middle = low + (high - low) / 2;
  38. if (data[low] > data[high]) {// 较大的数存在high中
  39. ArrayUtils.exchangeElements(data, low, high);
  40. }
  41. if (data[middle] > data[high]) {
  42. ArrayUtils.exchangeElements(data, middle, high);
  43. }
  44. if (data[middle] > data[low]) {
  45. ArrayUtils.exchangeElements(data, middle, low);
  46. }
  47. pivotKey = data[low];// 选取low作为基准点,pivotKey为基准点的值
  48. // 将大于基准点的值得数放到后面
  49. while (low < high) {
  50. while (low < high && data[high] >= pivotKey) {//
  51. high--;
  52. }
  53. data[low] = data[high];
  54. // 将小于基准点的值得数放到前面
  55. while (low < high && data[low] <= pivotKey) {
  56. low++;
  57. }
  58. data[high] = data[low];
  59. }
  60. data[low] = pivotKey;
  61. // 返回基准点的索引
  62. return low;
  63. }
  64. }

3)数组中出现次数超过一半的数字

一、问题描述

给定一个数组,找出数组中元素出现次数超过数组长度一半的元素  如数组:  [4, 3, 2, 1, 1, 1, 1, 1, 1, 0 ]  其中超过一半的元素就是 1

二、解题思路

1)本题同样可以医用快速排序的思想来做,如果一个数字出现次数超过一般,那么排好序的数组的中间数肯定就是出现次数超过一半的数字  2)考虑异常情况下,出现次数没有超过一半  遍历数组,检查一下

三、代码

  1. package com.xujun.quicksort;
  2. import java.util.Collections;
  3. public class MoreThanHalf {
  4. static int[] a = new int[] { 20, 9, 3, 5, 10,10,10,10,10 };
  5. public static void main(String[] args) {
  6. System.out.println("before sort");
  7. ArrayUtils.printArray(a);
  8. int k = 8;
  9. int pivot = findMoreHalfInArray(a);
  10. int target = a[pivot];
  11. boolean checkIsMoreThanHalf = checkIsMoreThanHalf(a, target);
  12. if(checkIsMoreThanHalf){
  13. System.out.println("after sort");
  14. ArrayUtils.printArray(a);
  15. System.out.println("超过一般的数是="+target);
  16. }else{
  17. System.out.println("没有超过一般的数字");
  18. }
  19. }
  20. private static boolean checkIsMoreThanHalf(int[] data, int target) {
  21. int half=data.length/2;
  22. int count=0;
  23. for(int i=0;i<data.length;i++){
  24. if(data[i]==target){
  25. count++;
  26. }
  27. }
  28. return count>=half?true:false;
  29. }
  30. private static int findMoreHalfInArray(int[] data) {
  31. if (data == null || data.length <= 0) {
  32. return -1;
  33. }
  34. int start = 0;
  35. int end = data.length - 1;
  36. int half = data.length / 2;
  37. int pivot = partition(data, start, end);
  38. while (pivot != half - 1) {
  39. if (pivot < half - 1) {// 枢轴在一半的 左边
  40. start = pivot + 1;
  41. pivot = partition(data, start, end);
  42. } else {// 枢轴在一半(中间点)的右边
  43. end = half - 1;
  44. pivot = partition(data, start, end);
  45. }
  46. }
  47. return pivot;
  48. }
  49. private static int partition(int[] data, int low, int high) {
  50. int pivotKey;
  51. /*
  52. * pivotKey = data[low];// 选取low作为基准点,pivotKey为基准点的值
  53. */
  54. int middle = low + (high - low) / 2;
  55. if (data[low] > data[high]) {// 较大的数存在high中
  56. ArrayUtils.exchangeElements(data, low, high);
  57. }
  58. if (data[middle] > data[high]) {
  59. ArrayUtils.exchangeElements(data, middle, high);
  60. }
  61. if (data[middle] > data[low]) {
  62. ArrayUtils.exchangeElements(data, middle, low);
  63. }
  64. pivotKey = data[low];// 选取low作为基准点,pivotKey为基准点的值
  65. // 将大于基准点的值得数放到后面
  66. while (low < high) {
  67. while (low < high && data[high] >= pivotKey) {//
  68. high--;
  69. }
  70. data[low] = data[high];
  71. // 将小于基准点的值得数放到前面
  72. while (low < high && data[low] <= pivotKey) {
  73. low++;
  74. }
  75. data[high] = data[low];
  76. }
  77. data[low] = pivotKey;
  78. // 返回基准点的索引
  79. return low;
  80. }
  81. }

关于二分查找的,可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)

关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java)

转载请注明原博客地址:

源码下载地址:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

R语言学习笔记——R语言面向对象编程系列2

最近在看任坤大神的新作——《R语言编程指南》,其中对于编程语言中非常流行的面向对象编程范式(OOP)在R语言中的实现进行了非常详尽的讲解,强烈推荐各位有志于进阶...

362120
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

15710
来自专栏云飞学编程

python学习,数据分析系列工具,初识numpy

其实,数据分析看着很高大上,也很实用,但是真的很枯燥啊。。。。但是它又不得不学,毕竟数据分析对很多工作是很有帮助的,比如爬虫,抓到的数据,不论是保存到文件还是数...

9520
来自专栏猿人谷

oc 中随机数的用法(arc4random() 、random()、CCRANDOM_0_1()

1)、arc4random() 比较精确不需要生成随即种子        使用方法 :                  通过arc4random() 获取0到...

25980
来自专栏Linyb极客之路

UML类图(下):关联、聚合、组合、依赖

关联(Assocition)关系是类与类之间最常见的一种关系,它是一种结构化的关系,表示一类对象与另一类对象之间有联系,如汽车和轮胎、师傅和徒弟、班级和学生等。...

17120
来自专栏牛客网

头条实习面经

【每日一语】真实人生中,我们往往在大势底定无可更改时才迟迟进场,却又在胜败未分的浑沌中提早离席。——翁贝托·埃科《开头与结尾》

13920
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K50
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

13010
来自专栏ATYUN订阅号

PyTorch 4.0版本迁移指南

欢迎阅读PyTorch 0.4.0的迁移指南。在此版本中,我们引入了许多振奋人心的新功能和重要的bug修复,旨在为用户提供更好,更清晰的接口。在这个指南中,我们...

18020
来自专栏机器之心

教程 | 简单实用的pandas技巧:如何将内存占用降低90%

选自DATAQUEST 作者:Josh Devlin 机器之心编译 参与:Panda pandas 是一个 Python 软件库,可用于数据操作和分析。数据科学...

865100

扫码关注云+社区

领取腾讯云代金券