java常用算法,java基本算法有哪些

JAVA算法合集：冒泡+插入+快速+希尔+归并+桶+基数+剪枝+回溯算法

又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。

（2）这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1 个位置。

（3）N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。

插入排序算法

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。

快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1. 操作方法：

选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；

2. 按增量序列个数 k，对序列进行 k 趟排序；

3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

桶排序的基本思想是：把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

1.找出待排序数组中的最大值 max、最小值 min

2.我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1

3.遍历数组 arr，计算每个元素 arr[i] 放的桶

4.每个桶各自排序

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA算法等。

求所有子数组的和的最大值。要求时间复杂度为O(n)。比如输入a[]={31,-41,59,26,-53,58,97,-93,-23,84}，那么程序的输出为a[2…6]的和，即187。

《编程珠玑》给出了一个时间复杂度为O(n)的扫描算法。代码非常简练，但得稍微思考一下才能明白。

首先我们必须找到最大的子数组的起始点，从a[0]开始扫描，并且逐一累加，累加和存储到max_ending_here变量。当累加到i,即a[0]+a[1]+…a[i]的和小于0时，我们认定最大子数组绝对不包括a[0]~a[i],就可以更新最大子数组的起始位置begin=i+1，并将max_ending_here清0。所以说max_ending_here始终存储的是累加和大于0的子数组累加和。这时还需要另外一个变量max_sofar存储当前的最大子数组累加和。每扫描一个数据就将max_ending_here和max_sofar进行一次比较，保证max_sofar始终存储目前最大的子数组累加和。代码如下：

现在假设有一个很实际的问题：我们要在 n 个城市中建立一个通信网络，则连通这 n 个城市需要布置 n-1 一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？

于是我们就可以引入连通图来解决我们遇到的问题，n 个城市就是图上的 n 个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有 n 个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST 性质（假设N=(V,{E})是一个连通网，U 是顶点集 V 的一个非空子集，如果（u，v）是一条具有最小权值的边，其中 u 属于 U，v 属于 V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用 MST 性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。

Java常用的7大排序算法汇总

这段时间闲了下来，就抽了点时间总结了下java中常用的七大排序算法，希望以后可以回顾！

1.插入排序算法

