搜索与排序:Insertion Sort, Selection Sort, and Binary Search

本文将介绍两种排序方式以及一种搜索方式
I will talk about two different sorting method and a way of searching.

Selection Sort

当我们有一组乱序数字的时候,举例说
When we have an array of random numbers, for example

450 604 100 802 301 200
[0] [1] [2] [3] [4] [5]

我们先找到最小的数字100,然后把它和[0]的数字交换位置
Let’s find the smallest number first, which is 100, and then swap it with number in [0].

100 | 604 450 802 301 200
[0] | [1] [2] [3] [4] [5]

这样左边是已经排序好的数列,右边是还没有排序好的,我们用竖线隔开
In this case, we have a sorted array on the left and an unsorted array on the right. We seperate those two arrays by a line.

第二步,我们再从右边的数列里面找到最小的,和位置[1]的数字交换
Secondly, we find the minimum number from the array on the right and swap it with number in [1].

100 200 | 450 802 301 604
[0] [1] | [2] [3] [4] [5]

我们最后再不断重复这个步骤,直到全部整理完
Finally, we just kepp repeating this step until there isn’t any element in the right array.

100 200 301 | 802 450 604
[0] [1] [2] | [3] [4] [5]

100 200 301 450 | 802 604
[0] [1] [2] [3] | [4] [5]

100 200 301 450 604 | 802
[0] [1] [2] [3] [4] | [5]

100 200 301 450 604 802 |
[0] [1] [2] [3] [4] [5] |

Insertion Sort

这个方法里,我们把[0]位置的数字当作已经整理完的
In this method, we treat number in [0] as a sorted array

450 | 604 100 802 301 200
[0] | [1] [2] [3] [4] [5]

然后我们把[0]的数字和[1]的数字比较,[1]较小的话就插到[0]的前面
Then we compare numbers in [0] and in [1]. Insert the number in [1] if it is smaller

100 604 | 450 802 301 200
[0] [1] | [2] [3] [4] [5]

第二步,我们比较出450的正确位置,并插入
Secondly, we compare 450 with each number and insert it into the correct position

100 450 604 | 802 301 200
[0] [1] [2] | [3] [4] [5]

我们最后再不断重复这个步骤,直到全部整理完
Finally, we just keep repeating this step until there isn’t any element in the right array.

100 450 604 802 | 301 200
[0] [1] [2] [3] | [4] [5]

100 301 450 604 802 | 200
[0] [1] [2] [3] [4] | [5]

100 200 301 450 604 802 |
[0] [1] [2] [3] [4] [5] |

Binary Search

一个完整的检索过程是先整理无序的信息再寻找目标,所以我们假设Binary Search处理的数列是一个已经从小到大排列好的数列,比如我们要从下列数列中找到500
In order to search an object, we need to sort the original array first. So we assume what binary search deal with is a sorted list. For example, we want to find 500 in following array,

100 200 300 400 500 600
[0] [1] [2] [3] [4] [5]

我们先把这个数列分成两半,然后比较第一部分最后一个数字.
We divide this array into two halves and compare 500 with the last element in the first half.

100 200 300 | 400 500 600
[0] [1] [2] | [3] [4] [5]

300<500

很显然,500在第二部分,重复之前那个步骤
Clearly, 500 is not in the first half, then we divide the second half into two parts and compare again.

100 200 300 |    400 500 | 600
[0] [1] [2] |    [3] [4] | [5]

500==500

这样,我们就用了两次就找到了500,相比一个个比较的方法,显然要快很多。
That’s how we find 500 in the array. Obviously, it is faster than compare 500 with elements in the array one by one.