java实现的各种排序算法代码示例

2024-10-05 00:06:02

折半插入排序

折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的
插入位置，这实际上是一种查找算法：折半查找。Java的Arrays类里的binarySearch()方法，就是折半查找的实现，用
于从指定数组中查找指定元素，前提是该数组已经处于有序状态。与直接插入排序的效果相同，只是更快了一些，因
为折半插入排序可以更快地确定第i个元素的插入位置

代码：

package interview;
/**
 * @author Administrator
 * 折半插入排序
 */
public class BinaryInsertSort {
  public static void binaryInsertSort(DataWrap[] data) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    for (int i = 1; i < arrayLength; i++) {
      DataWrap temp = data[i];
      int low = 0;
      int high = i - 1;
      while (low <= high) {
        int mid = (low + high) / 2;
        if (temp.compareTo(data[mid]) > 0) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      for (int j = i; j > low; j--) {
        data[j] = data[j - 1];
      }
      data[low] = temp;
      System.out.println(java.util.Arrays.toString(data));
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "")};
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    binaryInsertSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果：

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-30, -16, 9, 21*, 23, -49, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21, 21*, 23, 30*, 30]
[-49, -30, -16, 9, 21, 21*, 23, 30*, 30]
[-49, -30, -16, 9, 21, 21*, 23, 30, 30*]
排序之后：
[-49, -30, -16, 9, 21, 21*, 23, 30, 30*]

冒泡排序

代码：

package interview;
/**
 * @author Administrator
 * 冒泡排序
 */
public class BubbleSort {
  public static void bubbleSort(DataWrap[] data) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    for (int i = 0; i < arrayLength - 1; i++) {
      boolean flag = false;
      for (int j = 0; j < arrayLength - 1 - i; j++) {
        if (data[j].compareTo(data[j + 1]) > 0) {
          DataWrap temp = data[j + 1];
          data[j + 1] = data[j];
          data[j] = temp;
          flag = true;
        }
      }
      System.out.println(java.util.Arrays.toString(data));
      if (!flag)
        break;
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "")};
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    bubbleSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

