常见排序算法
在计算机科学与数学中，一个排序算法（Sorting algorithm）是一种能将一串数据依照特定排序方式的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，如此这些算法才能得到正确解答。排序算法也用在处理文字数据以及产生人类可读的输出结果。基本上，排序算法的输出必须遵守下列两个原则：
• 输出结果为递增串行（递增是针对所需的排序顺序而言）
• 输出结果是原输入的一种排列、或是重组
分类：
主要有以下几大方面：
• 计算复杂度：也就是时间复杂度，（最差、平均、和最好性能），依据列表（list）的大小（n）。一般而言，好的性能是O(n log n)，且坏的行为是O(n2)
• 存储器使用量：也就是空间复杂度
• 稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
• 排序特性：插入、交换、选择、合并等等
• 排序范畴：内存排序(内排)，外存排序（外排）
具体分为以下：
说明：
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
冒泡排序
算法步骤：
1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的示例：
package org.vanjor.sort;
public class BubbleSort implements Sorter {
@Override
public String getName() {
return "BubbleSort";
}
@Override
public void sort(int[] array) {
int temp;
for (int i = 0; i < array.length - 1; i++) {
// 每次将最小的冒到最前面
for (int j = array.length - 1; j > i; j--) {
if (array[j - 1] > array[j]) {
temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
}
插入排序
算法步骤：
1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
插入排序的示例：
package org.vanjor.sort;
public class InsertSort implements Sorter {
@Override
public String getName() {
return "InsertSort";
}
@Override
public void sort(int[] array) {
int temp;
int j;
// i之前的子串都是已经排序好了
for (int i = 1; i < array.length; i++) {
j = i;
temp = array[j];
// 对当前位置j的数字在已排序好的子串选择合适的位置插入
while (j > 0 && temp < array[j - 1]) {
// 顺移直接存放
array[j] = array[j - 1];
j--;
}
// 选择到位置，直接存放归队
array[j] = temp;
}
}
}
折半插入排序
相比简单插入排序，折半插入在已排序中寻找插入位置用折半查找：
package org.vanjor.sort;
public class HalfInsertSort implements Sorter {
@Override
public String getName() {
return "HalfInsertSort";
}
@Override
public void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 二分查找寻找最佳插入位置
int low = 0, high = i - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (array[middle] > array[i]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
// 顺移并插入
int cursor = i;
int temp = array[i];
while (cursor > low) {
array[cursor] = array[cursor - 1];
cursor--;
}
array[cursor] = temp;
}
}
}
选择排序
算法步骤：
1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。
选择排序的示例：
package org.vanjor.sort;
public class SelectSort implements Sorter {
@Override
public String getName(){
return "SelectSort";
}
@Override
public void sort(int[] array) {
int cursor;
int temp;
for (int i = 0; i < array.length - 1; i++) {
//通过比较选出最小值的游标，最后才交换
cursor = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[cursor]) {
cursor = j;
}
}
if(cursor!=i){
temp = array[i];
array[i] = array[cursor];
array[cursor] = temp;
}
}
}
}
快速排序
算法步骤：
从数列中挑出一个元素，称为 “基准”（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
快速排序的示例：
（a）一趟排序的过程：
（b）排序的全过程
package org.vanjor.sort;
public class QuickSort implements Sorter {
@Override
public String getName() {
return "QuickSort";
}
@Override
public void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
sort(array, 0, array.length - 1);
}
/**
* 递归式，对array中的start到end区域进行快排
*
* @param array
* @param start
* @param end
*/
private void sort(int[] array, int start, int end) {
// 递归终止条件
if (start >= end) {
return;
}
int low = start;
int high = end;
// 选择当前子数组第一个数为旗帜
int flag = array[low];
while (low < high) {
while (low < high && array[high] >= flag) {
high--;
}
array[low] = array[high];
while (low < high && array[low] <= flag) {
low++;
}
array[high] = array[low];
}
// 此时low的位置为旗帜的最终正确位置
array[low] = flag;
// 递归对旗帜的两边进行排序，这是low=high
sort(array, start, low - 1);
sort(array, high + 1, end);
}
}
希尔排序
相比冒泡排序，相邻比较，希尔是选择一定间隔的进行比较，间隔逐渐缩短，最终做到有序，相比冒泡排序，减少了比较交换的次数。
算法步骤：
1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2）按增量序列个数k，对序列进行k 趟排序；
3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：
package org.vanjor.sort;
public class ShellSort implements Sorter {
@Override
public String getName() {
return "ShellSort";
}
@Override
public void sort(int[] array) {
int temp;
int inc = array.length / 2;
while (inc >= 2) {
for (int cursor = 0; cursor <= array.length - 1 - inc; cursor++) {
if (array[cursor] > array[cursor + inc]) {
temp = array[cursor];
array[cursor] = array[cursor + inc];
array[cursor + inc] = temp;
}
}
// 步长序列每次除2
inc /= 2;
}
// 最后步长为1，知道检查无更改，即退出循环
boolean tag = true;
while (tag) {
tag = false;
for (int cursor = 0; cursor < array.length - 1; cursor++) {
if (array[cursor] > array[cursor + 1]) {
temp = array[cursor];
array[cursor] = array[cursor + 1];
array[cursor + 1] = temp;
tag = true;
}
}
}
}
}
归并排序
算法步骤：
1)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2)设定两个指针，最初位置分别为两个已经排序序列的起始位置
3)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4)重复步骤3直到某一指针达到序列尾
5)将另一序列剩下的所有元素直接复制到合并序列尾
归并排序的示例：
package org.vanjor.sort;
public class MergeSort implements Sorter {
@Override
public String getName(){
return "MergeSort";
}
@Override
public void sort(int[] array) {
int[] tempArray = new int[array.length];
mergeSort(array, tempArray, 0, array.length - 1);
}
/**
* 不断分割，再合并，递归求解
*/
private void mergeSort(int[] array, int[] tempArray, int start, int end) {
// 递归终止条件，最终粒度为1
if (end <= start) {
return;
}
// 这里保证了start<=middle,middle+1<=end
int middle = (start + end) / 2;
// 从middle分两部分，每一部分排序后，再合并排序
mergeSort(array, tempArray, start, middle);
mergeSort(array, tempArray, middle + 1, end);
// 合并
merge(array, tempArray, start, middle, end);
}
/**
* 将两个有序数组合并，两数组的位置分别为start->middle,middle+1->end
*/
private void merge(int[] array, int[] tempArray, int start, int middle, int end) {
int i = start, j = middle + 1;
int m = middle, n = end;
int k = start;
//将两相邻子数组合并到临时数组中
while (i <= m && j <= n){
if (array[i] <= array[j]) {
tempArray[k++] = array[i++];
} else {
tempArray[k++] = array[j++];
}
}
//对剩余的部分直接复制
while (i <= m) {
tempArray[k++] = array[i++];
}
while (j <= n) {
tempArray[k++] = array[j++];
}
//将临时数据中按位置拷贝回
for (i = 0; i < k; i++) {
array[start + i] = tempArray[i];
}
}
}
堆排序
运用堆的特性，特殊的二叉树，顶点比两个孩子要么都大（大顶堆），要么都小（小顶堆），对于数组初始化构建后，也是一个完全二叉树，序号为p的两个孩子为2p与2p+1，先n/2轮次（从最底端非叶子节点开始）建堆，然后每次取堆顶，后调整堆，最终完成有序排序。
堆排序算法的基本思想是，将数组A创建为一个最大堆，然后交换堆的根(最大元素)和最后一个叶节点x，将x从堆中去掉形成新的堆A1，然后重复以上动作，直到堆中只有一个节点。
算法步骤：
1）创建一个堆H[0…n-1]
2）把堆首（最大值）和堆尾互换
3）把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4）重复步骤2，直到堆的尺寸为1
根结点（堆顶元素）的值是最小(或最大)：
（a）大顶堆序列：（96, 83,27,38,11,09)
（b）小顶堆序列：（12，36，24，85，47，30，53，91）
调整小顶堆的方法：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
2）将根结点与左、右子树中较小元素的进行交换。
3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）。
4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）。
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图：
再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。
2）筛选从第个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
package org.vanjor.sort;
public class HeapSort implements Sorter {
@Override
public String getName() {
return "HeapSort";
}
public void sort(int[] array) {
if (array == null || array.length < 2) {
return;
}
int len = array.length - 1;
// 从最底层非叶子节点开始建堆
for (int i = (len) / 2; i >= 1; i--) {
headAjust(array, i, len);
}
// 需要turnNum次取堆顶，获得全部排序
int turnNum = len;
// 当前轮次，堆顶，最大值
int turnMax = array[1];
// 因为array排序起点为1，所谓到1停止了
while (turnNum >= 1) {
array[1] = array[turnNum];
array[turnNum] = turnMax;
turnNum--;
// 重建堆
headAjust(array, 1, turnNum);
// 得到新堆堆顶
turnMax = array[1];
}
}
public void headAjust(int[] array, int start, int end) {
int cursor;
// 保存当前顶点start值
int local = array[start];
for (cursor = 2 * start; cursor <= end; cursor *= 2) {
// 取start的两个叶子节点中较大者，cursor为对应叶子节点序号
if (cursor < end && array[cursor] < array[cursor + 1]) {
cursor++;
}
// 如果顶节点就是最大，则无需继续调节了
if (local >= array[cursor]) {
break;
}
// 最大值上移到顶点
array[start] = array[cursor];
// 沿树向下继续建堆调整，其实也就是被替换下来的顶点找到位置
start = cursor;
}
// 找到对应位置，归位
array[start] = local;
}
}
基数排序
基数排序中的一个环节与桶排序思路很相同，就是利用数字分层，如个位，十位，百位，分别排序，每一层都可以被放在十个桶里，从0到9，进行轮次的取放，最终得到有序。
基数排序是典型的利用空间换时间的一种思路，有两种极端的方向：
- 桶够多：如果带排数相差不是特别大，可以用一个足够的桶集，直接将每一个不同的数放到不同的桶里，最后桶的顺序就是数的顺序，在数的密度够均匀的情况下效率为O(n)
- 桶够少：如果按bit位来进行基数排序时，每个bit就两种情况0,1,也就是只需要两个桶，但是这样总共需要的轮次，假设最大值为M，则轮次为log(M)，时间复杂度为log(M)•O（n）
基数排序的主要思路是，将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零。然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9)。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程
第一次排序(个位):
3 4 2
5 7 6
3 5 6
0 5 8
第二次排序(十位):
3 4 2
3 5 6
0 5 8
5 7 6
第三次排序(百位):
0 5 8
3 4 2
3 5 6
5 7 6
结果: 58 342 356 576
package org.vanjor.sort;
import java.util.ArrayList;
import java.util.LinkedList;
public class RadixSort implements Sorter {
@Override
public String getName() {
return "RadixSort";
}
@Override
public void sort(int[] array) {
// 只是为了演示，基数所用桶，这里用高级链表API
// 桶集A存放当前轮次开始前的状态
ArrayList<LinkedList<Integer>> bucketA = new ArrayList<LinkedList<Integer>>();
// 桶集B存放当前轮次排序后的状态
ArrayList<LinkedList<Integer>> bucketB = new ArrayList<LinkedList<Integer>>();
// 每轮次排序后颠倒后交换用
ArrayList<LinkedList<Integer>> tempArray;
// 基于数字排序，共10个桶
final int bucketBase = 10;
int temp = bucketBase;
while ((--temp) >= 0) {
bucketA.add(new LinkedList<Integer>());
bucketB.add(new LinkedList<Integer>());
}
// 找出当前最大的数，用以确定最多需要桶装填的轮次
int maxNum = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] > maxNum) {
maxNum = array[i];
}
}
// 计算轮次
int turn = 0;
while (maxNum > 0) {
turn++;
maxNum /= bucketBase;
}
// 初始装填到A桶集中
for (int i = 0; i < array.length; i++) {
bucketA.get(array[i] % 10).add(array[i]);
}
int locNum;
int turnBaseDiv = 1;
while ((turn--) > 0) {
// 当前轮次，对桶集中的10个桶按当前位进行重新状态
for (int i = 0; i < bucketBase; i++) {
while (!bucketA.get(i).isEmpty()) {
locNum = bucketA.get(i).remove();
// 根据当前轮次比较位，找到对应的桶
bucketB.get((locNum / turnBaseDiv) % 10).add(locNum);
}
}
// 比较位前移
turnBaseDiv *= 10;
// 交换A，B次序
tempArray = bucketB;
bucketB = bucketA;
bucketA = tempArray;
}
// 从桶中顺序取数
for (int i = 0, j = 0; i < 10; i++) {
while (!bucketA.get(i).isEmpty()) {
array[j++] = bucketA.get(i).remove();
}
}
}
}
桶式排序
桶式排序不再是基于比较的了，它和基数排序同属于分配类的排序，这类排序的特点是事先要知道待排序列的一些特征。桶式排序事先要知道待排序列在一个范围内，而且这个范围应该不是很大的。比如知道待排序列在[0,M）内，那么可以分配M个桶，第I个桶记录I的出现情况，最后根据每个桶收到的位置信息把数据输出成有序的形式。这里我们用两个临时性数组，一个用于记录位置信息，一个用于方便输出数据成有序方式，另外我们假设数据落在0到MAX,如果所给数据不是从0开始，你可以把每个数减去最小的数。
如果我们有N个整数，范围从1到M(或从0到M-1)，我们可以利用这个信息得到一种快速的排序，叫做桶式排序(bucket sort)。我们留置一个数组，称之为Count，大小为M，并初始化为零。于是，Count有M个单元(或桶)，开始时他们都是空的。当数组元素A[i]被读入时Count[A[i]]增1。在所有的输入被读进以后，扫描数组Count，打印输出排好序的表。该算法花费O(M+N)。
由此我们可以发现桶式排序需要满足的两个前提条件：第一，待排序数组元素为非负整数；第二，待排序数组元素有界。这两个前提条件限制了桶式排序的应用范围，但桶式排序算法的思想是很值得我们学习和借鉴的。
#include <stdio.h>
// Count数组大小
#define MAXNUM 100
// 功能：桶式排序
// 输入：待排序数组 arrayForSort[]
// 待排序数组大小 arraySize
// 待排序数组元素上界 maxItem；数组中的元素都落在[0, maxItem]区间
// 输出：void
void BucketSort(int arrayForSort[], int arraySize, int maxItem)
{
int Count[MAXNUM];
// 置空
for (int i = 0; i <= maxItem; ++i)
{
Count[i] = 0;
}
// 遍历待排序数组
for (int i = 0; i < arraySize; ++i)
{
++Count[arrayForSort[i]];
}
// 桶排序输出
// 也可以存储在数组中，然后返回数组
for (int i = 0; i <= maxItem; ++i)
{
for (int j = 1; j <= Count[i]; ++j)
{
printf("%3d", i);
}
}
printf("\n");
}
void main()
{
// 测试
int a[] = {2, 5, 6, 12, 4, 8, 8, 6, 7, 8, 8, 10, 7, 6, 0, 1};
BucketSort(a, sizeof(a) / sizeof(a[0]), 12);
}
其它算法
1. 使用随机算法产生一个数，要求把1-1000W之间这些数全部生成。
/**
* 使用随机算法产生一个数，要求把1-1000W之间这些数全部生成。
* （考察高效率，解决产生冲突的问题）
*/
private static void testRandom() {
int value = 10000000;
//int类型最大值：2的32次方 - 1 = Integer.MAX_VALUE = 2147483647，二十亿多,真够啦 。
Set<Integer> result = Sets.newHashSetWithExpectedSize(value);
Random random = new Random();
long a = System.currentTimeMillis();
while (result.size() < value + 1) {
int i = random.nextInt(value + 1);
result.add(i);
}
System.out.println("\r<br> 执行耗时 : " + (System.currentTimeMillis() - a) / 1000f + " 秒 ");
System.out.println("完了，集合大小为" + result.size());
}
具体请看：http://blog.csdn.net/qq_27093465/article/details/52598034
2. 两个有序数组的合并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列
import com.alibaba.fastjson.JSON;
public class MergeSort {
//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int[] a, int n, int[] b, int m, int[] c)
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
void mergearray(int[] a, int first, int mid, int last, int[] temp)
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int[] a, int first, int last, int[] temp)
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
boolean MergeSort(int[] a, int n)
{
int[] p = new int[n];
if (p == null)
return false;
mergesort(a, 0, n - 1, p);
return true;
}
public static void main(String[] args) {
MergeSort mergeSort = new MergeSort();
int[] a = {1,3,5,7,9,11,12,13};
int[] b = {2,3,6,8,10};
int[] c = new int[a.length + b.length];
mergeSort.MemeryArray(a, a.length, b, b.length, c);
System.out.println(JSON.toJSONString(c));
int[] arr = {11, 3, 1, 4, 1, 2, 20, 5, 10, 6};
mergeSort.MergeSort(arr, arr.length);
System.out.println(JSON.toJSONString(arr));
}
}
3. 一个数组的倒序
private static void testArrayReverse() {
int[] data = {22, 12, 33, 24, 75};
System.out.println("原顺序" + Arrays.toString(data));
int length = data.length;
for (int i = 0; i < length / 2; i++) {
int temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
System.out.println("倒序后" + Arrays.toString(data));
}
具体请看：http://blog.csdn.net/qq_27093465/article/details/52595958
4. 计算一个正整数的正平方根
可以用移位法求平方根，方法和 手动计算 平方根类似。
至于效率，没比较过，不知道那个快一点
移位法，不用浮点数，对于不能计算浮点数的CPU，还是不错的
上取整，下取整，四舍五入取整，都可以实现
#include <iostream>
#include <cmath>
using namespace std;
typedef unsigned int uint;
///四舍五入法
uint sqrt_round(uint a){
uint r=0;
int n = sizeof(a)*8/2;
uint rem = (a>>(n*2-2));
for(int i=0;i<n+1;i++){
r <<= 1;
if(rem >=2*r+1 )
{rem-=2*r+1;++r;}
a <<= 2;
rem<<=2;
rem+= (a>>(n*2-2));
}
return (r >> 1)+(r & 1);
}
///下取整
uint sqrt_floor(uint a){
uint r=0;
int n = sizeof(a)*8/2;
uint rem = (a>>(n*2-2));
for(int i=0;i<n;i++){
r <<= 1;
if(rem >=2*r+1 )
{rem-=2*r+1;++r;}
a <<= 2;
rem<<=2;
rem+= (a>>(n*2-2));
}
return r;
}
///上取整
uint sqrt_ciel(uint a){
uint r=0;
int n = sizeof(a)*8/2;
uint rem = (a>>(n*2-2));
for(int i=0;i<n;i++){
r <<= 1;
if(rem >=2*r+1 )
{rem-=2*r+1;++r;}
a <<= 2;
rem<<=2;
rem+= (a>>(n*2-2));
}
return r+ (rem >0);
}
int main()
{
for(int i=0;i<=100;i++){
cout <<"floor sqrt("<< i <<") = "
<< sqrt_floor(i)<<endl;
cout <<"round sqrt = "<< sqrt_round(i)<<endl;
cout <<"ciel sqrt = "<<sqrt_ciel(i)<<endl;
cout <<"double sqrt ="<<sqrt(i) <<endl;
}
return 0;
}
5. 二叉树的遍历算法
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
具体请看：
- http://blog.csdn.net/sjf0115/article/details/8645991
- http://blog.csdn.net/pony_maggie/article/details/38390513
6. DFS,BFS算法
关于图的搜索有两种：广度优先（bfs）深度优先 （dfs）。
以下图为例：
深度优先的基本思想简单说就是搜到底，重新搜。从v0为起点进行搜索，如果被访问过，则做一个标记，直到与v0想连通的点都被访问一遍，如果这时，仍然有点没被访问，可以从中选一个顶点，进行再一次的搜索，重复上述过程，所以深度优先的过程也是递归的过程。
深度优先访问的结果是：0->1->3->7->4->2->5->6
广度优先的基本思想是，从顶点v0出发，访问与v0相邻的点，访问结束后，再从这些点出发，继续访问，直到访问结束为止。标记被访问过的点同深搜一下，不过，广度优先一般需要用到队列。
上图广度优先的结果：0->1->2->3->4->5->6->7
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define maxn 100
using namespace std;
typedef struct
{
int edges[maxn][maxn]; //邻接矩阵
int n; //顶点数
int e; //边数
}MGraph;
bool vis[maxn]; //标记顶点是否被访问过
void createGraph(MGraph &G) //用引用做参数
{
int i,j;
int s,t; //存储顶点的编号
int v; //存储边的权值
for(i=0;i<G.n;i++) //初始化
{
for(j=0;j<G.n;j++)
{
G.edges[i][j] = 0;
}
vis[i] = false;
}
for(i = 0;i<G.e;i++) //对邻接矩阵的边赋值
{
scanf("%d%d%d",&s,&t,&v); //输入边顶点的编号以及权值
G.edges[s][t] = v;
}
}
void dfs(MGraph G,int v)
{
int i;
printf("%d ",v); //访问结点v
vis[v] = true;
for(int i = 0;i<G.n;i++) //访问与v相邻且未被访问过的结点
{
if(G.edges[v][i]!=0&&vis[i]==false)
{
dfs(G,i);
}
}
}
void dfs1(MGraph G,int v) //非递归实现(用到了栈，其实在递归的实现过程，仍是用到了栈，所以。。。)
{
stack<int> s;
printf("%d",v); //访问初始的结点
vis[v]=true;
s.push(v); //入栈
while(!s.empty())
{
int i,j;
i=s.top(); //取栈顶顶点
for(j=0;j<G.n;j++) //访问与顶点i相邻的顶点
{
if(G.edges[i][j]!=0&&vis[j]==false)
{
printf("%d ",j); //访问
vis[j]=true;
s.push(j); //访问完后入栈
break; //找到一个相邻未访问的顶点，访问之后跳出循环
}
}
if(j==G.n) //如果与i相邻的顶点都被访问过，则将顶点i出栈
s.pop();
}
}
void bfs(MGraph G,int v)
{
queue<int> Q;
printf("%d",v);
vis[v] = true;
Q.push(v);
while(!Q.empty())
{
int i,j;
i = Q.front(); //取队首顶点
Q.pop();
for(j=0;j<G.n;j++) //广度遍历
{
if(G.edges[i][j]!=0&&vis[j]==false)
{
printf("%d",j);
vis[j]=true;
Q.push(j);
}
}
}
}
int main()
{
int n,e; //建图的顶点数和边数
while(scanf("%d%d",&n,&e)==2&&n>0)
{
MGraph G;
G.n = n;
G.e = e;
createGraph(G);
dfs(G,0);
printf("\n");
// dfs1(G,0);
// printf("\n");
// bfs(G,0);
// printf("\n");
}
return 0;
}
/*测试数据：
9
1 1
3 1
4 1
7 1
7 1
2 1
5 1
6 1
6 1
*/
7. 比较重要的数据结构，如链表，队列，栈的基本理解及大致实现。
单向链表：
public class LinkedList {
private Node head;
private Stack s;
LinkedList(){
head = null;
s = new Stack();
}
private static class Node{
int item;
Node next;
Node(){
this.item = 0;
this.next = null;
}
Node(int item, Node next){
this.item = item;
this.next = next;
}
}
public void insert(int x){
Node node = new Node(x, null);
Node p = head;
// 注意链表为空的时候的插入
if(head==null){
head = node;
}
// 尾插法
else{
while(p.next != null){
p = p.next;
}
p.next = node;
}
}
public void travese(Node head){
Node p = head;
while(p!=null){
System.out.println(p.item);
p = p.next;
}
}
双向链表：
public class DoubleLinkedList {
// 哨兵节点nil(作为表头指针)
private Node nil;
// 初始化一个链表
DoubleLinkedList(){
nil = new Node();
nil.next = nil;
nil.prev = nil;
count = 0;
}
// 链表长度
private int count;
private static class Node{
int item;
Node next;
Node prev;
Node(){
item = 0;
next = null;
prev = null;
}
Node(int item, Node next, Node prev){
this.item = item;
this.next = next;
this.prev = prev;
}
}
//返回当前链表的长度
public int length(){
return count;
}
//获取value为k的节点
public Node listsearch(int k){
Node result = null;
Node head = nil;
while(head.next != nil){
if(head.next.item == k){
result = head.next;
break;
}
else
head = head.next;
}
return result;
}
//插入一个节点在队首
public void listinsert(Node node){
node.next = nil.next;
nil.next.prev = node;
nil.next = node;
node.prev = nil;
count++;
}
//根据value删除一个节点
public Node listdelete(Node node){
Node head = nil;
Node nodetodelete;
while(head.next!=nil){
if(head.next.item == node.item){
nodetodelete = head.next; //将要删除的节点
head.next = nodetodelete.next;
nodetodelete.next.prev = head;
nodetodelete = null;
count--;
}
else{
head = head.next;
}
}
return node;
}
//输出链表
public void traverse(){
Node head = nil;
while( head.next!= nil){
System.out.println(head.next.item);
head = head.next;
}
}
队列：
public class Queue {
private int[] array = new int[4];
private int head = 1;
private int tail = 1;
//入队
public void enqueue(int x){
//处理上溢
try{
if(head != tail +1){
array[tail++] = x;
if(tail == array.length){
tail = 0;
}
}
else{
System.out.println("overflow");
throw new Exception("queue overflow");
}
}catch(Exception e){
e.printStackTrace();
}
}
//出队
public int dequeue(){
int number=0;
try{
if(tail != head){
number = array[head];
head++;
}
else{
throw new Exception("queue underflow");
}
}catch(Exception e){
System.out.println("underflow");
e.printStackTrace();
}
return number;
}
栈：
public class Stack {
private int[] array = new int[5];
private int top = -1;
public Boolean stackempty(){
if(top == -1){
return true;
}
else
return false;
}
public void push(int x){
if(top<=array.length-1){
array[++top] = x;
}
else{
System.out.println("overflow");
}
}
public int pop() {
int number = -1;
if(stackempty() != true){
number = array[top];
top--;
return number;
}
else
{
System.out.println("underflow");
return -1;
}
}
具体请看：
8. 快排为什么不稳定，为什么你的项目还在用
排序算法稳定定义是:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
快速排序是从头和尾开始对元素进行比较，有可能把关键值相同的两个元素调换了位置，所以说是不稳定的，比如对 2 4 1 3 1进行排序，第一趟就把后面的1换到前面去，形成了不稳定排序
9. 逆波兰计算器
涉及到中缀表达式，波兰表达式、逆波兰表达式
具体请看： http://blog.csdn.net/Leoamy/article/details/51217362
10. Hoffman 编码
霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
11. 查找树与红黑树
（1）二叉查找树
二叉搜索树是一种特殊的二叉树，即：节点的左子节点的值都小于这个节点的值，节点的右子节点的值都大于等于这个节点的值。
搜索二叉树有一个特点，即如果使用中序遍历遍历搜索二叉树，将得到包含搜索二叉树中所有节点值的升序排序结果。
树的大部分操作需要从上至下一层层的查找树的节点，对于一棵满树，大约有一半的节点处于最底层（最底层节点数 = 其它层节点数的和 + 1），故节点操作大约有一半需要找到最底层节点，大约有四分之一的节点处于倒数第二层，故节点操作大约有四分之一需要找到倒数第二层节点，依此类推
查找过程中，需要访问每一层的节点，故只要知道了查找的层数，就能知道操作所需的时间，如果节点总数为N，层数为L，L=log2(N+1)
总的来说可以认为二叉搜索树操作的时间复杂度为为O(logN)
具体请看： http://www.cnblogs.com/fingerboy/p/5493786.html
（2）红黑树
红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。
红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
- (1) 每个节点或者是黑色，或者是红色。
- (2) 根节点是黑色。
- (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
- (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
- (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
关于它的特性，需要注意的是：
- 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
- 第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
红黑树示意图如下：
具体请看：