Merge sort

Leave a comment

July 3, 2017 by oneOokay

merge sort 是一个divide and conquer. 记不住什么是merge sort大概是因为merge sort的名字里面少了divide…

merge sort:包含两部分,divide和merge.

时间复杂度是:O(nlogn)

  1. Divide: recursively divide elements into two parts:
    1. 所以这里要传入一个left和right index来标明目前要divide是原array中的哪一段
    2. divide无非就是根据传入的left和right index,求得中点mid.分成[left, mid]和[mid + 1, right]这样两端段.
    3. 这样一直一直divide到把整个array分成单个元素为止.此时的传入的left和right的值是相等的.
    4. 而且这样一直divide下来就是一个tree的形状了.这个树的depth是log N(N为array的总元素的个数);树的每一层也都有N个元素.
  2. Merge:在divide之后才进行merge,所以起始merge是merge单个元素.之后的回溯到上层的merge就是merge 两个sorted array的merge了.
    1. merge要传入三个参数:left, mid, right.
    2. 新建两个tmp array分别存[left, mid]和[mid+1, right]
    3. 在原array里面用一个指针,同时遍历两个tmp array,放到原array里面去….

其他没什么特别的了. 模板:

Advertisements
»

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

July 2017
M T W T F S S
« Jun    
 12
3456789
10111213141516
17181920212223
24252627282930
31  
%d bloggers like this: