切割排序 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

排序切割, 把一个数组分为, 大于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

版权声明：本文博客原创文章，博客，未经同意，不得转载。