排序分割 代码(C)

?

?

?

排序分割, 把一个数组分为, 大于k小于k等于k的三个部分.

可以使用快速排序的Partition函数, 进行处理, 把大于k的放在左边, 小于k的放在右边.

使用一个变量记录中间的位置, 则时间复杂度为O(3n/2).

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.9.18
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; int RandomInRange(int min, int max) { return rand()%(max-min+1) + min; } void Swap(int* num1, int* num2) { int tmp = *num1; *num1 = *num2; *num2 = tmp; } int PartitionK (int data[], int length, int k) { if (data == NULL || length <= 0) return -1; int small = -1; int index = 0; for (index=0; index
       
        =pos; index--) { if (data[index] > k) { small--; if (small != index) Swap(&data[small], &data[index]); } } return --small; } int main (void) { int data[] = {1, 3, 2, 5, 2, 0, 5, 2, -1, 0, 4}; int length = sizeof(data)/sizeof(data[0]); PartitionK(data, length, 2); for (int i=0; i
         
         输出:
         
?
         
?
         
1 0 -1 0 2 2 2 3 5 5 4 
 
         
 
         
 
         
?
 
         
?
 
         
?
 
         
?