特殊数组排序

给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
数组排序

从1开始，往下找k个数，把最小的和1调换.
以此类推
感觉应该是这样

这样复杂度就是O（K * N）

这样复杂度就是O（K * N）
Imbalism 发表于 2011-9-24 13:39

    用大小为k+1的堆， 每次pop一个压入一个

1. 
   
2. bool Pred(int a, int b)
   
3. {
   
4.         return a > b;
   
5. }
   
6. 
   
7. void ReSort(int a[], int n, int k)
   
8. {
   
9.         assert(a && n > 0 && k > 0 && k < n);
   
10. 
    
11.         int* pHeap = new int[k];
    
12.         for (int i = 0; i < k; i++)
    
13.                 pHeap[i] = a[i];
    
14. 
    
15.         make_heap(pHeap, pHeap + k, Pred);
    
16. 
    
17.         for (int i = k; i < n; i++)
    
18.         {
    
19.                 pop_heap(pHeap, pHeap+k, Pred);
    
20.                 a[i-k] = pHeap[k-1];
    
21.                 pHeap[k-1] = a[i];
    
22.                 push_heap(pHeap, pHeap+k, Pred);
    
23.         }
    
24. 
    
25.         sort_heap(pHeap, pHeap+k, Pred);
    
26. 
    
27.         for (int j = k; j >= 1; j--)
    
28.                 a[n - j] = pHeap[j - 1];
    
29.         delete []pHeap;
    
30. }
    

复制代码

回复 1# wwwyhx


    我首先想到的是希尔排序。。。
但排序这种东西应该是殊途同归吧。。。
难道最优的复杂度是

O(n/K* log n)么。。。

最简单的应该是冒泡吧。。。
比如最大的数肯定在前K+1个里面，那就对前k+1个数冒泡一趟
冒出来第一个后，第二大的数肯定在2到K+2里面。。。
O(n*k)

最简单的应该是冒泡吧。。。
比如最大的数肯定在前K+1个里面，那就对前k+1个数冒泡一趟
冒出来第一个后，第二大的数肯定在2到K+2里面。。。
O(n*k)
ilhrx 发表于 2011-10-3 13:35

    没必要排序啊,可以参考2楼的,每次调换以后数组还是保留那个k范围的性质,但是数组缩小了一个,是收敛的

回复 7# wwwyhx

二楼应该跟我的意思是一样的。。。
就是前k个里面就能找到最小的
然后依次类推。

回复 8# ilhrx
en ,lou zhu de fangfa hen qiao miao, wo da yi le