运行结果：

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-16, 9, 21*, -30, -49, 21, 23, 30*, 30]
[-16, 9, -30, -49, 21*, 21, 23, 30*, 30]
[-16, -30, -49, 9, 21*, 21, 23, 30*, 30]
[-30, -49, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

桶式排序

算法的时间效率：时间效率极高，只需经过两轮遍历即可算法的空间效率：空间开销较大，需要两个数组来完成，算
法的稳定性：稳定
代码：

package interview;
import java.util.Arrays;
/**
 * @author Administrator
 * 桶式排序
 */
public class BucketSort {
  public static void bucketSort(DataWrap[] data, int min, int max) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    DataWrap[] temp = new DataWrap[arrayLength];
    int[] buckets = new int[max - min];
    for (int i = 0; i < arrayLength; i++) {
      buckets[data[i].data - min]++;
    }
    System.out.println(Arrays.toString(buckets));
    for (int i = 1; i < max - min; i++) {
      buckets[i] = buckets[i] + buckets[i - 1];
    }
    System.out.println(Arrays.toString(buckets));
    System.arraycopy(data, 0, temp, 0, arrayLength);
    for (int k = arrayLength - 1; k >= 0; k--) {
      data[--buckets[temp[k].data - min]] = temp[k];
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""),
        new DataWrap(-1, ""), new DataWrap(8, ""),
        new DataWrap(5, "*"), new DataWrap(7, ""),
        new DataWrap(3, ""), new DataWrap(-3, ""),
        new DataWrap(1, ""),new DataWrap(3, "*")};
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    bucketSort(data, -3, 10);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果

排序之前：
[9, 5, -1, 8, 5*, 7, 3, -3, 1, 3*]
开始排序
[1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1]
[1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10]
排序之后：
[-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 9]

堆排序

代码：

package interview;
/**
 * @author Administrator
 * 堆排序
 */
public class HeapSort {
  public static void heapSort(DataWrap[] data) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    // 循环建堆
    for (int i = 0; i < arrayLength - 1; i++) {
      // 建堆
      builMaxdHeap(data, arrayLength - 1 - i);
      // 交换堆顶和最后一个元素
      swap(data, 0, arrayLength - 1 - i);
      System.out.println(java.util.Arrays.toString(data));
    }
  }
  // 对data数组从0到lastIndex建大顶堆
  private static void builMaxdHeap(DataWrap[] data, int lastIndex) {
    // 从lastIndex处节点（最后一个节点）的父节点开始
    for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
      // k保存当前正在判断的节点
      int k = i;
      // 如果当前k节点的子节点存在
      while (k * 2 + 1 <= lastIndex) {
        // k节点的左子节点的索引
        int biggerIndex = 2 * k + 1;
        // 如果biggerIndex小于lastIndex，即biggerIndex +1
        // 代表k节点的右子节点存在
        if (biggerIndex < lastIndex) {
          // 如果右子节点的值较大
          if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
            // biggerIndex总是记录较大子节点的索引
            biggerIndex++;
          }
        }
        // 如果k节点的值小于其较大子节点的值
        if (data[k].compareTo(data[biggerIndex]) < 0) {
          // 交换它们
          swap(data, k, biggerIndex);
          // 将biggerIndex赋给k，开始while循环的下一次循环
          // 重新保证k节点的值大于其左、右节点的值
          k = biggerIndex;
        } else {
          break;
        }
      }
    }
  }
  // 交换data数组中i、j两个索引处的元素
  private static void swap(DataWrap[] data, int i, int j) {
    DataWrap temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "")};
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    heapSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果：

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-16, 30, 21*, 23, -30, -49, 21, 9, 30*]
[-16, 23, 21*, 9, -30, -49, 21, 30, 30*]
[21, 9, 21*, -16, -30, -49, 23, 30, 30*]
[-49, 9, 21*, -16, -30, 21, 23, 30, 30*]
[-30, 9, -49, -16, 21*, 21, 23, 30, 30*]
[-30, -16, -49, 9, 21*, 21, 23, 30, 30*]
[-49, -30, -16, 9, 21*, 21, 23, 30, 30*]
[-49, -30, -16, 9, 21*, 21, 23, 30, 30*]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30, 30*]

直接插入排序

package interview;
public class InsertSort {
	public static void insertSort(DataWrap[] data){
	  System.out.println("开始排序");
	  int arrayLength = data.length;
	  for(int i = 1;i < arrayLength;i++){
	    DataWrap temp = data[i];
	    if(data[i].compareTo(data[i-1]) < 0){
	      int j = i -1;
	      for(;j >= 0 && data[j].compareTo(temp) > 0;j--){
	        data[j +1] = data[j];
	      }
	      data[j + 1] = temp;
	    }
	    System.out.println(java.util.Arrays.toString(data));
	  }
	}
	public static void main(String[] args) {
	  DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
	      new DataWrap(21, "*"), new DataWrap(23, ""),
	      new DataWrap(-30, ""), new DataWrap(-49, ""),
	      new DataWrap(21, ""), new DataWrap(30, "*"),
	      new DataWrap(30, "")};
	  System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
	  insertSort(data);
	  System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
	}
}

结果

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-30, -16, 9, 21*, 23, -49, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

归并排序

算法的时间效率：归并算法需要递归地进行分解、合并，每进行一趟归并排序，需要merge()方法一次，每次执行
merge()需要比较n次，较差，需要一个与原始序列同样大小的辅助序列。算法的稳定性：稳定
代码：

package interview;
/**
 * @author Administrator
 * 归并排序
 */
