排序与查找算法总结

1. 排序

1. 选择排序：首先找到数组中最小的元素， 然后将它和数组中的第一个元素交换位置。 再次在剩下的元素中找到最小的元素， 将它与数组的第二个元素交换位置。它不断地在剩余元素中选择最小者。 O(n^2)
2. 插入排序：当前索引左边的元素都是有序的， 但它们的最终位置还不确定。将当前索引位置上的元素插入到之前已经有序的元素中的适当位置，当索引到达数组的右端时，排序就完成了。 与希尔排序的联系
3. 希尔排序：还是蛮奇怪的。。。
4. 归并排序：稳定的。归并的概念：将两个有序的数组归并成一个更大的有序数组。 递归方法。取两个数组的中当前元素的最小值，若某一个数组被取尽则后续直接用另一个数组填充。
5. 快速排序：最快的通用排序算法,分治的排序算法。将一个数组分为两个子数组， 并将两部分独立地排序。快速排序与归并排序是互补的。如何切分是快速排序的要点
   切分元素要点：
   1.对某个j, a[j]已经排定，
   2. a[lo..j-1] <= a[j] <= a[j+1..hi];从左到右扫描一个大于等于它的元素， 从右到左寻找一个小于等于它的元素，交换这两个元素的位置，当两个指针相遇时说明数组扫描完毕， 此次切分完成。
6. 堆排序
7. 冒泡排序

2. 查找

1. 二分查找树
2. 平衡查找树(红黑树)
3. 散列表