春节7天练 | Day 3：排序和二分查找

精选留言

• 
  李皮皮皮皮皮

  2019-02-06 20:27:10

  各种排序算法真要说起来实际中使用的最多的也就是快排了。然而各种编程语言内置的标准库都包含排序算法的实现，基本没有自己动手实现的必要。然后作为经典的算法，自己实现一遍，分析分析时间空间复杂度对自己的算法设计大有裨益。需要注意的是为了高效，在实际的实现中，多种排序算法往往是组合使用的。例如c标准库中总体上是快排，但当数据量小于一定程度，会转而使用选择或插入排序。
  求平方根使用牛顿法二分逼近😄
• 
  TryTs

  2019-02-07 23:05:44

  虽然现在有很多排序算法自己不会亲自写，但是作为算法的基础，分治，归并，冒泡等排序算法在时间复杂度，空间复杂度以及原地排序这些算法知识上的理解非常有帮助。递归分治这些算法思想在简单的算法中也能体现出来，其实更多的是思维方式的训练。

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:57:24

• 
  虎虎❤️

  2019-02-07 12:50:55

  基本排序算法的关注点分为：
  1. 时间复杂度。如n的平方（冒泡，选择，插入）；插入排序的优化希尔排序，则把复杂度降低到n的3/2次方；n乘以logn(快排，归并排序，堆排序）。
  2. 是否为原地排序。如，归并排序需要额外的辅助空间。
  3. 算法的稳定性。稳定排序（by nature）如冒泡，插入，归并。如果把次序考虑在内，可以把其他的排序（如快排，堆排序）也实现为稳定排序。
  4. 算法的实现。同为时间复杂度同为n平方的算法中，插入排序的效率更高。但是如果算法实现的不好，可能会降低算法的效率，甚至让稳定的算法变得不稳定。又如，快速排序有不同的实现方式，如三路快排可以更好的应对待排序数组中有大量重复元素的情况。堆排序可以通过自上而下的递归方式实现，也可以通过自下而上的方式实现。
  5. 不同算法的特点，如对于近乎有序的数组进行排序，首选插入排序，时间复杂度近乎是n，而快速排序则退化为n平方。
  
  二分查找，需要注意 (l+r)/2可能存在越界问题。
  
  leetcode题，用二分查找找到x*x > n 且(x-1)的平方小于n的数，则n-1就是结果。或者 x的平方小于n且x+1的平方大于n,则返回x。
• 
  失火的夏天

  2019-02-06 22:55:37

  牛顿法或者二分逼近都可以解决平方根问题，leetcode上有些大神的思路真的很厉害，经常醍醐灌顶
• 
  hopeful

  2019-02-16 16:50:25

  #O(n)时间复杂度时间复杂度内找到一组数据的第 n大元素
  import random
  import time
  
  def Array(n):
  a = []
  for i in range(n):
  a.append(random.randint(0 , n))
  return a
  def QuickSort(n):
  array = Array(100)
  if n > len(array) or n < 1:
  print("超出范围，找不到")
  return
  n = n-1
  a = qsort(0 , len(array)-1 , array , n)
  print(sorted(array))
  print("-----------------------------")
  print(a)
  
  def qsort(start , end , array , n):
  if start == end:
  res = array[start]
  if start < end:
  key = partation(array , start , end)
  print(start , key , end)
  if key > n :
  res = qsort(start , key-1 , array , n)
  elif key < n:
  res = qsort(key+1 , end , array , n)
  else:
  res = array[key]
  return res
  
  def swap(array , start , end):
  temp = array[start]
  array[start] = array[end]
  array[end] = temp
  
  def partation(array , start , end):
  temp = array[start]
  while start < end :
  while start<end and array[end]<=temp:
  end-=1
  swap(array , start , end)
  while start<end and array[start]>=temp:
  start+=1
  swap(array , start , end)
  return start
• kai

  2019-02-11 10:32:10

  实现模糊二分查找算法2:
  
  public class BinarySearch {
  // 3. 查找第一个大于等于给定值的元素
  public static int bsFistGE(int[] array, int target) {
  int lo = 0;
  int hi = array.length - 1;
  
  while (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1);
  
  if (array[mid] >= target) {
  if (mid == 0 || array[mid-1] < target) {
  return mid;
  } else {
  hi = mid - 1;
  }
  } else {
  lo = mid + 1;
  }
  }
  
  return -1;
  }
  
  // 4. 查找最后一个小于等于给定值的元素
  public static int bsLastLE(int[] array, int target) {
  int lo = 0;
  int hi = array.length - 1;
  
  while (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1);
  
  if (array[mid] <= target) {
  if (mid == hi || array[mid+1] > target) {
  return mid;
  } else {
  lo = mid + 1;
  }
  } else {
  hi = mid - 1;
  }
  }
  
  return -1;
  }
  }
