`

插入排序 快速排序

阅读更多

/**
     * 插入排序,当数组有序的时候是比较快的排序方法 非稳定算法,最快(当数组有序时)为线性(O(n)) 最慢以及平均情况都是为(O(n^2))二次算法
     * @param <T>
     *        范型参数
     * @param data
     *        要排序的数组
     */
    public static <T extends Comparable<T>> void insertionSort(T[] data) {
        if (data == null) // 检查数组参数
          throw new IllegalArgumentException("data is empty!");
        int i, j;
        T temp;
        for (i = 1; i < data.length; i++) {
            temp = data[i]; // 当检查数组中的元素不在正确的位置就和前面的元素交换,直到插入到正确的位置为止。
            for (j = i; j > 0 && data[j - 1].compareTo(temp) > 0; j--) {
                data[j] = data[j - 1];
            }
            data[j] = temp;
        }
    }

 

 

 

/**
    * 快速排序,非稳定的排序算法,确定为基数选择错误的时候,排序效率为二次 平均情况为(O(nlogn)),最坏情况为(O(n^2))
    * @param <T>
    *        范型参数
    * @param data
    *        要排序的数组
    */

public class QuickSortTest {
 public static int[] sort(int[] numbers) {
  return sort(numbers, 0, numbers.length - 1);
 }

 public static int[] sort(int[] numbers, int low, int high) {
  if (low < high) {
   int media = numbers[low];
   int j = high;
   int i = low;
   while (i != j) {
    while (j > i && numbers[j] >= media)
     j--;
    swap(numbers, i, j);
    while (i < j && numbers[i] <= media)
     i++;
    swap(numbers, i, j);
   }
   sort(numbers, low, i - 1);
   sort(numbers, i + 1, high);
  }
  return numbers;
 }

 public static void swap(int[] numbers, int i, int j) {
  int media = numbers[i];
  numbers[i] = numbers[j];
  numbers[j] = media;
 }

 public static void main(String[] args) {
  int[] a = sort(new int[] { 6,8, 7, 6, 5,10, 4, 3, 2, 1 });
  for (int i : a)
   System.out.print(i);
 }

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics