排序算法的Java实现全攻略

Collections.sort()

 

Java的排序可以用Collections.sort() 排序函数实现。
用Collections.sort方法对list排序有两种方法：
第一种是list中的对象实现Comparable接口，如下：

/**
* 根据order对User排序
*/
public class User implements Comparable<User>{
  private String name;
  private Integer order;
  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public Integer getOrder() {
    return order;
  }
  public void setOrder(Integer order) {
    this.order = order;
  }
  public int compareTo(User arg0) {
    return this.getOrder().compareTo(arg0.getOrder());
  }
}

测试一下：

public class Test{

  public static void main(String[] args) {
    User user1 = new User();
    user1.setName("a");
    user1.setOrder(1);
    User user2 = new User();
    user2.setName("b");
    user2.setOrder(2);
    List<User> list = new ArrayList<User>();
    //此处add user2再add user1
    list.add(user2);
    list.add(user1);
    Collections.sort(list);
    for(User u : list){
      System.out.println(u.getName());
    }
  }
}

输出结果如下

a
b

第二种方法是根据Collections.sort重载方法来实现，例如：

/**
* 根据order对User排序
*/
public class User { //此处无需实现Comparable接口
  private String name;
  private Integer order;
  public String getName() {
    return name;
  }
  public void setName(String name) {
    this.name = name;
  }
  public Integer getOrder() {
    return order;
  }
  public void setOrder(Integer order) {
    this.order = order;
  }
}

主类中这样写即可：

public class Test{
  public static void main(String[] args) {
    User user1 = new User();
    user1.setName("a");
    user1.setOrder(1);
    User user2 = new User();
    user2.setName("b");
    user2.setOrder(2);
    List<User> list = new ArrayList<User>();
    list.add(user2);
    list.add(user1);

    Collections.sort(list,new Comparator<User>(){
      public int compare(User arg0, User arg1) {
        return arg0.getOrder().compareTo(arg1.getOrder());
      }
    });
    for(User u : list){
      System.out.println(u.getName());
    }
  }
}

输出结果如下

a
b

前者代码结构简单，但是只能根据固定的属性排序，后者灵活，可以临时指定排序项，但是代码不够简洁

择优用之。

 

常用排序算法
下面来看几种经典排序算法的Java代码实践：

冒泡排序

   

public static void bubbleSort(int A[], int n) {
   int i, j;

   for (i = 0; i < n - 1; i ++) {
     for (j = 0; j < n - i - 1; j ++) {
       if (A[j] > A[j + 1]) {
         A[j] = A[j] ^ A[j + 1];
         A[j + 1] = A[j] ^ A[j + 1];
         A[j] = A[j] ^ A[j + 1];
       }
     }
   }
 }

 

直接插入排序

    

public static void insertSort(int A[], int n) {
    int i, j, tmp;

    for (i = 1; i < n; i++) {
      tmp = A[i];

      for (j = i - 1; j >= 0; j--) {
        if (A[j] > tmp) {
          A[j + 1] = A[j];
        } else {
          break;
        }
      }

      A[j + 1] = tmp;
    }
  }

 

直接选择排序

    

public static void selectSort(int A[], int n) {
    int i, j, loc;

    for (i = 0; i < n; i++) {
      loc = i;

      for (j = i + 1; j < n; j++) {
        if (A[j] < A[loc]) {
          loc = j;
        }
      }

      if (loc != i) {
        A[i] = A[i] ^ A[loc];
        A[loc] = A[i] ^ A[loc];
        A[i] = A[i] ^ A[loc];
      }
    }
  }

 

堆排序

 

/**
 * 堆排序（从小到大）
 *
 * @param A
 * @param n
 */
public static void heapSort(int A[], int n) {
  int tmp;

  // 构建大根堆
  buildMaxHeap(A, n);

  for (int j = n - 1; j >= 1; j--) {
    tmp = A[0];
    A[0] = A[j];
    A[j] = tmp;

    maxheapIfy(A, 0, j);
  }
}

/**
 * 构建大根堆
 *
 * @param A
 * @param n
 */
private static void buildMaxHeap(int A[], int n) {
  for (int i = (n - 2) / 2; i >= 0; i--) {
    maxheapIfy(A, i, n);
  }
}

/**
 * 维护从下标i开始的最大堆
 *
 * @param A
 * @param i
 * @param n
 */