• 
  TryTs

  2019-02-14 11:34:27

  #include<iostream>
  #include<cmath>
  using namespace std;
  double a = 1e-6;
  double sqrt(double n){
  double low = 0.0;
  double high = n;
  
  int i = 1000;
  
  while(i--){
  double mid = low + (high - low) / 2.0;
  //cout<<"n:"<<n<<endl;
  double square = mid * mid;
  //cout<<"sq:"<<square<<endl;
  //cout<<"s:"<<abs(square - n)<<endl;
  if(abs(mid * mid - n) < a){
  return mid;
  }
  else{
  
  if(square > n){
  high = mid;
  }
  else{
  low = mid;
  }
  }
  }
  return -2.0;
  }
  int main(){
  double t;
  while(true){
  cin>>t;
  cout<<sqrt(t)<<endl;
  }
  }
• 
  Monster

  2019-02-13 18:22:35

  /**
  * O(n)时间复杂度内求无序数组中第K大元素
  */
  public class TopK {
  
  public int findTopK(int[] arr, int k) {
  return findTopK(arr, 0, arr.length - 1, k);
  }
  
  private int findTopK(int[] arr, int left, int right, int k) {
  if (arr.length < k) {
  return -1;
  }
  int pivot = partition(arr, left, right);
  if (pivot + 1 < k) {
  findTopK(arr, pivot + 1, right, k);
  } else if (pivot + 1 > k) {
  findTopK(arr, left, pivot - 1, k);
  }
  return arr[pivot];
  }
  
  
  private int partition(int[] array, int left, int right) {
  int pivotValue = array[right];
  int i = left;
  
  //小于分区点放在左边 大于分区点放在右边
  for (int j = left; j < right; j++) {
  if (array[j] < pivotValue) {
  int tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
  i++;
  }
  }
  //与分区点交换
  int tmp = array[i];
  array[i] = array[right];
  array[right] = tmp;
  return i;
  }
  }

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您10元无门槛优惠券，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 11:12:45

• 
  EidLeung

  2019-02-12 19:05:50

  编程实现 O(n) 时间复杂度内找到一组数据的第 K 大元素。
  这个的时间复杂路应该是n·logk吧？
• 
  Abner

  2019-02-11 17:44:01

  java实现冒泡排序
  代码如下：
  package sort;
  
  public class BubbleSort {
  
  public int[] bubbleSort(int[] array) {
  for (int i = 0;i < array.length - 1;i++) {
  for (int j = 0;j < array.length - i - 1;j++) {
  if (array[j] > array[j + 1]) {
  int temp = array[j + 1];
  array[j + 1] = array[j];
  array[j] = temp;
  }
  }
  }
  return array;
  }
  
  public static void main(String[] args) {
  int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  BubbleSort bubbleSort = new BubbleSort();
  int[] result = bubbleSort.bubbleSort(array);
  for (int i = 0;i < result.length;i++) {
  System.out.print(result[i] + " ");
  }
  }
  
  }
  
• kai

  2019-02-11 10:31:49

  实现模糊二分查找算法1:
  
  public class BinarySearch {
  
  // 1. 查找第一个值等于给定值的元素
  public static int bsFirst(int[] array, int target) {
  int lo = 0;
  int hi = array.length - 1;
  
  while (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1);
  
  if (array[mid] > target) {
  hi = mid - 1;
  } else if (array[mid] < target) {
  lo = mid + 1;
  } else {
  if (mid == lo || array[mid-1] != array[mid]) {
  return mid;
  } else {
  hi = mid - 1;
  }
  }
  }
  
  return -1;
  }
  
  // 2. 查找最后一个值等于给定值的元素
  public static int bsLast(int[] array, int target) {
  int lo = 0;
  int hi = array.length - 1;
  
  while (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1);
  
  if (array[mid] > target) {
  hi = mid - 1;
  } else if (array[mid] < target) {
  lo = mid + 1;
  } else {
  if (mid == hi || array[mid] != array[mid+1]) {
  return mid;
  } else {
  lo = mid + 1;
  }
  }
  }
  
  return -1;
  }
  }
• kai

  2019-02-11 10:29:16

  实现一个有序数组的二分查找算法:
  
  public class BinarySearch {
  // 最简单的二分查找算法：针对有序无重复元素数组
  // 迭代
  public static int binarySearch(int[] array, int target) {
  if (array == null) return -1;
  
  int lo = 0;
  int hi = array.length-1; // 始终在[lo, hi]范围内查找target
  
  while (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1); // 这里若是 (lo + hi) / 2 有可能造成整型溢出
  
  if (array[mid] > target) {
  hi = mid - 1;
  } else if (array[mid] < target) {
  lo = mid + 1;
  } else {
  return mid;
  }
  }
  
  return -1;
  }
  
  // 递归
  public static int binarySearchRecur(int[] array, int target) {
  if (array == null) return -1;
  return bs(array, target, 0, array.length-1);
  }
  
  private static int bs(int[] array, int target, int lo, int hi) {
  if (lo <= hi) {
  int mid = lo + ((hi - lo) >> 1);
  if (array[mid] > target) {
  return bs(array, target, lo, mid-1);
  } else if (array[mid] < target) {
  return bs(array, target, mid+1, hi);
  } else {
  return mid;
  }
  }
  
  return -1;
  }
  }
