排序和查找算法

1、冒泡排序算法

void popSort(int *p, int n)
{
    for(int i= 0; i<n-1; i++)
    {
        for(int j=0; j<n-1-i; j++)
        {
            if(p[j] > p[j+1])
            {
                p[j] ^= p[j+1];
                p[j+1] ^= p[j];
                p[j] ^= p[j+1];
            }
        }
    }
}

2、插入排序

void insertSort(int *a,int n)
{
    int i,j,key;
    for(i=1;i<n;i++)//控制需要插入的元素
    {
        key = a[i]; //key 为要插入的元素
        //查找要插入的位置,循环结束,则找到插入位置
        for(j=i; j-1>=0 && a[j-1]>key; j--)
        {
            a[j] = a[j-1]; //移动元素的位置.供要插入元素使用
        } a
                [j] = key; //插入需要插入的元素
    }
}

3、希尔排序

void shellSort(int *p, int n)
{
    int gap =n/ 2;
    while (gap >= 1)
    {
        // 把距离为 gap 的元素编为一个组, 扫描所有组
        int i,j,key;
        for ( i = gap; i < n; i++)
        {
            key = p[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i; j-gap >=0 && p[j-gap] > key ; j = j - gap)
            {
                p[j] = p[j-gap];
            } p
                    [j] = key;
        }
        gap = gap / 2; // 减小增量
    }
}

4、选择排序

int selectSort(int *p, int n)
{
    int idx;
    for(int i=0; i<n-1; i++)
    {
        idx = i;
        for(int j=idx+1; j<n; j++)
        {
            if(p[idx] >p[j])
                idx = j;
        }
        if(idx != i)
        {
            p[i] ^= p[idx];
            p[idx] ^= p[i];
            p[i] ^= p[idx];
        }
    }
}

二分查找

迭代版

int binSearch(int *p, int start, int end,int find)
{
    while(start<=end)
    {
        int mid = (start+end)/2;
        if(p[mid] == find)
            return mid;
        else if(p[mid]>find)
            start = mid+1;
        else
            end = mid-1;
    } 
    return -1;
} 

递归版

int binSearch(int *p, int start, int end,int find)
{
    if(start<=end)
    {
        int mid = (start+end)/2;
        if(p[mid] == find)
            return mid;
        else if(find > p[mid])
            return binSearch(p,mid+1,end,find);
        else
            return binSearch(p,start,mid-1,find);
    } 
    else
            return -1;
} 
Last modification:October 6th, 2019 at 01:54 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment