将所有取负值的关键字排在所有取正值(非负值)的关键字之前

        试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的关键字排在所有取正值(非负值)的关键字之前。

        快排的思想，从n-1开始依次递减找到一个小于0的，从0开始依次递增找到一个大于等于0的，交换。就OK了。

int partition(int num[],int low,int high){
	
    while(low<high){
		while(low<high&&num[high]>=0){
			high--;
		}
		while(low<high&&num[low]<0){
			low++;
		}
		if(low<high){
			int temp = num[high];
			num[high]=num[low];
			num[low] = num[high];
            low++;
            high--;
		}
		
	}
	
	return low;
	
}

打赏

微信扫一扫，打赏作者吧～