Sort
Main sort algorithms based on 2 number comparison are selection sort, insertion sort, bubble sort, merge sort, and quick sort. Selection sort, insertion sort, and bubble sort’s time complexity are O(n ^ 2). Merge sort, heap sort time complexity are O(nlogn), and quick sort average time complexity is O(nlogn). The sort algorithm itself is not very often asked during an interview. However, the thought extended from the sort algorithm is widely used.
In this article, we will mainly focus on the merge and quick sort and their appliance. We will only briefly describe what other sort algorithms are.
The main thought in this article is originated from jiuzhang
Selection Sort:
Find the smallest element in each iteration and put it in front of all unsorted element.
In the inner loop A[i]will compare to A[j]
Insertion Sort:
We will enlarge our sorted area one by one, and make sure the each new element will be in order in the sorted area. It is like playing poke, every time when we pick a new card (enlarge the sorted area), we will put it into the correct order to make sure all cards we have are in order.
In the inner loop j will start from i - 1 , and A[j]will compare to A[j - 1]
Bubble Sort:
In each iteration, we need make sure every 2 elements closed to each other are in order. Thus in one round of iteration, we can make sure the last one is the largest.
In the inner loop, A[j]will compare to A[j + 1] and make sure i and j will loop A.length times
Heap Sort:
It will be described in the Heap article
Merge Sort:
Details are described in MergeSort article
Quick Sort:
Details are described in QuickSort article