1.堆排序
(1)堆排序的实现
//下沉操作 void siftDown(int arr[],int i,int size) { int val = arr[i]; while(i<size/2)//不能将条件写成 i <= (size-2)/2 要化成这个i<size/2 { //若不化成后面的算式，则会因为本来当i=0,size=1时不满足进行循环条件,用了一式则会满足进入循环导致错误 int child = 2*i+1; if(child +1 < size && arr[child+1] > arr[child]) { child = child +1; } if(arr[child] > val) { arr[i] = arr[child]; i = child; } else { break; } } arr[i] = val; } void HeapSort(int arr[],int size) { int n = size-1; //将一个二叉堆转化成一个大根堆 for (int i = (n-1)/2; i >= 0;i--) //如何来遍历到每一个非叶子节点呢？先找到第一个非叶子节点，然后自减即可遍历 { //下沉操作 siftDown(arr,i,size); } for (int i = n; i > 0; i--) { //交换堆顶和末尾元素 int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; //下沉操作，继续调整为大根堆 siftDown(arr,0,i); } }1.在堆排序中如何遍历到每一个非叶子节点呢？先找到最后一个非叶子节点，然后进行自减操作就可以遍历到堆中的每一个非叶子节点啦。
2.在进行下沉操作的while循环条件中，虽然条件是i要从根节点遍历到最后一个非叶子节点，即i<=(size-2)/2,但是最后要化简转化为i<size/2条件，因为当其中的i取到0，size取到1时应该不不能进入循环条件的然而由于-1/2等于0，导致了进行了循环条件使得排序错误。
(2)相关知识
特点：基于大根堆小根堆特点的排序。
堆排序的平均时间复杂度是O(nlogn),最坏时间复杂度是O(nlogn)，最好时间复杂度O(nlogn)，空键复杂度O(1),稳定性(不稳定)。
2.基数排序
(1)基数排序的实现
//基数排序 void RadixSort(int arr[],int size) { //获取数据中的最大长度 int MaxData = arr[0]; for (int i = 0; i < size; i++) { if(abs(arr[i]) > MaxData) { MaxData = abs(arr[i]); } } int len = to_string(MaxData).size(); //根据最大长度比较每个数据中的每一个位放入对应桶中 int mod = 10; int div = 1; vector<vector<int>> vec; for (int i = 0; i < len; i++,mod*=10,div*=10) { vec.resize(20); //获取每个数据中的对应位,并放入桶中 for (int j = 0; j < size; j++) { int index = (arr[j]%mod)/div+10; vec[index].push_back(arr[j]); } //将桶中的元素依次遍历放回原来序列中 int idx = 0; for(vector<int> ve:vec) { for(int v:ve) { arr[idx++] = v; } } vec.clear(); } }(2)相关知识
基数排序的平均时间复杂度是O(dn),最坏时间复杂度O(dn),最好时间复杂度O(dn),空间复杂度O(n),稳定性(稳定)。
3.哈希表
(1)线性探测哈希表的实现
//桶的状态 enum State { STATE_USING, STATE_UNUSE, STATE_DEL, }; //桶的类型 struct Bucket { Bucket(int val = 0 ,State state = STATE_UNUSE) //注意在该类中也要书写相应的构造函数，进行构造 :val_(0) ,state_(state) {} int val_; //桶中存放的数据 State state_; //桶的当前状态 }; //哈希表类 class HashTable { public: HashTable(int size = primes_[0], double loadFactor_ = 0.75) :useBucketNum_(0) , loadFactor_(loadFactor_) , primeIdx_(0) { //将用户传入的size值转化到哈希表中的相近的较大值 if (size != primes_[0]) { for (; primeIdx_ < primeSize_; primeIdx_++) { if (primes_[primeIdx_] > size) { break; } } //如果用户传入的size值太大就将其调整到素数表中的最大值，即最后一个元素值 if (primeIdx_ == primeSize_) { primeIdx_--; } } tableSize_ = primes_[primeIdx_]; table_ = new Bucket[tableSize_]; } ~HashTable() { delete[]table_; table_ = nullptr; } //插入元素 bool insert(int val) { //扩容判断 double factor = useBucketNum_ * 1.0 / tableSize_; cout << "factor:" << factor << endl; if (factor > loadFactor_) { expand(); } //通过哈希函数计算出索引值 int idx = val % tableSize_; //进行存储 int i = idx; do { if (table_[i].state_ != STATE_USING) { table_[i].val_ = val; table_[i].state_ = STATE_USING; useBucketNum_++; return true; } i = (i + 1) % tableSize_; } while (i != idx); return false; } //删除元素 bool erase(int val) { int idx = val % tableSize_; int i = idx; do { if (table_[idx].val_ == val && table_[idx].state_ == STATE_USING) { table_[idx].state_ = STATE_DEL; useBucketNum_--; } i = (i + 1) % tableSize_; } while (i != idx && table_[i].state_ != STATE_UNUSE); return true; } //查询元素 bool find(int val) { int idx = val % tableSize_; int i = idx; do { if (table_[i].val_ == val && table_[i].state_ == STATE_USING) { return true; } i = (i + 1) % tableSize_; } while (i != idx && table_[i].state_ != STATE_UNUSE); return false; } private: //扩容接口 void expand() { primeIdx_++; if (primeIdx_ == tableSize_) { throw "Hash is too large, can not expand!"; } //创建新表 Bucket* p = new Bucket[primes_[primeIdx_]]; //旧表数据哈希到新表中 for (int i = 0; i < tableSize_; i++) { if (table_[i].state_ == STATE_USING) { int idx = table_[i].val_ % primes_[primeIdx_]; int j = idx; do { if (p[j].state_ != STATE_USING) { p[j].val_ = table_[i].val_; p[j].state_ = STATE_USING; break; } j = (j + 1) % primes_[primeIdx_]; } while (j != idx); } } delete[]table_; table_ = p; tableSize_ = primes_[primeIdx_]; } Bucket* table_; //指向哈希表的指针 int tableSize_; //哈希表的大小 int useBucketNum_; //已经使用的桶的数量 double loadFactor_;//哈希表装载因子 static const int primeSize_ = 10;//素数表的大小 static int primes_[primeSize_]; //素数表 int primeIdx_; //当前哈希表使用的素数表中的素数 }; int HashTable::primes_[primeSize_] = { 3,7,23,47,97,251,443,911,1471,42773 };(2)线性探测哈希表的增加删除查找元素思路
增加： 首先通过哈希函数来计算出该值对应的索引值，然后与哈希表中该索引值位置进行对比，若该位置没有元素占用则直接将该元素放入该位置，若有元素占有则往后遍历在遍历时遇到被删除的或者没有被占用过的位置即可将该元素放入。
删除： 首先通过哈希函数来计算出该值对应的索引值，然后与哈希表中该索引值的位置元素进行对比，若该位置的值与要删除的值相等且该值的状态是没有被删除的就将该位置的状态设置为删除即可实现删除，若需要将该哈希表中所有与要删除的值相等的元素进行删除则可以继续向后遍历重复以上操作，直到遍历到的位置的状态时没有被占用过，则结束删除过程。
查找：首先通过哈希函数来计算出要查找的值对应的索引值，然后与哈希表中该索引值的位置的元素进行对比，若该位置的值与要查找的值相等且状态是没有被删除的就说明找到了，若不是则进行向后遍历重复上述比较过程，若直到遍历到的位置的状态是没有被占用过的，则说明哈希表中没有该要查找的元素，结束查找过程。
