layout: post
title: "基础算法(1)"
category:
tags: ["读文章", "算法"]
{% include JB/setup %}
Linear search: O(N)
Binary search: O(logN)
Insertion in unordered array: O(1)
Insertion in ordered array: O(N)
Deletion in unordered array: O(N)
Deletion in ordered array: O(N)
Bubble Sort:
- Compare two players
- If the one on the left is taller, swap them
Move one position right
You continue down the line this way until you reach the right end. You have by no means finishes sorting the kids, but you do know that the tallest kid is on the right.
When you reach the first sorted player, start over at the left end of the line.
Selection Sort:
- Making a pass through all the players and picking the shortest one.
- This shortest player is then swapped with the player on the left end of the line, at postion 0.
- Now the leftmost player is sorted and wont need to be moved again.
- The next time you pass down the row of players, you start at position 1, and, finding the minimum, swap with postion 1.
Insertion Sort:
A stack is used to reverse the letters（字段一个单词一个单词放入stack中） and delimiter matching（开始的（或{放入stack中，如果遇到}或者）就pop出来，出现pop的和输入的不符，则不匹配）.
Stack: FILO
Queue: FIFO
Priority Queue: Like an ordinary queue, a priority queue has a front and a rear, and items are removed from the front. However, in a priority queue, items are ordered by key value so that the item with the lowest key is always at the front. Items are inserted in the proper position to maintain the order.
The mergesort is fairly easy to implement. The downside of the mergesort is that it requires an additional array in memory, equal in size of the one being sorted. If your original array barely fits in memory, the mergesort wont work. However, if you have enough space, it's a good choice.