使用快排一次划分求第k小、使用优先级队列、使用堆

快排

#include
using namespace std;/**************************************
*
* Partition() 快排的一次划分函数
*
*/// 把小的插入头部位置&＃xff0c;可用于链表
int Partition(int* ar, int left, int right) {int i &＃61; left - 1, j &＃61; left;int tmp &＃61; ar[j];while (j <&＃61; right) {if (ar[j] <&＃61; tmp) {std::swap(ar[i &＃43; 1], ar[j]);i &＃43;&＃61; 1;}j &＃43;&＃61; 1;}std::swap(ar[left], ar[i]);return i;
}// 双指针单方向推进
int Partition1(int* ar, int left, int right)
{int i &＃61; left, j &＃61; left &＃43; 1;int tmp &＃61; ar[i];while (i < right && j < right){while (j <&＃61; right && ar[j] <&＃61; tmp) j&＃43;&＃43;; // 大值if (j > right) break;i &＃61; j &＃43; 1;while (i <&＃61; right && ar[i] > tmp) i&＃43;&＃43;; // j后小值if (i > right) break;std::swap(ar[i], ar[j]);//j&＃43;&＃43;;}std::swap(ar[j - 1], ar[left]);return j - 1;
}// 双指针&＃xff0c;两边夹逼推进
int Partition2(int* ar, int left, int right)
{int i &＃61; left, j &＃61; right;int tmp &＃61; ar[i];while (i < j){while (i < j && ar[j] > tmp) j--;if (i >&＃61; j) break;while (i < j && ar[i] <&＃61; tmp) i&＃43;&＃43;;if (i >&＃61; j) break;std::swap(ar[i], ar[j]);}std::swap(ar[i], ar[left]);return i;
}// 快排中间层&＃xff0c;递归调用一次划分
void QuickPass(int* ar, int left, int right)
{if (left < right){int pos &＃61; Partition(ar, left, right);QuickPass(ar, 0, pos - 1);QuickPass(ar, pos &＃43; 1, right);}
}
// 快排接口
void QuickSort(int* ar, int n)
{if (nullptr &＃61;&＃61; ar || n < 1) return;QuickPass(ar, 0, n - 1);
}int main()
{int arr[] &＃61; { 4,5,2,3,4,4,3,1,7,8,4,9,10,6 };QuickSort(arr, sizeof(arr) / sizeof(arr[0]));for (int a : arr)std::cout << a << &＃39; &＃39;;std::cout << std::endl;return 0;
}

有关快排优化&＃xff1a;参考&＃xff1a;万字长文带你走进快速排序的前世今生【拓跋阿秀】

1. 非递归
2. 优化基准选取位置&＃xff0c;如三位取中法等
3. 设定一个阈值&＃xff0c;在阈值范围内使用插入排序&＃xff08;插入排序在元素比较少时效率最高&＃xff09;
4. 三向切分。

使用快排的的一次划分&＃xff0c;我们可以实现寻找无序数列中的第K小。

#include
using namespace std;
int OnePartition(int* ar, int left, int right)
{int midVal &＃61; ar[left]; // 基准while (left < right){while (left < right){if (ar[right] >&＃61; midVal) right--;else {swap(ar[right], ar[left&＃43;&＃43;]); break;}}while (left < right){if (ar[left] <&＃61; midVal) left&＃43;&＃43;;else {swap(ar[left], ar[right--]); break;}}}return left;
}
int Select_K(int* ar, int left, int right, int pos)
{int i &＃61; OnePartition(ar, left, right);if (i < pos - 1) i &＃61; Select_K(ar, i &＃43; 1, right, pos); // 右边else if (i > pos - 1) i &＃61; Select_K(ar, left, i - 1, pos); //左边else return ar[i];
}int main()
{int arr[] &＃61; { 67,12,89,23,90,100 ,34,78,56,45 };int n &＃61; sizeof(arr) / sizeof(arr[0]);//cout <for (int i &＃61; 1; i < 11; i&＃43;&＃43;)cout << i << ": " << Select_K(arr, 0, n - 1, i) << endl;return 0;
}/*输出&＃xff1a;1: 122: 233: 344: 455: 566: 677: 788: 899: 9010: 100
*/

除此之外&＃xff0c;我们可以使用优先级队列&＃xff0c;或直接使用数据结构堆。

优先级队列&＃xff0c;大数优先级高&＃xff08;底层大根堆实现&＃xff09;。使用小数优先级高的方式也可以实现下列算法。

#include
#include
#include
using namespace std;// 第k大
int KthLargest(int arr[], int n, int k)
{if (nullptr &＃61;&＃61; arr || n <&＃61; 0 || k > n) return -1;//priority_queue pq; // 默认产生大根堆,数据大的优先priority_queue<int, vector<int>, less<int>> pq;for (int i &＃61; 0; i < n; i&＃43;&＃43;){pq.push(arr[i]); // 把数据加入优先级队列中}// 把第1大&＃xff0c;第2大&＃xff0c;第3....&＃xff0c;到第k次时为第k大while (k > 1){pq.pop();k--;}return pq.top();
}
// 第k小
int KthSmall(int arr[], int n, int k)
{if (nullptr &＃61;&＃61; arr || n <&＃61; 0 || k > n) return -1;priority_queue<int> pq;for (int i &＃61; 0; i < n; i&＃43;&＃43;){pq.push(arr[i]); // 把数据加入优先级队列中}k &＃61; n - k &＃43; 1; // 求第k小&＃xff0c;把n-k&＃43;1的大数据出队&＃xff0c;剩下的就是第k小while (k > 1){pq.pop();k--;}return pq.top();
}int main()
{int arr[] &＃61; { 67,12,89,23,90,100 ,34,78,56,45 };int n &＃61; sizeof(arr) / sizeof(arr[0]);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)cout << i << ":\t small " << KthSmall(arr, n, i)<< "\t big" << KthLargest(arr, n, i) << endl;return 0;
}
/*输出&＃xff1a;1: small 12 big1002: small 23 big903: small 34 big894: small 45 big785: small 56 big676: small 67 big567: small 78 big458: small 89 big349: small 90 big2310: small 100 big12*/

直接使用数据结构堆。

#include
#include
#include
using namespace std;// 第k大
int KthLargest(int arr[], int n, int k)
{if (nullptr &＃61;&＃61; arr || n <&＃61; 0 || k > n) return -1;// std::make_heap(arr, arr &＃43; n); // 在一个迭代器范围内构造一个堆&＃xff08;默认最大堆&＃xff09;std::make_heap(arr, arr &＃43; n, less<int>()); // 创建大根堆while (k > 1){pop_heap(arr, arr &＃43; n); // 弹出堆顶元素&＃xff0c;并把它放到末尾位置n--;make_heap(arr, arr &＃43; n, less<int>()); // 将剩余元素调整为堆k--;}return arr[0];
}
// 第k小
int KthSmall(int arr[], int n, int k)
{if (nullptr &＃61;&＃61; arr || n <&＃61; 0 || k > n) return -1;//n &＃61; n - 1; // 将长度变成下标std::make_heap(arr, arr &＃43; n, greater<int>()); // 创建小根堆while (k > 1){pop_heap(arr, arr &＃43; n); // 弹出堆顶元素&＃xff0c;并把它放到末尾位置n--;make_heap(arr, arr &＃43; n, greater<int>()); // 将剩余元素调整为堆k--;}return arr[0];
}int main()
{int arr[] &＃61; { 67,12,89,23,90,100 ,34,78,56,45 };int brr[] &＃61; { 67,12,89,23,90,100 ,34,78,56,45 };int n &＃61; sizeof(arr) / sizeof(arr[0]);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)cout << i << ":\t small " << KthSmall(arr, n, i)<< "\t big" << KthLargest(arr, n, i) << endl;return 0;
}/*输出&＃xff1a;1: small 12 big1002: small 23 big903: small 34 big894: small 45 big785: small 56 big676: small 67 big567: small 78 big458: small 89 big349: small 90 big2310: small 100 big12
*/