• 
  纯洁的憎恶

  2019-02-09 17:00:15

  这道题似乎可以等价于从1到x中找到一个数y，使得y*y小于等于x，且（y+1）*（y+1）大于x。那么可以从1到x逐个尝试，提高效率可以采用二分查找方法，时间复杂度为O（logx）。
• 
  黄丹

  2019-02-07 18:35:30

  王争老师初三快乐！
  这是今天两道题的解题思路和代码
  1. O(n)时间内找到第K大的元素：
  解题思路：利用快排中分区的思想，选择数组区间A[0...n-1]的左右一个元素A[n-1]作为pivot，对数组A[0...n-1]原地分区，这样数组就分成了三部分，A[0..p-1],A[p],A[p+1...n-1],如果p+1=k,那么A[p]就是要求解的元素，如果K>p+1,则说明第K大的元素在A[p+1...n-1]这个区间，否则在A[0...p-1]这个区间，递归的查找第K大的元素
  2. Sqrt(x) （x 的平方根）
  解题思路：利用二分查找的思想，从1到x查找x的近似平方根
  代码：
  https://github.com/yyxd/leetcode/blob/master/src/leetcode/sort/Problem69_Sqrt.java
• 
  C_love

  2019-02-07 13:00:33

  Use Binary Search
  
  class Solution {
  public int mySqrt(int x) {
  if (x == 0 || x == 1) {
  return x;
  }
  
  int start = 0;
  int end = (x >> 1) + 1;
  
  while (start + 1 < end) {
  final int mid = start + ((end - start) >> 1);
  final int quotient = x / mid;
  if (quotient == mid) {
  return mid;
  } else if (quotient < mid) {
  end = mid;
  } else {
  start = mid;
  }
  }
  
  return start;
  }
  }

  作者回复

  感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

  2019-02-22 10:54:13

• 
  杨建斌(young)

  2023-06-29 15:44:47

  public static void main(String[] args) {
  
  int x = 243432;
  if (x < 4) {
  System.out.println(1);
  }
  if (x < 9) {
  System.out.println(2);
  }
  if (x < 16) {
  System.out.println(3);
  }
  if (x < 25) {
  System.out.println(4);
  }
  int end = x / 2;
  int start = 1;
  while (start + 1 < end) {
  int value = (end + start) / 2;
  if (value * value > x || value * value < 0) {//-0 溢出
  end = value;
  } else {
  start = value;
  }
  
  }
  System.out.println(start);
  
  }
• Geek_86533a

  2019-08-14 10:22:40

  不断学习，不断练习到今天。发现自己的代码能力、思考问题的能力有了明显的进步。感谢！
• 
  懒猫

  2019-05-23 10:03:35

  打卡
• 
  hopeful

  2019-02-17 00:56:06

  #二分查找变种
  import random
  import time
  
  def Array(n):
  a = []
  for i in range(n):
  a.append(random.randint(0 , n))
  return a
  #查找第一个值等于给定值的元素
  def find_1(n):
  array = Array(100)
  array = sorted(array)
  left = 0
  right = len(array)-1
  while left <= right:
  mid = int((left+right)/2)
  if array[mid] > n:
  right = mid - 1
  elif array[mid] < n:
  left = mid + 1
  else:
  if mid==0 or array[mid] != array[mid-1]:
  return mid
  else:
  right = mid - 1
  print("找不到")
  return -1
  
  #查找最后一个值等于给定值的元素
  def find_2(n):
  array = Array(100)
  array = sorted(array)
  left = 0
  right = len(array)-1
  while left <= right:
  mid = int((left+right)/2)
  if array[mid] > n:
  right = mid - 1
  elif array[mid] < n:
  left = mid + 1
  else:
  if mid==right or array[mid] != array[mid+1]:
  return mid
  else:
  left = mid + 1
  print("找不到")
  return -1
  
  #查找第一个值大于等于给定值的元素
  def find_3(n):
  array = Array(100)
  array = sorted(array)
  left = 0
  right = len(array)-1
  while left <= right:
  mid = int((left+right)/2)
  if array[mid] >= n:
  if mid==0 or array[mid-1]<n:
  return mid
  else:
  right = mid - 1
  else array[mid] < n:
  left = mid + 1
  print("找不到")
  return -1
  
  #查找最后一个值小于等于给定值的元素
  def find_4(n):
  array = Array(100)
  array = sorted(array)
  left = 0
  right = len(array)-1
  while left <= right:
  mid = int((left+right)/2)
  if array[mid] <= n:
  if mid==right or array[mid+1]>n:
  return mid
  else:
  left = mid + 1
  else array[mid] > n:
  right = mid - 1
  print("找不到")
  return -1
• 
  hopeful

  2019-02-16 15:58:43

  #实现一个有序数组的二分查找算法
  import random
  import time
  
  def Array(n):
  a = []
  for i in range(n):
  a.append(random.randint(0 , n))
  return a
  
  def find(n):
  array = Array(100)
  array = sorted(array)
  left = 0
  right = len(array)-1
  while left <= right:
  mid = int((left+right)/2)
  if array[mid] > n:
  right = mid - 1
  elif array[mid] < n:
  left = mid + 1
  else:
  return mid
  print("找不到")
  return -1