1. Bubble Sort (internal sorting)

Bubble Sort 是本科接触的第一个☝️排序算法， Bubble sort steps through the list and compares adjacent pairs of elements. The elements are swapped if there are in the wrong order. 但是也正是因为冒泡法从头到尾的遍历过程中需要两两相比较，如果比较的很顺利，也就是整个array其实已经是排序好了的，这时候的time complexity 就是$o(n)$，如果整个array是乱七八糟的，这时候也就是worst time complexity $o(n^2)$

2. Insertion Sort (internal sort)

On each loop iteration, insertion sort removes one element from the array. It then finds the location where that element belongs within another sorted array and inserts it there. 我们先来看一下插入排序的pesudo code。

Loop from i = 1 to n-1

pick element arr[i], and insert it into the sorted sequence arr[0...i-1]

然后再举个例子来理解，

arr[] = 11 13 10 20

1st loop: 11 13 10 20 （since 11< 13)

2nd loop: 10 11 13 20 (since 10 < 11)

3rd loop: 10 11 13 20 (since 20 > 13)

现在我们来看一下time complexity。好的情况就是没有swap的过程，和上面bubble一样，整个array其实已经是排序好了的，所以best time complexity $o(n)$ 。坏的情况就是我们需要的是升序的，但一开始的array是降序排列的, # opertaion = n(n-1) 所以worst time complexity $o(n^2)​$

3. Selection Sort (internal sort)

The algorithm maintains two subarrays in a given array. 1)The subarray which is already sorted 2) Remaining subarray which is unsorted。也就是我们把一个数组分为已经排列整齐的 和 乱七八糟的两类。在乱七八糟的那一部分找到一个最小的元素，把它放到已经排列好的那一部分的数组中正确的位置中去。

用上面同样的例子来理解一下

arr[] = 11 13 10 20

10 // find the minimum element in arr[0…3] put at the beginning

10// sorted 11 13 20// unsorted

11 // find the minimum element in arr[1…3] put at the second place

10 11 //sorted 13 20 // unsorted

13 // find the minimum element in arr[2..3] put at the third place

then we get 10 11 13 20

---------------------- 本文结束----------------------