private static void maxheapIfy(int A[], int i, int n) {
  int left, right, loc;

  while (i < n) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    loc = i;

    if (left < n && A[left] > A[i]) {
      i = left;
    }

    if (right < n && A[right] > A[i]) {
      i = right;
    }

    if (loc != i) {
      A[i] = A[loc] ^ A[i];
      A[loc] = A[loc] ^ A[i];
      A[i] = A[loc] ^ A[i];
    } else {
      break;
    }
  }
}

 

快速排序

 

public static void quickSort(int A[], int bt, int ed) {
  if (bt < ed) {
    int pivot = pivotPartition(A, bt, ed);

    quickSort(A, bt, pivot - 1);

    quickSort(A, pivot + 1, ed);
  }
}

private static void swapVar(int A[], int bt, int ed) {
  int mid = bt + (ed - bt) / 2;

  if (mid != bt) {
    A[bt] = A[bt] ^ A[mid];
    A[mid] = A[bt] ^ A[mid];
    A[bt] = A[bt] ^ A[mid];
  }
}

private static int pivotPartition(int A[], int bt, int ed) {
  // 取中间值作为stand，防止数组有序出现O(n^2)情况
  swapVar(A, bt, ed);

  int stand = A[bt];

  while (bt < ed) {
    while (bt < ed && A[ed] >= stand) {
      ed--;
    }
    if (bt < ed) {
      A[bt++] = A[ed];
    }

    while (bt < ed && A[bt] <= stand) {
      bt++;
    }
    if (bt < ed) {
      A[ed--] = A[bt];
    }
  }

  A[bt] = stand;

  return bt;
}

归并排序

  

public static void mergeSort(int A[], int bt, int ed) {
   if (bt < ed) {
     int mid = bt + (ed - bt) / 2;

     mergeSort(A, bt, mid);

     mergeSort(A, mid + 1, ed);

     mergeArray(A, bt, mid, ed);
   }
 }

 private static void mergeArray(int A[], int bt, int mid, int ed) {
   int i, j, k, len = ed - bt + 1;
   int tmp[] = new int[len];

   for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
     if (A[i] <= A[j]) {
       tmp[k] = A[i++];
     } else {
       tmp[k] = A[j++];
     }
   }

   while (i <= mid) {
     tmp[k++] = A[i++];
   }

   while (j <= ed) {
     tmp[k++] = A[j++];
   }

   for (i = 0; i < k; i++) {
     A[bt + i] = tmp[i];
   }
 }

 

测试程序

 来将以上算法归纳总结一下：

