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

时间:2022-02-02作者:klpeng分类:IT综合浏览:1025评论:0

        试设计一个算法, 使得在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;
	
}

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