常用算法（C语言描述）

二分查找

要求：待查序列按关键码有序。基本思想：先确定待查记录所在的区间，然后逐步缩小范围直到找到或找不到该记录为止。折半查找要求线性表用顺序表作为存储结构。

int Search_Bin(int a[], int n, int target)//a[0]不用，a[1]~a[n]存储数据
{
    int low = 1;
    int high = n;
    while(low  target) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

直接插入排序

不断地将新来的元素插到有序序列的合适位置，特别适合于待排序序列基本有序的情况。（数据有序程度越高，越高效）

void InsertSort(int r[], int n)//r[0]不用，n为元素个数
{
    for(int i = 2; i  r[0]; j--)//边查边后移
            r[j+1] = r[j];
        r[j+1] = r[0];
    }
}

希尔排序

是插入排序的改进版，对于中等规模数据的性能表现还不错。在不相邻的元素之间进行比较和交换。利用了插入排序的最佳时间代价特性，它试图将待排序序列变成基本有序的，然后再用插入排序完成排序工作。但是希尔排序在插入时是跳跃式插入，有可能破坏稳定性，因此希尔排序是不稳定的。

const int INCRGAP = 3;
void ShellSort(int a[], int len)	//len为数组长度
{
    int InsertNum = 0;
    unsigned gap = len / INCRGAP + 1;	//进行步长初始化，当len =1
    {
        for(unsigned i = gap; i = gap && InsertNum 

冒泡排序

冒泡排序的方法是在待排序的元素中选择两个相邻的元素进行比较，反序则交换，直至没有反序为止。

//普通版
void BubbleSort(int r[], int n)
{
    for(int i = 1; i  r[j+1])	//相邻元素比较，交换
            {
                r[0] = r[j];
                r[j] = r[j+1];
                r[j+1] = r[0];
            }
        }
    }
}


//改进版
void BubbleSort(int r[], int n)
{
    int pos = n;
    while(pos != 0)
    {
        int bound = pos;	//比较边界，之后的为有序，无序比较
        int pos = 0;
        for(int i = 1; i  r[i+1])
            {
                pos = i;	//记录打破有序的位置
                r[0] = r[i]; r[i] = r[i+1]; r[i+1] = r[0];
            }
        }
    }
}

快速排序

快速排序是冒泡的改进，快排元素的比较和移动是从两端向中间进行的，移动的距离比较远，更靠近目的地，因此效率较高。

int Partion(int r[], int first, int end)
{
    int i = first;
    int j = end;
    int pivot = r[i];
    while(i  pivot)
            j--;	//右侧扫描，不符合条件左移
        r[i] = r[j];
        while(i 

简单选择排序

选择排序的基本方法：每趟选择待排序序列中关键码最小的元素，顺序添加到已排好序的有序序列后面，直到全部记录排序完毕。

void SelectSort(int r[], int n)
{
    for(int i=1; i 

直接选择排序

堆排序

堆排序通过构造大根堆或者小根堆的数据结构来记录简单选择排序中前一趟的比较结果，从而减少比较次数，提高整个排序的效率。以大根堆为例。

void Sift(int r[], int k, int m)	//用数组记录堆，k是要调整的节点，通过调整满足堆的性质
{
    int i = k, j = 2 * i;
    while(j  r[j]) break;	//满足条件，跳出
        else
        {
            r[0] = r[i];
            r[i] = r[j];
            r[j] = r[0];
            i = j;j = 2*i;	//比较节点下移
        }
    }
}

void HeapSort(int r[], int n)
{
    for(int i = n/2; i >= 0; i--)	//构建堆
        Sift(r, i, n);
    for(int i = n; i > 1; i--)
    {
        r[0] = r[1]; r[1] = r[i]; r[i] = r[0];	//输出堆顶元素
        Sift(r, 1, i-1);	//调整使满足堆的性质
    }
}

归并排序

归并排序的基本思想是：将两个或两个以上的有序序列归并成一个有序序列

//归并两个有序序列
void Merge(int r[], int r1[], int s, int m ,int t)
{
    int i = s, j = m + 1, k = s;
    while(i 

基数排序

//求数据的最大位数，决定排序的次数
int MaxBit(int data[], int n)		//n为数组的位数
{
    int max = 1;	//保存最大的位数
    int temp = 10;
    for(int i = 0; i = temp)
        {
            temp *= 10;
            ++max;
        }
    }
    return max;
}

//基数排序
void RadixSort(int data[] , int n)
{
    int max = MaxBit(data, n);
    int temp[n];
    int i, j, k;
    int radix = 1;
    for(i = 1; i = 0; j--)	//将所有桶中记录依次收集到temp中
        {
            k = (data[j] / radix) % 10;
            temp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j