import java.util.Scanner;

 public class JavaSort {
   public static void main(String args[]) {
     Scanner cin = new Scanner(System.in);

     int A[], n;

     while (cin.hasNext()) {
       n = cin.nextInt();
       A = new int[n];

       for (int i = 0; i < n; i++) {
         A[i] = cin.nextInt();
       }

       // bubbleSort(A, n);

       // insertSort(A, n);

       // selectSort(A, n);

       // heapSort(A, n);

       // quickSort(A, 0, n - 1);

       mergeSort(A, 0, n - 1);

       printArr(A);
     }
   }

   /**
    * 归并排序
    *
    * @param A
    * @param bt
    * @param ed
    */
   public static void mergeSort(int A[], int bt, int ed) {
     if (bt < ed) {
       int mid = bt + (ed - bt) / 2;

       mergeSort(A, bt, mid);

       mergeSort(A, mid + 1, ed);

       mergeArray(A, bt, mid, ed);
     }
   }

   /**
    * 合并数组
    *
    * @param A
    * @param bt
    * @param mid
    * @param ed
    */
   private static void mergeArray(int A[], int bt, int mid, int ed) {
     int i, j, k, len = ed - bt + 1;
     int tmp[] = new int[len];

     for (i = bt, j = mid + 1, k = 0; i <= mid && j <= ed; k++) {
       if (A[i] <= A[j]) {
         tmp[k] = A[i++];
       } else {
         tmp[k] = A[j++];
       }
     }

     while (i <= mid) {
       tmp[k++] = A[i++];
     }

     while (j <= ed) {
       tmp[k++] = A[j++];
     }

     for (i = 0; i < k; i++) {
       A[bt + i] = tmp[i];
     }
   }

   /**
    * 快速排序
    *
    * @param A
    * @param bt
    * @param ed
    */
   public static void quickSort(int A[], int bt, int ed) {
     if (bt < ed) {
       int pivot = pivotPartition(A, bt, ed);

       quickSort(A, bt, pivot - 1);

       quickSort(A, pivot + 1, ed);
     }
   }

   private static void swapVar(int A[], int bt, int ed) {
     int mid = bt + (ed - bt) / 2;

     if (mid != bt) {
       A[bt] = A[bt] ^ A[mid];
       A[mid] = A[bt] ^ A[mid];
       A[bt] = A[bt] ^ A[mid];
     }
   }

   /**
    * 快排寻找基准点位置
    *
    * @param A
    * @param bt
    * @param ed
    * @return
    */
   private static int pivotPartition(int A[], int bt, int ed) {
     // 取中间值作为stand，防止数组有序出现O(n^2)情况
     swapVar(A, bt, ed);

     int stand = A[bt];

     while (bt < ed) {
       while (bt < ed && A[ed] >= stand) {
         ed--;
       }
       if (bt < ed) {
         A[bt++] = A[ed];
       }

       while (bt < ed && A[bt] <= stand) {
         bt++;
       }
       if (bt < ed) {
         A[ed--] = A[bt];
       }
     }

     A[bt] = stand;

     return bt;
   }

   /**
    * 堆排序（从小到大）
    *
    * @param A
    * @param n
    */
   public static void heapSort(int A[], int n) {
     int tmp;

     // 构建大根堆
     buildMaxHeap(A, n);

     for (int j = n - 1; j >= 1; j--) {
       tmp = A[0];
       A[0] = A[j];
       A[j] = tmp;

       maxheapIfy(A, 0, j);
     }
   }

   /**
    * 构建大根堆
    *
    * @param A
    * @param n
    */
   private static void buildMaxHeap(int A[], int n) {
     for (int i = (n - 2) / 2; i >= 0; i--) {
       maxheapIfy(A, i, n);
     }
   }

   /**
    * 维护从下标i开始的最大堆
    *
    * @param A
    * @param i
    * @param n
    */
   private static void maxheapIfy(int A[], int i, int n) {
     int left, right, loc;

     while (i < n) {
       left = 2 * i + 1;
       right = 2 * i + 2;
       loc = i;

       if (left < n && A[left] > A[i]) {
         i = left;
       }

       if (right < n && A[right] > A[i]) {
         i = right;
       }

       if (loc != i) {
         A[i] = A[loc] ^ A[i];
         A[loc] = A[loc] ^ A[i];
         A[i] = A[loc] ^ A[i];
       } else {
         break;
       }
     }
   }

   /**
    * 直接选择排序
    *
    * @param A
    * @param n
    */
   public static void selectSort(int A[], int n) {
     int i, j, loc;

     for (i = 0; i < n; i++) {
       loc = i;

       for (j = i + 1; j < n; j++) {
         if (A[j] < A[loc]) {
           loc = j;
         }
       }

       if (loc != i) {
         A[i] = A[i] ^ A[loc];
         A[loc] = A[i] ^ A[loc];
         A[i] = A[i] ^ A[loc];
       }
     }
   }

   /**
    * 直接插入排序
    *
    * @param A
    * @param n
    */
   public static void insertSort(int A[], int n) {
     int i, j, tmp;

     for (i = 1; i < n; i++) {
       tmp = A[i];

       for (j = i - 1; j >= 0; j--) {
         if (A[j] > tmp) {
           A[j + 1] = A[j];
         } else {
           break;
         }
       }

       A[j + 1] = tmp;
     }
   }

   /**
    * 冒泡排序
    *
    * @param A
    * @param n
    */
   public static void bubbleSort(int A[], int n) {
     int i, j;

     for (i = 0; i < n - 1; i++) {
       for (j = 0; j < n - i - 1; j++) {
         if (A[j] > A[j + 1]) {
           A[j] = A[j] ^ A[j + 1];
           A[j + 1] = A[j] ^ A[j + 1];
           A[j] = A[j] ^ A[j + 1];
         }
       }
     }
   }

   /**
    * 打印数组
    *
    * @param A
    */
   public static void printArr(int A[]) {
     for (int i = 0; i < A.length; i++) {
       if (i == A.length - 1) {
         System.out.printf("%d\n", A[i]);
       } else {
         System.out.printf("%d ", A[i]);
       }
     }
   }
 }