【8.04更新】上海华为的一道关于指针方面的编程题

int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至 
数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)

#include <iostream>
using namespace std;
/*
 * int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至
 * 数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)
 *
 */
int Func(int *A, int nSize) {
	int index = (nSize - 1);
	//由后往前
	while ((nSize--) >= 0) {
		if (*(A + nSize) == 0) {//为零，直接下标前移
			index = nSize;
			continue;
		}
		//否则拿前面的数据与自己相比较
		for (int i = 0; i < nSize; i++) {
			int last = *(A + nSize);
			int pre = *(A + i);
			if (pre == 0) {//直接交换,跳出for循环
				*(A + nSize) = pre;
				*(A + i) = last;
				index = nSize;
				break;
			}
			if (last > pre) {//排序交换
				*(A + nSize) = pre;
				*(A + i) = last;
				;//swap
			}
		}
	}
	return index;
}

int main(void) {
	const int intSize = 10;
	int A[intSize] = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };
	cout << "The return value= " << Func(&A[0], intSize);
	return 0;
}

public static void main(String[] args) {   
    int[] a = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };   
    int j = 0;   
    for (int i = 0; i < a.length; i++) {   
        if (a[i] == 0 && i != a.length - 1 && a[i + 1] != 0) {   
            a[j++] = a[i + 1];   
            a[i + 1] = 0;   
        }   
    }   
  
    System.out.println(Arrays.toString(a));   
}  

好像这样做是最好的，在Java中的话就是写个实现Compartor接口的类，不过就是在返回值的时候，需要遍历一下数组。

不用遍历也行~ 只要在比较的时候记录下0的数量就行了。

     就会java的觉得这里Compartor接口也可以用。怎么说呢。java的Compartor接口就是比较大小。排序有jdk负责。我的思路是写两个函数。

     一个int Func(int *A, int nSize) 只负责排序。一个 compare方法。负责排序的具体实现。这样可能好很多。

int *p1, *p2;
p1 = p2 = A;
// 初始状态是p1和p2从第一个元素开始，p1移动到第一个0元素，p2移动到p1后第一个非0的元素
// 中间状态是p1指向第一个是0的元素，p2指向p1后第一个非零元素
// 比如 ....000000...02304.....
//          p1        p2
// 然后交换一下
// 结束时p2在数组末尾
// ......23000000.....000
//         p1           p2
// 这样一次遍历就够了
// 移动p1到第一个0值
while(p1 < A + nSize && *p1 != 0) p1++;
if(p1 == A + nSize) return;
p2 = p1;
while(p2 < A + nSize)
{
    // 移动p1到第一个0值
    while(p1 < A + nSize && *p1 != 0) p1++;
    if(p1 == A + nSize) return;
    // 移动p2到p1后的第一个非0值
    while(p2 < A + nSize && *p2 == 0) p2++;
    if(p2 == A + nSize) return;
    // 交换一下位置
    *p1 = *p2;
    *p2 = 0;
}

package com.gpdi.strcom;

import com.gpdi.sort.*;

/**
 * @author Administrator
 *
 */
public class Test01 {
	
	private static  int [] DATA = {0,1,0,0,3,4,5,0,0,0,0,10,99,32754,0,0};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		moveZero(DATA,DATA.length);
		for (int var : DATA	 ){
			System.out.println(var);
		}
	}
	
	
	private static void moveZero(int [] data,int size){
		for (int i =0 ; i<size; i++){
			while( 0 != data[i])
			{
				i++;
			}
			int j = i;
			while ((j<size)&&(0==data[j])) {
				j++;
			}
			if ((j>=i)&&(i<size)&&(j<size)) {
				SortUtil.sortSwap(data, i, j);
			}
		}
	}
}