数组查找、冒泡排序、快速排序（一）

原创

玖叁叁

发布于 2023-05-10 13:45:59

3690

发布于 2023-05-10 13:45:59

文章被收录于专栏：玖叁叁玖叁叁

数组查找

数组查找是一种常见的算法，用于在一个已排序或未排序的数组中查找指定的值。常用的数组查找算法包括线性查找、二分查找、哈希表查找等。

线性查找

线性查找是最简单的一种查找算法，也称为顺序查找。它的实现非常简单，只需要从数组的第一个元素开始逐个遍历，直到找到目标元素或者遍历到数组的最后一个元素为止。如果找到了目标元素，就返回它的下标；否则返回-1，表示未找到。

下面是一个实现线性查找的示例代码：

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

二分查找

二分查找是一种针对有序数组的查找算法，也称为折半查找。它的实现原理是：首先确定数组的中间元素，然后将待查找的值与中间元素进行比较，如果相等则返回中间元素的下标；如果待查找的值比中间元素小，则在数组的左半部分继续查找；如果待查找的值比中间元素大，则在数组的右半部分继续查找。每次查找都可以将待查找的区间缩小一半，因此时间复杂度为O(log n)。

下面是一个实现二分查找的示例代码：

int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

哈希表查找

哈希表是一种基于哈希函数实现的数据结构，可以快速地进行查找、插入、删除等操作。哈希表的实现原理是：首先将关键字通过哈希函数映射到一个地址上，然后在该地址上进行查找、插入、删除等操作。由于哈希函数的设计非常重要，所以不同的哈希函数对于同一个数据集的性能表现也有很大的差异。

下面是一个实现哈希表查找的示例代码：

class HashTable {
private:
    vector<pair<int, int>> data;
    int capacity;
    int hash(int key) {
        return key % capacity;
    }
public:
    HashTable(int capacity) {
        this->capacity = capacity;
        data.resize(capacity);
    }
    void put(int key, int value) {
        int index = hash(key);
        while (data[index].first != 0 && data[index].first != key) {
            index = (index + 1) % capacity;
        }
        data[index] = {key, value};
    }
    int get(int key) {
        int index = hash(key);
        while (data[index].first != 0 && data[index].first != key) {
            index = (index + 1) % capacity;
        }
        if (data[index].first == key) {
            return data[index].second;
        }
        return -1;
    }
};

以上是三种常用的数组查找算法，它们在不同的场景下都有着各自的优缺点，选择合适的算法可以大大提高程序的效率。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

登录后参与评论

0 条评论

热度