关于算法的单独整理文章

作者:陈劲灿 编辑日期: 2017年10月11日 14:04 阅读量: 413 分类: algorithm
快速排序算法
 1.
 2.
 3.
 4.
 5.
 6.
 7.
 8.
 9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
def partition(arr, left, right):
    i = left
    j = right
    temp = arr[i]
    while i != j:
        while arr[j] >= temp and i < j: #先从右边开始查找
            j -= 1

        while arr[i] <= temp and i < j:
            i += 1

        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
    arr[left] = arr[i]
    arr[i] = temp
    return i

def quicksort(arr, left, right):
    if left < right:
        p = partition(arr, left, right)
        quicksort(arr, left, p - 1)
        quicksort(arr, p + 1, right)

if __name__ == '__main__':
    arr = [3, 2, 54, 5675, 765, 343, 213123]
    quicksort(arr, 0, 6)
    for i in arr:
        print i

hash查找相关
  1.
  2.
  3.
  4.
  5.
  6.
  7.
  8.
  9.
 10.
 11.
 12.
 13.
 14.
 15.
 16.
 17.
 18.
 19.
 20.
 21.
 22.
 23.
 24.
 25.
 26.
 27.
 28.
 29.
 30.
 31.
 32.
 33.
 34.
 35.
 36.
 37.
 38.
 39.
 40.
 41.
 42.
 43.
 44.
 45.
 46.
 47.
 48.
 49.
 50.
 51.
 52.
 53.
 54.
 55.
 56.
 57.
 58.
 59.
 60.
 61.
 62.
 63.
 64.
 65.
 66.
 67.
 68.
 69.
 70.
 71.
 72.
 73.
 74.
 75.
 76.
 77.
 78.
 79.
 80.
 81.
 82.
 83.
 84.
 85.
 86.
 87.
 88.
 89.
 90.
 91.
 92.
 93.
 94.
 95.
 96.
 97.
 98.
 99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
#include <iostream>
#include <vector>
#include <list>

template<typename KeyType, class DataType>
class HashEntry 
{
public:
    KeyType m_key;
    DataType m_data;
};

template<typename KeyType, class DataType>
class HashTable 
{
    typedef HashEntry<KeyType, DataType> Entry;

public:

    HashTable(int p_size, unsigned long int(*p_hash)(KeyType)){
        m_size = p_size;
        m_hash = p_hash;
        m_count = 0;

        m_table.resize(m_size);
    }

    void Insert(KeyType p_key, DataType p_data){
        Entry entry;
        entry.m_data = p_data;
        entry.m_key = p_key;

        int index = m_hash(p_key) % m_size;
        m_table[index].push_back(entry);

        ++m_count;
    }

    Entry* Find(KeyType p_key) {
        int index = m_hash(p_key) % m_size;

        std::list<Entry>& tmpList = m_table[index];
        for (auto entry : tmpList) {
            if (entry.m_key == p_key) {
                return &entry;
            }
        }
        return 0;
    }

    bool Remove(KeyType p_key) {
        int index = m_hash(p_key) % m_size;

        std::list<Entry>& tmpList = m_table[index];
        for (auto iter = tmpList.begin(); iter != tmpList.end(); ++iter) {
            if (iter->m_key == p_key) {
                tmpList.erase(iter);
                --m_count;
                return true;
            }
        }
        return false;
    }

    const int count() {
        return m_count;
    }

private:
    int m_size;
    int m_count;

    std::vector<std::list<Entry> > m_table;
    unsigned long int(*m_hash)(KeyType);
};

int main() {

    auto hash_func = [](int key) -> unsigned long int {
        return key;
    };
    HashTable<int, int>* hashTable = new HashTable<int, int>(10, hash_func);
    hashTable->Insert(1, 100);
    hashTable->Insert(2, 40);
    hashTable->Insert(3, 400);
    hashTable->Insert(4, 3);


    auto entry1 = hashTable->Find(3);
    if (entry1) {
        std::cout << entry1->m_data << std::endl;
    }
    else {
        std::cout << "Can't Find!!!" << std::endl;
    }

    std::cout << hashTable->Remove(1) << std::endl;
    auto entry2 = hashTable->Find(1);
    if (entry2) {
        std::cout << entry2->m_data << std::endl;
    }
    else {
        std::cout << "Can't Find!!!" << std::endl;
    }

    system("pause");
    return 0;
}

堆排序
 1.
 2.
 3.
 4.
 5.
 6.
 7.
 8.
 9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
#include <vector>
#include <iostream>

template<typename DataType>
void HeapWalkDown(  std::vector<DataType>& p_array, 
                    int p_index, 
                    int p_maxIndex, 
                    int(*p_compare)(DataType, DataType)) 
{
    int parent = p_index;
    int child = p_index * 2;
    DataType tmpData = p_array[parent - 1];

    while (child <= p_maxIndex) {
        if (child < p_maxIndex) {
            if (p_compare(p_array[child - 1], p_array[child]) < 0) {
                ++child;
            }
        }

        if (p_compare(tmpData, p_array[child - 1]) < 0) {
            p_array[parent - 1] = p_array[child - 1];
            parent = child;
            child *= 2;
        }else
            break;
    }
    p_array[parent - 1] = tmpData;
}

template<typename DataType>
void HeadSort(std::vector<DataType>& p_array, int(*p_compare)(DataType, DataType)) {
    int maxSize = p_array.size();
    int rightIndex = maxSize / 2;

    for (int i = rightIndex; i > 0; --i) {
        HeapWalkDown(p_array, i, maxSize, p_compare);
    }

    while (maxSize > 0) {
        DataType tmpData = p_array[0];
        p_array[0] = p_array[maxSize - 1];
        p_array[maxSize - 1] = tmpData;

        maxSize--;
        HeapWalkDown(p_array, 1, maxSize, p_compare);
    }
}

int compare(int a, int b) {
    if (a > b)return 1;
    if (a < b)return -1;
    return 0;
}

int main()
{
    std::vector<int> vec({434, 34,3, 2312, 32, 32,3435,436, 657, 87,6897,890});
    HeadSort(vec, compare);

    for (auto v : vec) {
        std::cout << v << std::endl;
    }

    system("pause");
    return 0;
}

桶排序
 1.
 2.
 3.
 4.
 5.
 6.
 7.
 8.
 9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
#include <iostream>
#include <algorithm>
#include <vector>

void BucketSort(int arr[], int n) {
    std::vector<std::vector<int> > b;
    b.resize(n);

    //放置元素
    for (int i = 0; i < n; ++i) {
        int bi = arr[i] / 10;
        b[bi].push_back(arr[i]);
    }

    //对每一段进行排序
    for (int i = 0; i < n; ++i)
        sort(b[i].begin(), b[i].end());

    //连接
    int index = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < b[i].size(); ++j)
            arr[index++] = b[i][j];
}

int main() {
    int arr[] = { 32, 43, 52, 32, 23, 14, 68 };
    int n = sizeof(arr) / sizeof(arr[0]);
    BucketSort(arr, n);

    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << std::endl;

    system("pause");
    return 0;
}

上一篇
下一篇
单独开一篇关于C++相关知识的巩固
TypeScript的入门-环境搭建