1. 对几乎有序的数组排序
问题: 给定数组 arr, 元素个数为 N, 将其排序后元素移动的顺序不超过 K, 其中 K<<N.
分析:
1. 冒泡排序, 选择排序, 快速排序, 归并排序等排序时间复杂度与数组状态无关.
2. 插入排序复杂度为 O(N*K)
3. 改进后的堆排序可以做到 O(N*logK)
改进后的堆排序:
1. 考虑到每次移动不超过 K, 则最小的元素在 0..K 中.
2. 将 0...K 进行建小堆, 得到最小元素 arr[0].
3. 弹出堆顶, 将下一个元素不在堆内的元素置入堆顶, 下滤.
4. 重复 3, 直到无法添加新元素时, 堆的最后一个元素置入堆顶, 删除堆的最后一个元素, 下滤, 弹出堆顶.
5. 堆为空, 数组排序完成.
- vector<int> percDown(vector<int> A,int p,int r){
- int parent,child;
- int key=A[p];
- for(parent=p;parent*2+1<=r;parent=child){
- child=parent*2+1;
- if(child+1<=r&&A[child]>A[child+1])
- child++;
- if(key<=A[child]) break;
- else{
- A[parent]=A[child];
- }
- }
- A[parent]=key;
- return A;
- }
- vector<int> sortElement(vector<int> A, int n, int k) {
- // write code here
- // 建立小堆
- for(int j=(k-1)/2;j>=0;j--)
- A=percDown(A,j,k);
- vector<int> res;
- int heaplast=k;
- for(int i=0;i<n;i++){
- res.push_back(A[0]);
- int last=i+k+1;
- if(last>n-1) {
- A[0]=A[heaplast--];
- A=percDown(A,0,heaplast);
- }else{
- A[0]=A[last];
- A=percDown(A,0,k);
- }
- }
- return res;
- }
来源: http://www.bubuko.com/infodetail-2589490.html