java 算法实现

标签：完成   exti   word   ati   --   希尔排序   策略   heap   The   

（1）时间频度：一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

（2）时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。去掉常数项+去低阶项+去掉最高阶系数

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2*n)＜Ο(n!)

1.1 选择 排序

选择排序算法也是比较简单的排序算法,其思路比较直观。选择排序算法在每一步中选取最小值来重新排列,从而达到排序的目的。   选择排序算法通过选择和交换来实现排序,其排序流程如下:

1.首先从原始数组中选择最小的1个数据,将其和位于第1个位置的数据交换。
2.接着从剩下的 n-1 个数据中选择次小的 1 个数据,将其和第2个位置的数据交换。
3.然后不断重复上述过程,直到最后两个数据完成交换。至此,便完成了对原始数组的从小到大的排序。

public class Xzz {
  public static void sortXz(int[] arr){
    int d,e;
    for(int i=0;iarr.length-1;i++){
      d=i;
      for(int j=i+1;jarr.length;j++){
        if(arr[j]arr[d]){  // 若剩余 n-(i+1) 个数据中有小于 a[i]的，则记录该元素下标
          d=j;
        }
        if(d!=i){
          e = arr[i];
          arr[i] = arr[d];
          arr[d] = e;
        } } } }
  public static void main(String[] args) {
    int[] a=new int[20];
    Random random=new Random();
    for(int i=0;i20;i++){
      a[i]=random.nextInt(100);
    }
  Xzz.sortXz(a);
    for(int i=0;ia.length;i++){
      System.out.printf("%d ",a[i]);
    }
  }
}

1.2 插入排序

1.将一组数据分成两组，分别为有序组、无序组（一般将数据第一个元素视为有序组，剩余为无序组）。
2.取出无序组第一个元素，按从后向前的顺序，与有序组的元素逐个比较，插入到有序组合适位置。
3.重复步骤 2， 直至无序组元素为空。

插入排序对小规模数据或基本有序数据比较有效。数据有序程度越高，越有效

public class Cr {
  public static void InsertSort(int[] arr) {
    int k=0,j ;
    for(int i=1;iarr.length;i++){
      k=arr[i];              // 从无序组取出第一个元素
      j=i-1;                  // i-1 即为有序组最后一个元素（与待插入元素相邻）的下标
      // 按从后向前的顺序，将待插入元素与有序组元素逐个比较
      while (j>=0&&karr[j]){
        arr[j+1]=arr[j];    // 若不是合适位置，有序组元素向后移动
        j--;
      }
      arr[j+1]=k;          // 找到合适位置，将元素插入
    }
  }
  public static void main(String[] args) {
    int[] a=new int[20];
    Random random=new Random();
    for(int i=0;i20;i++){
      a[i]=random.nextInt(100);
    }
    Cr.InsertSort(a);
    for(int i=0;ia.length;i++){
      System.out.printf("%d ",a[i]);
    }
  }
}
?

1.3 希尔排序（shell排序/缩小增量排序）

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对每个子序列进行直接插入排序。然后缩减增量对子序列进行排序…，直至增量为 1 时，将整个元素序列变为有序。

希尔排序适用于大规模且无序的数据

1.假设共有 n 个元素，第一次取增量 gap = n / 2，对 gap 个元素序列进行插入排序
2.取 gap = gap / 2，对 gap 个元素序列进行插入排序
3.重复步骤 2，直至 gap = 1，将整个元素序列变为有序

public class XXee {
  static final int SIZE = 20;
  public static void shellSort(int[] array) {
    int j, temp, k = 0;
    for (int gap = array.length / 2; gap >= 1; gap /= 2) {
      // 对子序列进行插入排序
      for (int i = gap; i array.length; i++) {
        temp = array[i];            // 取无序组第一个元素，此元素即为待插入元素
        j = i - gap;                // i-gap 为有序组最后一个元素
        // 按从后向前的顺序，将待插入元素与有序组元素逐个比较
        while (j >= 0 && temp array[j]) {
          array[j+gap] = array[j];// 若不是合适位置，有序组元素向后移动
          j -= gap;
        }
        array[j+gap] = temp;        // 找到合适位置，将元素插入
      }
      System.out.print("第" + ++k + "步排序结果：");
      Arrays.stream(array).mapToObj(item -> item + " ").forEach(System.out::print);
      System.out.println();
    }
  }
  public static void main(String[] args) {
    int[] array = new int[SIZE];
?
    System.out.println("排序前的数组为：");
    for (int i = 0; i SIZE; i++) {
      // 产生 100~199 之间的随机数
      array[i] = (int) (100 + Math.random() * 100);
      System.out.printf("%d ", array[i]);
      if ((i + 1) % 10 == 0)
        System.out.println();
    }
?
    shellSort(array);
    System.out.println("排序后的数组为：");
    for (int i = 0; i array.length; i++) {
      System.out.printf("%d ", array[i]);
      if ((i + 1) % 10 == 0)
        System.out.println();
    }
  }
}

1.4 快速排序

假设有一个由若干数据组成的序列，

取第一个数据为基准数据 base，指针 i 指向第一个数据，指针 j 指向最后一个数据；
当 i 当 i == j 时：交换 base 和 array[i]，则 base 左侧的数据都小于 base，base 右侧的数据都大于base，此时一次排序结束
以 base 为界限将数据分成两个子序列，对子序列进行同样的操作，…，直到整个序列有序

array[10] = { 150 107 182 178 183 154 141 138 182 169 } 

public class QuickSortDemo {
  static final int SIZE = 20;
  static int k = 0;
?
  public static void quickSort(int[] array, int left, int right) {
    // 数组长度为 0 或 1 时直接退出
    if (array == null || left > right || (array.length - 1 0))
      return;
?
    int base = array[left]; // base：基准数据
    int i = left, j = right;// 让 i 指向数据最左侧，让 j 指向数据最左侧
    int temp;
    while (i != j) {
      // 从右向左搜寻小于 base 的数据
      while (array[j] >= base && i j)
        j--;
      // 从左向右搜寻大于 base 的数据
      while (array[i] base && i j)
        i++;
?
      // 交换搜寻到的数据
      if (i j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
?
    // 将基准数放到中间的位置（基准数归位）
    array[left] = array[i];
    array[i] = base;
        /*temp = array[i];
        array[i] = array[left];
        array[left] = temp;*/
    // 一次排序结束，此时 base 左侧的数据全小于 base，右侧的数据全大于base
?
    quickSort(array, left, i - 1); // 快排 base 左侧数据
    quickSort(array, i + 1, right);// 快排 base 右侧数据
  }
?
  public static void main(String[] args) {
    int[] array = new int[SIZE];
?
    System.out.println("排序前的数组为：");
    for (int i = 0; i SIZE; i++) {
      // 产生 100~199 之间的随机数
      array[i] = (int) (100 + Math.random() * 100);
      System.out.printf("%d ", array[i]);
    }
?
    quickSort(array, 0, array.length - 1);
    System.out.println("\n排序后的数组为：");
    for (int i = 0; i SIZE; i++) {