插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortInsert(int[] array){
for(int i=1;i<array.length;i++){
int temp = array[i];
int j;
for(j=i-1;j >= 0 && temp< array[j]; j–){
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
return array;
}

2.选择排序算法

选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortSelect(int[] arr){
for (int i = 0; i < arr.length; i++) {
int miniPost = i;
for (int m = i + 1; m < arr.length; m++) {
if (arr[m] < arr[miniPost]) {
miniPost = m;
}
}
if (arr[i] > arr[miniPost]) {
int temp;
temp = arr[i];
arr[i] = arr[miniPost];
arr[miniPost] = temp;
}
}
return arr;
}

3.冒泡排序算法

冒泡排序是將比較大的數字沉在最下面，较小的浮在上面

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortBubble(int[] array){
int temp;
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
for(int i=0;i<array.length-1;i++){
for (int j = array.length – 1; j > i; j–) {
if (array[j] < array[j – 1]) {
temp = array[j];
array[j] = array[j – 1];
array[j – 1] = temp;
}
}
}
return array;
}

4.快速排序算法

通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大。

可随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortQuick(int[] array){
return quickSort(array, 0, array.length-1);
}
private int quickSort(int[] arr, int low, int heigh) {
if (low < heigh) {
int division = partition(arr, low, heigh);
quickSort(arr, low, division – 1);
quickSort(arr, division + 1, heigh);
}
return arr;
}
// 分水岭,基位,左边的都比这个位置小,右边的都大
private int partition(int[] arr, int low, int heigh) {
int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录
while (low < heigh) { //从表的两端交替向中间扫描
while (low < heigh && arr[heigh] >= base) {
heigh–;
}
// base 赋值给当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大
swap(arr, heigh, low);
while (low < heigh && arr[low] <= base) {
low++;
}
// 遇到左边比base值大的了,换位置
swap(arr, heigh, low);
}
// now low = heigh;
return low;
}
private void swap(int[] arr, int a, int b) {
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}

5.合并排序算法

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

/**
* @param int 未排序数组
* @return int 排完序数组
*/
private int sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
sort(nums, low, mid);
// 右边
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
private void merge(int[] nums, int low, int mid, int high) {
int temp = new int[high – low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
public int sortMerge(int[] array) {
return sort(array, 0, array.length – 1);
}

6.希尔排序算法

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组。

以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ，则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序。

此时的数组已经基本上好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题，希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortShell(int[] array) {
// 取增量
int step = array.length / 2;
while (step >= 1) {
for (int i = step; i < array.length; i++) {
int temp = array[i];
int j = 0;
// 跟插入排序的区别就在这里
for (j = i – step; j >= 0 && temp < array[j]; j -= step) {
array[j + step] = array[j];
}
array[j + step] = temp;
}
step /= 2;
}
return array;
}

7.堆排序算法

本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换，剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。

/**
* @param int 未排序数组
* @return int 排完序数组
*/
public int sortHeap(int[] array) {
buildHeap(array);// 构建堆
int n = array.length;
int i = 0;
for (i = n – 1; i >= 1; i–) {
swap(array, 0, i);
heapify(array, 0, i);
}
return array;
}
private void buildHeap(int[] array) {
int n = array.length;// 数组中元素的个数
for (int i = n / 2 – 1; i >= 0; i–)
heapify(array, i, n);
}
private void heapify(int[] A, int idx, int max) {
int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）
int right = 2 * idx + 2;// 左孩子的下标（如果存在的话）
int largest = 0;// 寻找3个节点中最大值节点的下标
if (left < max && A[left] > A[idx])
largest = left;
else
largest = idx;
if (right < max && A[right] > A[largest])
largest = right;
if (largest != idx) {
swap(A, largest, idx);
heapify(A, largest, max);
}
}
}
// 建堆函数，认为【s，m】中只有 s
// 对应的关键字未满足大顶堆定义，通过调整使【s，m】成为大顶堆=====================================================
public static void heapAdjust(int[] array, int s, int m) {
// 用0下标元素作为暂存单元
array[0] = array[s];
// 沿孩子较大的结点向下筛选
for (int j = 2 * s; j <= m; j *= 2) {
// 保证j为较大孩子结点的下标，j < m 保证 j+1 <= m ，不越界
if (j < m && array[j] < array[j + 1]) {
j++;
}
if (!(array[0] < array[j])) {
break;
}
// 若S位较小，应将较大孩子上移
array[s] = array[j];
// 较大孩子的值变成S位的较小值，可能引起顶堆的不平衡，故对其所在的堆进行筛选
s = j;
}
// 若S位较大，则值不变；否则，S位向下移动至2*s、4*s、。。。
array[s] = array[0];

内容来源：Android开发中文站

最新的TIOBE指数显示，Java编程已经超过了20%的普及门槛，这意味着每五行源代码当中就有一行采用Java编写。这不是Java语言有史以来最高分，它曾在多年前和C与C++语言竞争当中失去了头把交椅，但现在可能已经卷土重来。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com

文章为作者独立观点不代本网立场，未经允许不得转载。

继续阅读本文相关话题

TAG

全部

行业动态

C4D教程

C4D百科

java常用算法,java基本算法有哪些收藏 0

2025-02-07 01:13 作者：中望小编来源：互联网点击：0

JAVA算法合集：冒泡+插入+快速+希尔+归并+桶+基数+剪枝+回溯算法

Java常用的7大排序算法汇总

继续阅读本文相关话题

C4D百科

3Dmax和C4D有什么区别？

上一篇

中望小编

C4D百科

java常用编辑器;java编译器有哪几种

中望小编

C4D百科

java常用软件【java开发软件有哪些】

中望小编

C4D百科

java常用类和方法、java开发常用四大框架

中望小编

C4D百科

java常见面试题—java中级面试题大汇总

中望小编

C4D百科

java常见的设计模式,JAVA24种设计模式

java常用算法,java基本算法有哪些 收藏 0

2025-02-07 01:13 作者： 中望小编 来源：互联网 点击：0

JAVA算法合集：冒泡+插入+快速+希尔+归并+桶+基数+剪枝+回溯算法

Java常用的7大排序算法汇总

继续阅读本文相关话题

C4D百科

3Dmax和C4D有什么区别？

上一篇

中望小编

中望小编

中望小编

中望小编

中望小编

java常用算法,java基本算法有哪些收藏 0

2025-02-07 01:13 作者：中望小编来源：互联网点击：0