Notes by Louisa
Notes by Louisa
Notes by Louisa
  • Introduction
  • Chapter1 Python Cheatsheet
    • Reference, Deep Copy and Shallow Copy
    • Iterators
    • List Comprehensions
    • Numpy
    • Pandas
    • Data Visualization
    • DateTime
    • Python Good to knows
  • Chapter2 Java Cheatsheet
    • Fundamentals to Java
    • Interface, Abstract Class, Access Modifier, Exceptions
    • Linked List and Java List
    • Java Queue, Stack and Deque
    • Binary Tree
    • Heap in Java
    • Map/Set/Hash
    • OOD
  • Chapter3 Algorithm
    • Fundamental Knowledge
    • Binary Search
    • Basic Sorting
    • Advanced Sorting
    • Linked List
    • Recursion 1
    • HashTable
    • Queue
    • Sliding Window
    • Stack
    • Binary Tree
    • Binary Search Tree
    • Heap
    • String
    • Graph Search DFS1 (Back Tracking)
    • Recursion II and Memoization
    • Dynamic Programming
    • Complete Binary Tree, Segment Tree, Trie Tree
    • Graph Search BFS
    • Graph Search BFS 2
    • Graph Search DFS2
    • Problems from 'JianZhi Offer'
    • Problems Categorized
    • Bit Operations
  • Chapter4 Model
    • Linear Regression
    • Logistic Regression
    • Regularization and Feature Selection
    • Model Evaluation
    • Nonlinear Models
    • PCA
    • Unsupervised Learning
    • Gradient Descent and Gradient Boosting
    • XG Boost and Light GBD
    • Deep Learning
    • Tensorflow/Keras
    • RNN
  • Chapter5 Statistics and A/B Testing
    • Inference about independence
    • Probability, Sampling and Randomization with Python
    • A/B Testing
    • Stats Interview Review
    • Statistics Glossary
  • Chapter6 SQL
    • Student Scores Query
    • Order Query
    • Movie Rating Query
    • Social-Network Query
    • LeetCode SQL题目总结
    • Spark SQL
  • Chapter7 Big Data and Spark
    • Introduction to Pyspark
    • Data Cleaning with Apache Spark
    • Feature Engineering with Pyspark
    • Building Recommendation Engines with Pyspark
    • Building Data Engineering Pipelines in Python
    • Hadoop MapReduce
    • Big Data Related Paper
  • Chapter8 Code Walk-Throughs
    • Python
    • R
    • Shell
  • Chapter9 Special Topics
    • Anomaly Detection
    • E Commerce
    • Supply Chain
    • Social Network Analysis
    • NLP intro
    • Time Series
    • Challenge Prophet with LSTM models
  • Project: The Winning Recipes to an Oscar Award
  • Project: A Crime Analysis of the Last Decade NYC
  • Project: Predict User Type Based on Citibike Data
  • GeoSpark/GeoSparkVis for Geospatial Big Data
  • Single Scattering Albedo
  • Sea Ice Albedo Retrievals
  • Lidar Project
Powered by GitBook
On this page
  • Bubble Sort 冒泡排序
  • Selection Sort 选择排序
  • 3 stacks 实现选择排序 无重复
  • 3 stacks 实现选择排序 有重复
  • 2 stacks 实现选择排序
  • Insertion Sort 插入排序
  • 方法一:
  • 方法二:
  • 方法三:
  1. Chapter3 Algorithm

Basic Sorting

冒泡、选择、插入

PreviousBinary SearchNextAdvanced Sorting

Last updated 4 years ago

Bubble Sort 冒泡排序

For each pass, we will move left to right swapping adjacent elements as needed. Each pass moves the next largest element into its final position.

以下是它的visualization

简单说,内外两个循环,外循环控制这是第几轮交换(1轮让max在最后,2轮让second largest在倒数第二...),内循环控制相邻位置的交换。

def bubble_sort (list):
    for n in range (len(list)-1,0,-1):
        for i in range(n):
            if (list[i]>list[i+1]):
                list[i],list[i+1]=list[i+1],list[i]
    return list
def bubble_sort (list):
    for n in range(0,len(list)):
        for i in range (len(list)-n-1):
            if (list[i]>list[i+1]):
                list[i],list[i+1]=list[i+1],list[i]
    return list

Space O(1) (in place)

Time O( n2n^{2}n2 )

Selection Sort 选择排序