public class MergeSort {
  public static void mergeSort(DataWrap[] data) {
    // 归并排序
    sort(data, 0, data.length - 1);
  }
  // 将索引从left到right范围的数组元素进行归并排序
  private static void sort(DataWrap[] data, int left, int right) {
    if(left < right){
      //找出中间索引
      int center = (left + right)/2;
      sort(data,left,center);
      sort(data,center+1,right);
      //合并
      merge(data,left,center,right);
    }
  }
  // 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
  private static void merge(DataWrap[] data, int left, int center, int right) {
    DataWrap[] tempArr = new DataWrap[data.length];
    int mid = center + 1;
    int third = left;
    int temp = left;
    while (left <= center && mid <= right) {
      if (data[left].compareTo(data[mid]) <= 0) {
        tempArr[third++] = data[left++];
      } else {
        tempArr[third++] = data[mid++];
      }
    }
    while (mid <= right) {
      tempArr[third++] = data[mid++];
    }
    while (left <= center) {
      tempArr[third++] = data[left++];
    }
    while (temp <= right) {
      data[temp] = tempArr[temp++];
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "") };
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    mergeSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果：

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

基数排序

基数排序已经不再是一种常规的排序方法，它更多地像是一种排序方法的应用，基数排序必须依赖于另外的排序方法。
基数排序的总体思路就是将待排数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字：第1个子关键字、第2个子关键字、第3个子
关键字。。。然后，根据子关键字对待排数据进行排序。在进行多关键字排序时有两种解决方案：

最高位优先法MSD
最低位优先法LSD

比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简单，因为LSD法是从头到尾进行若干次分配和收集，执行
的次数取决于构成关键字值的成分为多少；而MSD法则要处理各序列与子序列的独立排序问题，就可能复杂一些。

代码：

package interview; 

import java.util.Arrays; 

/**
 * @author Administrator
 * 基数排序
 */
public class MultiKeyRadixSort {
  public static void radixSort(int[] data, int radix, int d) {
    System.out.println("开始排序：");
    int arrayLength = data.length;
    int[] temp = new int[arrayLength];
    int[] buckets = new int[radix];
    for (int i = 0, rate = 1; i < d; i++) {
      // 重置count数组，开始统计第二个关键字
      Arrays.fill(buckets, 0);
      // 当data数组的元素复制到temp数组中进行缓存
      System.arraycopy(data, 0, temp, 0, arrayLength);
      for (int j = 0; j < arrayLength; j++) {
        int subKey = (temp[j] / rate) % radix;
        buckets[subKey]++;
      }
      for (int j = 1; j < radix; j++) {
        buckets[j] = buckets[j] + buckets[j - 1];
      }
      for (int m = arrayLength - 1; m >= 0; m--) {
        int subKey = (temp[m] / rate) % radix;
        data[--buckets[subKey]] = temp[m];
      }
      System.out.println("对" + rate + "位上子关键字排序："
          + java.util.Arrays.toString(data));
      rate *= radix;
    }
  } 

