- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
/**
* 时间复杂度:
* 最好的情况: O(n)
* 最坏的情况: O(n^2)
* 空间复杂度: O(1)
* @param array
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int j = i - 1;
int tmp = array[i];
while (j >= 0) {
if (array[j] > tmp) {
array[j + 1] = array[j];
j--;
}else {
break;
}
}
array[j + 1] = tmp;
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
插入排序,初始数据越接近有序,时间效率越高。
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap
,把待排序文件中所有记录分成个gap
组,所有距离为gap
的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap = (gap/3)+1
,重复上述分组和排序的工作。当到达gap=1
时,所有记录在统一组内排好序。
/**
*
* @param array 排序的数组
* @param gap 每组的间隔 -> 数组
*/
public static void shell(int[] array,int gap){
for (int i = gap; i < array.length ; i++) {
int tmp = array[i];
int j = i - gap;
while(j>=0){
if(array[j] > tmp){
array[j + gap] = array[j];
j -= gap;
}else {
break;
}
}
array[j + gap] = tmp;
}
}
public static void shellSort(int[] array){
int gap = array.length;
while (gap > 1){
gap = (gap / 3) + 1;// +1 保证最后一个序列是 1 (除几都行)
shell(array,gap);
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^1.3) | O(n^2) | O(n) | O(1) | 不稳定 |
/**
* 时间复杂度:
* 最好: O(n^2)
* 最坏: O(n^2)
* 空间复杂度: O(1)
* 稳定性: 不稳定
* @param array
*/
public static void selectSort(int[] array){
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j <array.length ; j++) {
if(array[j] < array[i]){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
public static void siftDown(int[] array,int root, int len){
int parent = root;
int child = root * 2 + 1;
while (child < len){
if( child+1 < len && array[child] < array[child+1] ){
child++;
}
//这里child下标就是左右孩子的最大值的下标
if(array[child] > array[parent]){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
parent = child;
child = parent * 2 + 1;
}else {
break;
}
}
}
public static void createHeap(int[] array){
for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {
siftDown(array,i,array.length);
}
}
public static void heapSort(int[] array){
createHeap(array);
int end = array.length - 1;
while (end > 0){
int tmp = array[end];
array[end] = array[0];
array[0] =tmp;
siftDown(array,0,end);
end--;
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
public static void BubbleSort(int[] array){
for (int i = 0; i < array.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < array.length - 1 - i ; j++) {
if(array[j+1] < array[j]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if(!flg){
break;
}
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
//Hoare法
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static int partition1(int[] array,int low,int high) {
int i = low;
int tmp = array[low];
while (low < high){
while (low < high && array[high] >= tmp){
high--;
}
while (low < high && array[low] <= tmp){
low++;
}
swap(array,low,high);
}
swap(array,i,low);
return low;
}
//挖坑法
public static int partition2(int[] array,int low,int high) {
int tmp = array[low];
while (low < high){
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quick(int[] array,int start,int end){
if(start >= end) return;
int pivot = partition1(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static int partition2(int[] array,int low,int high) {
int tmp = array[low];
while (low < high){
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
if(array[mid] > array[start]){
swap(array,start,mid);
}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]
if(array[mid] > array[end]){
swap(array,mid,end);
}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]
if(array[start] > array[end]){
swap(array,start,end);
}//此时有 array[mid] <= array[start] <= array[end]
}
public static void quick1(int[] array,int start,int end){
if(start >= end) return;
int mid = (start + end) / 2;
selectPivotMedianOFThree(array,start,end,mid);
int pivot = partition2(array,start,end);
quick1(array,start,pivot-1);
quick1(array,pivot+1,end);
}
public static void quick1Sort(int[] array){
quick1(array,0,array.length - 1);
}
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void insertSort2(int[] array,int start,int end){
for (int i = start + 1; i <= end; i++) {
int j = i + 1;
int tmp = array[i];
while (j >= 0){
if(array[j] > tmp){
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
public static int partition2(int[] array,int low,int high) {
int tmp = array[low];
while (low < high){
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
if(array[mid] > array[start]){
swap(array,start,mid);
}//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start]
if(array[mid] > array[end]){
swap(array,mid,end);
}//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end]
if(array[start] > array[end]){
swap(array,start,end);
}//此时有 array[mid] <= array[start] <= array[end]
}
public static void quick2(int[] array,int start,int end){
if(start >= end) return;
if(end - start + 1 <= 100){
insertSort2(array,start,end);
return;
}
int mid = (start + end)/2;
selectPivotMedianOFThree(array,start,end,mid);
int pivot = partition2(array,start,end);
quick2(array,start,pivot-1);
quick2(array,pivot+1,end);
}
public static void quick2Sort(int[] array){
quick2(array,0,array.length - 1);
}
public static void quickSort4(int[] array){
Stack<Integer> stack = new Stack<>();
int low = 0;
int high = array.length - 1;
int pivot = partition2(array,low ,high);
//左边有2个元素即以上
if(pivot > low + 1){
stack.push(0);
stack.push(pivot - 1);
}
//右边有2个元素即以上
if(pivot < high - 1){
stack.push(pivot + 1);
stack.push(high);
}
while (!stack.isEmpty()){
high = stack.pop();
low = stack.pop();
pivot = partition2(array,low,high);
//左边有2个元素即以上
if(pivot > low + 1){
stack.push(0);
stack.push(pivot - 1);
}
//右边有2个元素即以上
if(pivot < high - 1){
stack.push(pivot + 1);
stack.push(high);
}
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n^2) | O(n * log(n)) | O(log(n))~O(n) | 不稳定 |
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子 序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
public static void merge(int[] array,int low ,int high ,int mid){
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmp = new int[high - low + 1];
int k = 0;
while (s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1){
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
for (int i = 0; i < tmp.length; i++) {
array[i+low] = tmp[i];
}
}
public static void mergeSortInternal(int[] array,int low ,int high){
if(low >= high) return;
int mid = (low + high) / 2;
mergeSortInternal(array,low,mid);
mergeSortInternal(array,mid+1,high);
merge(array,low,high,mid);
}
public static void mergeSort(int[] array){
mergeSortInternal(array,0,array.length - 1);
}
public static void merge1(int[] array,int gap){
int[] tmp = new int[array.length];
int k = 0;
int s1 = 0;
int e1 = s1 + gap - 1;
int s2 = e1 + 1;
int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;
while (s2 < array.length){
while (s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1){
tmp[k++] = array[s1++];
}
while (s2 <= e2){
tmp[k++] = array[s2++];
}
s1 = e2 + 1;
e1 = s1 + gap - 1;
s2 = e1 + 1;
e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;
}
while (s1 <= array.length - 1){
tmp[k++] = array[s1++];
}
for (int i = 0; i < tmp.length; i++) {
array[i] = tmp[i];
}
}
public static void mergeSort1(int[] array){
for (int i = 1; i < array.length; i*=2) {
merge1(array,i);
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
(1)找出待排序的数组中最大和最小的元素
(2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项
(3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
(4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
public static void CountingSort(int[] array){
int maxValue = GetMaxValue(array);
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value:array) {
bucket[value]++;
}
int index = 0 ;
for (int i = 0; i < bucketLen; i++) {
while(bucket[i] > 0){
array[index++] = i;
bucket[i]--;
}
}
}
public static int GetMaxValue(int[] array){
int maxValue = array[0];
for (int i = 0; i < array.length; i++) {
if(maxValue < array[i]){
maxValue = array[i];
}
}
return maxValue;
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。
为了使桶排序更加高效,我们需要做到这两点:
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
public static void bucketSort(int[] arr) {
if (arr.length == 0) {
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
//得到最大和最小元素
int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的数量
ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>());
}
//将元素放入到桶中
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - minValue) / arr.length;
bucket.get(num).add(arr[i]);
}
for (int i = 0; i < bucket.size(); i++) {
//这里是比较,可以选择其他的方式实现,这里为了演示采取Collection的sort
Collections.sort(bucket.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucket.size(); i++){
for(int j = 0; j < bucket.get(i).size(); j++){
arr[index++] = bucket.get(i).get(j);
}
}
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n+k) | O(n^2) | O(n+k) | O(n+k) | 稳定 |
public static int getNumLength(int num){
if(num == 0) return 1;
int count = 0;
for (int i = num; i != 0; i /= 10) {
count++;
}
return count;
}
public static void RadixSort(int[] array){
int maxValue = array[0];
for (int i = 0; i < array.length; i++) {
if(maxValue < array[i]){
maxValue = array[i];
}
}
int maxDigit = getNumLength(maxValue);
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < array.length; j++) {
int bucket = ((array[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], array[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
array[pos++] = value;
}
}
}
}
public static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n*k) | O(n*2) | O(n*k) | O(n+k) | 稳定 |
排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n)数组有序 | O(n^2) | O(n^2) 数组逆序 | O(1) | 稳定 |
插入排序 | O(n)数组有序 | O(n^2) | O(n^2) 数组逆序 | O(1) | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
希尔排序 | O(n)数组有序 | O(n^1.3) | O(n^2)比较难构造 | O(1) | 不稳定 |
堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | 最好O(log(n)) 最坏O(n) | 不稳定 |
归并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
桶排序 | O(n+k) | O(n+k) | O(n^2) | O(k) | 稳定 |
计数排序 | O(n×k) | O(n×k) | O(n×k) | O(k) | 稳定 |
我正在编写一个具有以下签名的 Java 方法。 void Logger(Method method, Object[] args); 如果一个方法(例如 ABC() )调用此方法 Logger,它应该
我是 Java 新手。 我的问题是我的 Java 程序找不到我试图用作的图像文件一个 JButton。 (目前这段代码什么也没做,因为我只是得到了想要的外观第一的)。这是我的主课 代码: packag
好的,今天我在接受采访,我已经编写 Java 代码多年了。采访中说“Java 垃圾收集是一个棘手的问题,我有几个 friend 一直在努力弄清楚。你在这方面做得怎么样?”。她是想骗我吗?还是我的一生都
我的 friend 给了我一个谜语让我解开。它是这样的: There are 100 people. Each one of them, in his turn, does the following
如果我将使用 Java 5 代码的应用程序编译成字节码,生成的 .class 文件是否能够在 Java 1.4 下运行? 如果后者可以工作并且我正在尝试在我的 Java 1.4 应用程序中使用 Jav
有关于why Java doesn't support unsigned types的问题以及一些关于处理无符号类型的问题。我做了一些搜索,似乎 Scala 也不支持无符号数据类型。限制是Java和S
我只是想知道在一个 java 版本中生成的字节码是否可以在其他 java 版本上运行 最佳答案 通常,字节码无需修改即可在 较新 版本的 Java 上运行。它不会在旧版本上运行,除非您使用特殊参数 (
我有一个关于在命令提示符下执行 java 程序的基本问题。 在某些机器上我们需要指定 -cp 。 (类路径)同时执行java程序 (test为java文件名与.class文件存在于同一目录下) jav
我已经阅读 StackOverflow 有一段时间了,现在我才鼓起勇气提出问题。我今年 20 岁,目前在我的家乡(罗马尼亚克卢日-纳波卡)就读 IT 大学。足以介绍:D。 基本上,我有一家提供簿记应用
我有 public JSONObject parseXML(String xml) { JSONObject jsonObject = XML.toJSONObject(xml); r
我已经在 Java 中实现了带有动态类型的简单解释语言。不幸的是我遇到了以下问题。测试时如下代码: def main() { def ks = Map[[1, 2]].keySet()
一直提示输入 1 到 10 的数字 - 结果应将 st、rd、th 和 nd 添加到数字中。编写一个程序,提示用户输入 1 到 10 之间的任意整数,然后以序数形式显示该整数并附加后缀。 public
我有这个 DownloadFile.java 并按预期下载该文件: import java.io.*; import java.net.URL; public class DownloadFile {
我想在 GUI 上添加延迟。我放置了 2 个 for 循环,然后重新绘制了一个标签,但这 2 个 for 循环一个接一个地执行,并且标签被重新绘制到最后一个。 我能做什么? for(int i=0;
我正在对对象 Student 的列表项进行一些测试,但是我更喜欢在 java 类对象中创建硬编码列表,然后从那里提取数据,而不是连接到数据库并在结果集中选择记录。然而,自从我这样做以来已经很长时间了,
我知道对象创建分为三个部分: 声明 实例化 初始化 classA{} classB extends classA{} classA obj = new classB(1,1); 实例化 它必须使用
我有兴趣使用 GPRS 构建车辆跟踪系统。但是,我有一些问题要问以前做过此操作的人: GPRS 是最好的技术吗?人们意识到任何问题吗? 我计划使用 Java/Java EE - 有更好的技术吗? 如果
我可以通过递归方法反转数组,例如:数组={1,2,3,4,5} 数组结果={5,4,3,2,1}但我的结果是相同的数组,我不知道为什么,请帮助我。 public class Recursion { p
有这样的标准方式吗? 包括 Java源代码-测试代码- Ant 或 Maven联合单元持续集成(可能是巡航控制)ClearCase 版本控制工具部署到应用服务器 最后我希望有一个自动构建和集成环境。
我什至不知道这是否可能,我非常怀疑它是否可能,但如果可以,您能告诉我怎么做吗?我只是想知道如何从打印机打印一些文本。 有什么想法吗? 最佳答案 这里有更简单的事情。 import javax.swin
我是一名优秀的程序员,十分优秀!