n个元素,做n轮,每轮选出剩余元素最小值,归位。 For each pass, we will move from left to right looking for the next largest(smallest) value. Once that is found, it will be swapped into its final position.

以下是它的visualization

先要解决的子问题:找到一个array中最小的数

def find_min(array):
    min_value = array[0]
    for i in range (len(array)):
        if array[i]<min_value:
            min_value=array[i]
    return min_value

然后推广到每一层

class Solution(object):
  def solve(self, array):
    """
    input: int[] array
    return: int[]
    """
    # write your solution here
    if not array or len(array)==0:
      return array

    for i in range (0, len(array)): #也可range(len(array))
      minIdx=i
      for j in range(i, len(array)): #也可i+1
        if array[j]<array[minIdx]:
          minIdx=j
      array[i], array[minIdx] = array[minIdx], array[i]
    
    return array
def selection_sort (array):
    for i in range(len(array)-1,0,-1):
        max_index = 0
        for j in range(i+1):
            if array[max_index]<array[j]:
                max_index=j
        array[i], array[max_index] = array[max_index], array[i]

Space O(1) (in place)

Time O( n2n^{2}n2 )

3 stacks 实现选择排序 无重复

stack1(store input)

stack2(buffer) global min=

stack3(store output)

Time O( n2n^{2}n2 )

3 stacks 实现选择排序 有重复

2 stacks 实现选择排序

Insertion Sort 插入排序

Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.

It iterates the input elements by growing the sorted array at each iteration. It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position. This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.

先要解决的子问题:如何在数组中插入一个数,让它能在correct position。

def insert_num(array, n):
    idx=len(array)-1
    array.append(n)
    while idx>=0:
            if array[idx]>array[idx+1]:
                array[idx],array[idx+1]=array[idx+1],array[idx]
            idx-=1
    return array

方法一:

调用insert_num这个help function,实现insertion sort

方法一 O(N)的空间消耗
def insert_sort(array):
    new_array=[]
    for i in range (len(array)):
        insert_num(new_array, array[i])
    return new_array

Space O(n) 在line2中建立了一个空数组,往空数组里加元素,多占了n

Time O( n2n^{2}n2 )

所以这不是最优解

方法二:

像轮回洗牌似的操作, in place地进行插入排序。这个程序看起来会比上面的更简单,但是tricky的是要提前想明白所定义变量的物理意义。i之前的元素是已经排序好的,k是用来在内层循环中一个个往前找到cur应该处的位置的,在找的同时把元素一个个换过去,最后cur是现在需要排序的对象。

def insert_sort (array):
    for i in range (len(array)):
        cur = array[i]
        k = i
        while k>0 and cur<array[k-1]:
                array[k]=array[k+1]
                k-=1
         array[k]=cur   
for i in range (len(array)):
      smallest = i
      for j in range (i+1,len(array)):
        if (array[j]<array[smallest]):
          smallest=j
      array[i],array[smallest]=array[smallest],array[i]
    return array

Space O(1) (in place)

Time O( n2n^{2}n2 )

方法三:

也可以直接去优化方法一,因为binary search可以简化找位置的操作,让时间复杂度缩减到 O(log(n))O(log(n))O(log(n)) , 交换的操作是 O(n)O(n)O(n), 最后总的时间复杂度依然是O(log(n)+n)∗n=O(n2)O(log(n)+n)*n=O(n^{2})O(log(n)+n)∗n=O(n2)

这个有点问题 但我还不知道啥问题= =
def insert_num (array, n):
  idx=len(array)-1
  array.append(n)
  if idx<0:
    return n
  else:
    insert_place=binary_search(array, n) 
    for i in range(insert_place+1, idx):
     array[i+1]=array[i]
    array[insert_place]=n
    return array
    
def binary_search (nums, target):
  left=0
  right=len(nums)-1
  while left<right-1:
      mid=(left+right)/2
      if nums[mid]>target:
        right=mid
      elif nums[mid]<target:
        left=mid
      else:
        return mid
  return left 

array = [5,3,2,1]
new_array=[]
for i in range (len(array)):
  insert_num (new_array, array[i])

print new_array

https://www.hackerearth.com/zh/practice/algorithms/sorting/insertion-sort/visualize/www.hackerearth.com
https://www.hackerearth.com/zh/practice/algorithms/sorting/bubble-sort/visualize/www.hackerearth.com
https://www.hackerearth.com/zh/practice/algorithms/sorting/selection-sort/visualize/www.hackerearth.com