  public static void main(String[] args) {
    int[] data = { 1100, 192, 221, 12, 13 };
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    radixSort(data, 10, 4);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果

排序之前：
[1100, 192, 221, 12, 13]
开始排序：
对1位上子关键字排序：[1100, 221, 192, 12, 13]
对10位上子关键字排序：[1100, 12, 13, 221, 192]
对100位上子关键字排序：[12, 13, 1100, 192, 221]
对1000位上子关键字排序：[12, 13, 192, 221, 1100]
排序之后：
[12, 13, 192, 221, 1100]

快速排序

代码：

package interview;
/**
 * @author Administrator
 * 快速排序
 */
public class QuickSort {
  private static void swap(DataWrap[] data, int i, int j) {
    DataWrap temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }
  private static void subSort(DataWrap[] data, int start, int end) {
    if (start < end) {
      DataWrap base = data[start];
      int i = start;
      int j = end + 1;
      while (true) {
        while (i < end && data[++i].compareTo(base) <= 0)
          ;
        while (j > start && data[--j].compareTo(base) >= 0)
          ;
        if (i < j) {
          swap(data, i, j);
        } else {
          break;
        }
      }
      swap(data, start, j);
      subSort(data, start, j - 1);
      subSort(data, j + 1, end);
    }
  }
  public static void quickSort(DataWrap[] data){
    subSort(data,0,data.length-1);
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "") };
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    quickSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21, 21*, 23, 30*, 30]

直接选择排序

代码：

package interview;
/**
 * @author Administrator
 * 直接选择排序
 */
public class SelectSort {
  public static void selectSort(DataWrap[] data) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    for (int i = 0; i < arrayLength - 1; i++) {
      for (int j = i + 1; j < arrayLength; j++) {
        if (data[i].compareTo(data[j]) > 0) {
          DataWrap temp = data[i];
          data[i] = data[j];
          data[j] = temp;
        }
      }
      System.out.println(java.util.Arrays.toString(data));
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "") };
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    selectSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
[-49, 9, 21*, 23, -16, -30, 21, 30*, 30]
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, -16, 23, 21*, 9, 21, 30*, 30]
[-49, -30, -16, 9, 23, 21*, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

希尔排序

代码：

package interview;
/**
 * @author Administrator
 * Shell排序
 */
public class ShellSort {
  public static void ShellSort(DataWrap[] data) {
    System.out.println("开始排序");
    int arrayLength = data.length;
    int h = 1;
    /**
     * 将数组分割成若干个子序列
     */
    while (h <= arrayLength / 3) {
      h = h * 3 + 1;
      System.out.println("h的结果：" + h);
    }
    while (h > 0) {
      System.out.println("===h的值：" + h + "===");
      /**
       * 将分成的若干子序列进行直接插入排序
       */
      for (int i = h; i < arrayLength; i++) {
        DataWrap temp = data[i];
        if (data[i].compareTo(data[i - h]) < 0) {
          int j = i - h;
          for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) {
            data[j + h] = data[j];
          }
          data[j + h] = temp;
        }
        System.out.println(java.util.Arrays.toString(data));
      }
      h = (h - 1) / 3;
    }
  }
  public static void main(String[] args) {
    DataWrap[] data = {
        new DataWrap(9, ""), new DataWrap(-16, ""),
        new DataWrap(21, "*"), new DataWrap(23, ""),
        new DataWrap(-30, ""), new DataWrap(-49, ""),
        new DataWrap(21, ""), new DataWrap(30, "*"),
        new DataWrap(30, "")};
    System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
    ShellSort(data);
    System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  }
}

结果：

排序之前：
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序
h的结果：4
===h的值：4===
[-30, -16, 21*, 23, 9, -49, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
===h的值：1===
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 9, 21*, 23, -16, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后：
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

所需要的工具类：

package interview;
public class DataWrap implements Comparable<DataWrap>{
	 int data;
	 String flag;
	 public DataWrap(int data, String flag) {
	   this.data = data;
	   this.flag = flag;
	 }
	 public String toString(){
	   return data + flag;
	 }
	 @Override
	 public int compareTo(DataWrap dw) {
	   return this.data > dw.data ?
	       1 : (this.data == dw.data ? 0 : -1);
	 }
	}

以上代码亲测可用，供大家参考。

关于java实现的各种排序算法代码示例的内容，就到这里，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：Java 蒙特卡洛算法求圆周率近似值实例详解、Java编程实现递增排序链表的合并、Java编程ssh整合常见错误解析等，有什么问题可以随时留言，小编会及时回复大家的。这里推荐本站几本关于Java的书籍，免费下载，供广大编程爱好及工作者参考。

Java经典实例(第三版) 完整版 ([美]达尔文) 中文pdf扫描版

http://www.jb51.net/books/577859.html

数据挖掘：实用机器学习技术及Java实现（英文第2版）高清PDF

www.jb51.net/books/577815.html

Java初级开发工程师面试题汇总.PDF

http://www.jb51.net/books/576989.html

希望大家能够喜欢。

java实现的RC4加密解密算法示例

本文实例讲述了java实现的RC4加密解密算法.分享给大家供大家参考,具体如下: 有一个项目,需要解析一个用户提供的rc4加密后的文件,特意搜索整理了一个Java 版本的RC4加解密算法. public static String HloveyRC4(String aInput,String aKey) { int[] iS = new int[256]; byte[] iK = new byte[256]; for (int i=0;i<256;i++) iS[i]=i; int j = 1;
Apache Commons Math3学习之数值积分实例代码

Apache.Commons.Math3里面的数值积分支持类采用的是"逼近法",即,先对大区间做一次积分,再对小区间做一次积分,若两次积分结果的差值小于某一设定的误差值,则认为积分完成.否则,将区间再次细分,对细分后的区间进行积分,与前一次积分相比较,如此反复迭代,直至最近的两次积分差值足够小.这样的结果,有可能会导致无法收敛. 为了使用org.apache.commons.math3.analysis.integration包中的积分器类,需要先实现UnivariateFunctio
Java 蒙特卡洛算法求圆周率近似值实例详解

起源 [1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明,
java实现的各种排序算法代码示例

折半插入排序折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因为折半插入排序可以更快地确定第i个元素的插入位置代码: package interview; /** * @author Administrat
Java实现8种排序算法的示例代码

冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <
Java实现常见的排序算法的示例代码

目录一.优化后的冒泡排序二.选择排序三.插入排序四.希尔排序五.快速排序六.随机化快速排序七.归并排序八.可处理负数的基数排序一.优化后的冒泡排序 package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i+
Java实现世界上最快的排序算法Timsort的示例代码

目录背景前置知识指数搜索二分插入排序归并排序 Timsort 执行过程升序运行几个关键阀值运行合并合并条件合并内存开销合并优化背景 Timsort 是一个混合.稳定的排序算法,简单来说就是归并排序和二分插入排序算法的混合体,号称世界上最好的排序算法.Timsort一直是 Python 的标准排序算法.Java SE 7 后添加了Timsort API ,我们从Arrays.sort可以看出它已经是非原始类型数组的默认排序算法了.所以不管是进阶编程学习还是面试,理解 Tim
Java实现基本排序算法的示例代码

目录 1. 概述 2. 插入排序 2.1 直接插入排序 2.2 希尔排序(缩小增量排序) 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 交换排序 4.1 冒泡排序 4.2 快速排序 5. 归并排序 6. 计数排序(非比较类型的排序) 7. 排序算法总结 1. 概述排序概念:就是将一串记录按照其中某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:通俗的将就是数据元素不发生有间隔的交换,例如: 内部排序:数据元素全部放在内存中的排序外部排序:数据元素太多不能一次加载到内
Java实现拓扑排序算法的示例代码

目录拓扑排序原理 1.点睛 2.拓扑排序 3.算法步骤 4.图解拓扑排序算法实现 1.拓扑图 2.实现代码 3.测试拓扑排序原理 1.点睛一个无环的有向图被称为有向无环图.有向无环图是描述一个工程.计划.生产.系统等流程的有效工具.一个大工程可分为若干子工程(活动),活动之间通常有一定的约束,例如先做什么活动,有什么活动完成后才可以开始下一个活动. 用节点表示活动,用弧表示活动之间的优先关系的有向图,被称为 AOV 网. 在 AOV 网中,若从节点 i 到节点 j 存在一条有向路径,则称
Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

所谓有权图,就是图中的每一条边上都会有相应的一个或一组值.通常情况下,这个值只是一个数字如:在交通运输网中,边上的权值可能表示的是路程,也可能表示的是运输费用(显然二者都是数字).不过,边上的权值也有可能是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,里面集合了更多的数据克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树. 克鲁斯卡尔算法的执行步骤: 第一步:在带权连通图中,将边的权值
Java编程实现基于用户的协同过滤推荐算法代码示例

协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用
JAVA用递归实现全排列算法的示例代码

求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i
python实现经典排序算法的示例代码

以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

java实现的各种排序算法代码示例

相关推荐

随机推荐