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

java希尔排序实现，借用了下arr[0],欢迎拍砖：
        package sort;

import java.util.Random;

public class Test {

	public static void main(String args[]){
		Random random= new Random(6);
		int[] arr = new int[6];
		for(int i=1;i<5;i++){
			arr[i] = (int) (random.nextDouble()*100);
		}
		for(int i=1;i<arr.length;i++){
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		//insertSort(arr);
		shellInsertSort(arr);
		for(int i=1;i<arr.length;i++){
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		System.out.println("the position of first zero is :" + arr[0]);
	}
	private static void insertSort(int[] arr){
		int firstZero = arr[0];
		for(int i=2;i<arr.length;i++){
			if(firstZero == 0){
				if(arr[i-1] == 0 )firstZero = i-1;
				if(arr[i] == 0 )firstZero = i;
			}
			if(arr[i] < arr[i-1]){
				arr[0] = arr[i];
				//arr[i] = arr[i-1];
				
				int insertPos = 0;
				for(int k=i-1;k>=0;k--){
					if(arr[k] > arr[0]){
						arr[k+1] = arr[k];
					}else{
						insertPos = k+1;
						break;
					}
				}
				arr[insertPos] = arr[0];
			}
		}
		arr[0] = firstZero;
	}
	
	private static void shellInsertSort(int[] arr,int inc){
		int firstZero = arr[0];//第一个元素记录的是数字0出现的位置
		for(int i=inc+1;i<arr.length;i++){
			if(firstZero == 0){
				if(arr[i] == 0)firstZero = i;
				if(arr[i-inc] == 0)firstZero = i-inc;
			}
			if(arr[i] < arr[i-inc]){
				arr[0] = arr[i];
				
				int insertPos = i;
				for(int k=i-inc;k>=0;k-=inc){
					if(arr[k] > arr[0]){
						arr[k+inc] = arr[k];
						if(k-inc <= 0){
							insertPos = k;
						}
					}else{
						insertPos = k+inc;
						break;
					}
				}
				arr[insertPos] = arr[0];
			}
		}
		arr[0] = firstZero;
	}
	
	private static void shellInsertSort(int[] arr){
		int[] incs = {7,5,3,1};
		for(int i=0;i<incs.length;i++){
			shellInsertSort(arr,incs[i]);
		}
	}
}

 

 

	public static int A(int[] arr){
		int cur = 0;
		for(int i=0; i<arr.length; i++){
			if(arr[i]!=0)
				arr[cur++]=arr[i];
		}
		for(int i=cur; i<arr.length; i++){
			arr[i]=0;
		}
		return cur;
	}

c里面就是调用一下qsort就行了.

java实现

	static int z=0;
	public static void main(String[] args){
		int[] A={1,2,3,0,4,5,7,0,7,5,3,2,0,234,3,0,2,4};
//		int len=A.length;
//	    change(A,len-1);
//		quickSort(A,0,A.length-1);
		huawei(A);
	    for(int a:A){
	    	System.out.print(a +",");
	    } 
	    
	}
	
	public static void huawei(int[] array){
		int len=array.length;
		for(int i=0;i<len;i++){
			z++;
			if(array[i]==0){
				turns(array,i);
				break;
			}
		}
		
	}
	public static void turns(int[] array,int i){
		int len=array.length,temp;
		int j=0;
		for(;i<len-1;i++){
         	                        if(array[i+1]!=0){
        	   		sort(array,i-j,i+1);
        		        }else{
        			  j++;
           			}
		}
	}
	
	public static void sort(int[] A,int i,int j){
		int temp;
		temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	    for(int a:A){
	    } 
	}

 17次  感觉还行

 

1,2,3,4,0,5,7,0,7,5,3,2,0,234,3,0,2,4,
1,2,3,4,5,0,7,0,7,5,3,2,0,234,3,0,2,4,
1,2,3,4,5,7,0,0,7,5,3,2,0,234,3,0,2,4,
1,2,3,4,5,7,7,0,0,5,3,2,0,234,3,0,2,4,
1,2,3,4,5,7,7,5,0,0,3,2,0,234,3,0,2,4,
1,2,3,4,5,7,7,5,3,0,0,2,0,234,3,0,2,4,
1,2,3,4,5,7,7,5,3,2,0,0,0,234,3,0,2,4,
1,2,3,4,5,7,7,5,3,2,234,0,0,0,3,0,2,4,
1,2,3,4,5,7,7,5,3,2,234,3,0,0,0,0,2,4,
1,2,3,4,5,7,7,5,3,2,234,3,2,0,0,0,0,4,
1,2,3,4,5,7,7,5,3,2,234,3,2,4,0,0,0,0,

1,2,3,4,5,7,7,5,3,2,234,3,2,4,0,0,0,0,
 

	public static void maopao(int[] arra){
		
		boolean flag=false;
		int i=0;
		int swap;
		int length=arra.length-1;
		boolean nozero=false;
		boolean first=true;
		int zeroIndex=-1;
		while(i<length){
			int j=0;
			nozero=true;
			while(j<arra.length-i-1){
				if(arra[j]==0){
					if(first){
						first=false;
						zeroIndex=j;
					}
					swap=arra[j+1];
					arra[j+1]=arra[j];
					arra[j]=swap;
					nozero=false;
				
				}
				j++;
				
			}
			if(nozero){
				break;
			}
		i++;
		}
		System.out.println(zeroIndex);

	}
 

冒泡实现：主要那个排序很难理解，按大小，还是原来顺序

一个循环就搞掂了.

	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));
	}

第二个算法是错误的
多个0 相近的情况

int[] a = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };  
    int j = 0;
    int first = -1;
      
    for (int i = 0; i < a.length; ) {  
       if (a[i] == 0 )
       {
            if (first == -1)
            {
               first  = i;
            }
          i++;         
         
       }  else {
         a[j] = a[i];
         j++;
         i++;
        }
    } 
    for (; j < length; j++)
    {
       a[j] = 0;
    }

Turbo的代码有个小瑕疵，若第一个元素不为零，则逻辑会出问题。

应为：
public static void main(String[] args) {     

       int[] a = { 7, 2, 160,0, 0, 34, 21, 0, 19, 0,0,0,107 };   
 
       int j = -1;     

       for (int i = 0; i < a.length; i++) {     

           if(j==-1 && a[i]==0)
           {
               j=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)); 
}