论坛数组排序方法总结

原题：

有一个整数数组，有很多 个元素，如何把零移到最前面，要求算法效率要高。如 0,1,72,3,0,5,9,0,6,51,0,3。移动后为0,0,0,0,1,72,3,5,9,6,51,3。不知JE的牛人们有什么高效的算 法。

补充： 非零元素的位置不能改变的。

地址： http://www.iteye.com/topic/684511

本人笨拙：

1、 自己写的算法：利用数组copy，倒序插入。论坛上也有哥们提到过此算法。代码如下

public class test8 {
    public static void main(String...strings){
        int[] arr1={0,1,72,3,0,5,9,0,6,51,0,3};
        int[] arr2=new int[arr1.length];
        int index1=arr1.length;
        int index2=arr1.length;
        while(index1>0){
            if(arr1[--index1]!=0){
                arr2[--index2]=arr1[index1];
            }
        }
        for(int i=0;i<arr1.length;i++){
            System.out.print(arr2[i]+",");
        }
    }
}

分析：个人感觉速度上可以，占用空间。其中倒序思路与数组紧凑法类似。

2.

数组紧凑法：学习中。。
public class test9 {
     private static int[] array={0,1,72,3,0,5,9,0,6,51,0,3};
      public static int[] move(int [] array) 
       { 
            //自右向左扫描，将所有非零元素紧凑到右侧 
            int low,high; 
           for(low = array.length-1,high=low ; low>=0;low--) 
               if(array[low]!=0) 
                { 
                    array[high] = array[low]; 
                    high -- ;//更新紧凑序列的最左侧元素 
               } 
           //将余下所有元素全部置为0 
           for(;high>=0 ; high--) 
               array[high] = 0; 
           return array; 
       } 
      public static void main(String...strings){
          move(array);
          for(int i=0;i<array.length;i++){
              System.out.print(array[i]+",");
          }
         
      }
}

3：

public class test10 {
private static int[] array = { 0, 1, 72, 3, 0, 5, 9, 0, 6, 51, 0, 3 };

    static void frontzero(int array[]) {
        int zero = array.length - 1, nozero = zero;
        while (nozero >= 0) {

            if (array[zero] == 0 && array[nozero] != 0) {
                array[zero] = array[nozero];
                array[nozero] = 0;
                zero--;
            }
            if (array[zero] != 0)
                zero--;
            if (array[nozero] == 0)
                nozero--;

            if (zero < nozero)
                nozero = zero - 1;
        }
    }

    public static void main(String... strings) {
        frontzero(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }

    }
}
方法 4

public class test11 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] array = new int[] { 0, 1, 72, 73, 0, 5, 9, 0, 6, 51, 0, 0 };
        array = moveZero(array);
        for (int k = 0; k < array.length; k++) {
            System.out.print(array[k]+",");
        }
    }
    /**
     * 从右边边开始找零，如果找到0，就把前面的元素都往后面挪一个位置，并且第一个元素补零，没有的话，就往左边找，理论上需要循环 length-
     * zeroNum 次
     *
     * @param array
     * @return
     */
    public static int[] moveZero(int[] array) {
        // 统计零的个数
        int zeroNum = 0;
        for (int i = array.length - 1; i > 0;) {
            if (array[i] == 0) {
                zeroNum++;
                // 零前面的元素都往后面移动下
                for (int j = i; j > 0; j--) {
                    array[j] = array[j - 1];
                }
                // 移动完后，前面补零
                array[0] = 0;
                if (i < zeroNum) {
                    // 说明前面的都是0了，不用再找了
                    break;
                }
            } else {
                // 没有为零，移动下标，再往前找
                i--;
            }
        }
        return array;
    }

}

方法 5

public class test12 {
      public static void main(String[] args) 
          { 
              int[] array = new int[] { 0, 1, 72, 3, 0, 5, 9, 0, 6, 51, 0, 3, 0, -5, 9, 0, 8, -34, 0, -1 }; 
              int first = 0; 
              System.out.println(Arrays.toString(array)); 
              for (int i = 0; i < array.length; i++) 
              { 
                  if (array[i] == 0) 
                  { 
                      if (first < i) 
                      { 
                          for (int j = i - 1; j >= first; j--) 
                          { 
                              array[j + 1] = array[j]; 
                          } 
                          array[first] = 0; 
                          first++; 
                      } 
                  } 
              } 
              System.out.println(Arrays.toString(array)); 
          } 
}
下班了，就现不错分析了，先mark下，等回头再总结下。上面的代码中感觉有冒泡和快速的思想在里面

上面的算法有好有坏，不做分析。关键是学习大家思路。不同的场景应用不同的算法会更高效。

评论

1 楼 bighero3 2011-01-19  

很好。值得收藏