计数、基数、桶排序分析,顺序、对分查找实现:数据结构与算法分析

不基于比较、线性时间运行的排序算法:

Counting sort计数排序:O(n+k) 共n个元素 整数范围0-k 稳定
将元素作为辅助数组的下标,统计每个对应元素出现的次数,遍历数组元素输出。
该数组的每一个下标位置的值代表了数组中对应整数出现的次数。
Radix sort基数排序:O(t*(n+k)) t为整数的位数 子过程可以是计数排序 稳定
把待排序记录分解成个位(第一位)、十位(第二位)….然后分别以第一位、第二位…对整个序列进行计数排序。这样的话分解出来的每一位不超过9,即用计数排序序列中最大值是9。
Bucket sort桶排序:O(n+M),最坏到O(n^2),M是桶的个数,n是待排序元素的个数,稳定
将区间划分为m个等长的子区间。然后,将各个元素按照自己所属的区间放入相应的桶中,将每个桶的元素排好序,依次输出各个桶内的元素,就得到了有序的元素序列。
桶排序实际上只需要遍历一遍所有的待排序元素,然后依次放入指定的位置,如果加上输出排序的时间,那么需要遍历所有的桶,时间复杂度为O(n+m)。

查找算法:

顺序查找O(N)

int seqSearch(int *array, int low, int high, int key)
{
    for (int i = low; i < high; i++)
    {
        if (array[i] == key)
            return i;
    }
    return -1;
}

对分查找(折半查找) 适用于有序数组 O(logN)

int binarySearch(int *array, int low, int high, int key)
{
    while (low <= high)
    {
        //从中间划分
        //mid如果不是整数,则直接向下取整,不会影响查找结果
        int mid = (low + high) / 2;
        //正好是中间这个数
        if (key == array[mid])
            return mid;
        //数比中间的数大,则缩小范围到后半部分
        else if (key > array[mid])
            low = mid + 1;
        //数比中间的数小,则缩小范围到前半部分
        else
            high = mid - 1;
    }
    return -1;
}

相关内容:
数据结构复习笔记与一些总结:https://www.svip.tech/archives/907
基于比较、渐进最优的排序算法(插入、希尔、选择、堆、冒泡、快速、归并排序实现):https://www.svip.tech/archives/1152
不基于比较、线性时间运行的排序算法(计数、基数、桶排序分析)和顺序、对分查找实现:https://www.svip.tech/archives/1165
各种算法特性与复杂度总结:https://www.svip.tech/archives/1174

发表评论

电子邮件地址不会被公开。 必填项已用*标注