简单排序查找算法总结

排序算法

冒泡排序

存在10个不同大小的气泡，由底至上地把较少的气泡逐步地向上升，这样经过遍历一次后，最小的气泡就会被上升到顶（下标为0），然后再从底至上地这样升，循环直至十个气泡大小有序。
即相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成

插入排序

将数据分为两部分，有序部分与无序部分，
一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。
插入排序又分为直接插入排序、二分插入排序、链表插入等，
它是稳定的排序算法，时间复杂度为O(n^2)

快速排序

快速排序是目前在实践中非常高效的一种排序算法，它不是稳定的排序算法，平均时间复杂度为O(nlogn)，最差情况下复杂度为O(n^2)。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

选择排序

基本原理：先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

堆排序

先将初始数据R[1..n]建成一个最大堆，此堆为初始的无序区
再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
重复2、3步骤，直到无序区只有一个元素为止。

归并排序

将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕
归并排序是稳定的排序算法，其时间复杂度为O(nlogn)如果是使用链表的实现的话，空间复杂度可以达到O(1)，但如果是使用数组来存储数据的话，在归并的过程中，需要临时空间来存储归并好的数据，所以空间复杂度为O(n)

搜索查找算法

顺序查找

从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。
若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。
优点: 不要求待查找序列有序
缺点: 效率低，特别是待查找序列很大时

块查找

1. 首先将查找表分成若干块，在每一块中数据元素的存放是任意的，但块与块之间必须是有序的（假设这种排序是按关键字值递增的，也就是说在第一块中任意一个数据元素的关键字都小于第二块中所有数据元素的关键字，第二块中任意一个数据元素的关键字都小于第三块中所有数据元素的关键字，依次类推）；
2. 建立一个索引表，把每块中最大的关键字值按块的顺序存放在一个辅助数组中，这个索引表也按升序排列；
3. 查找时先用给定的关键字值在索引表中查找，确定满足条件的数据元素存放在哪个块中，查找方法既可以是折半方法，也可以是顺序查找。
4. 再到相应的块中顺序查找，便可以得到查找的结果。
   优点：
   ①在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。
   ②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
   分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
   分块查找算法的效率介于顺序查找和二分查找之间。

二分查找

条件：数组递增
基本思想：

1. 查找区间R[low..high]，首先确定该区间的中点位置：mid = (low + high) / 2;
2. 然后将待查的K值与R[mid]比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。
   ① 若R[mid] > K，则由数组的有序性可知R[mid..n]均大于K，因此该结点必定是在位置mid左边的R[0..mid-1]中
   ② 若R[mid] < K，则要查找的K必在mid的右边的R[mid+1..n]中，下一次查找是针对新的查找区间进行的。
3. 因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

附录

简单算法的多语言示例