Java常用的六种算法 赶紧拿去收藏吧

这段时间也是闲了下来，就抽出时间总结了下Java的六大常用算法，希望可以帮到你们。

一.插入排序算法

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

二.选择排序算法

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

三.冒泡排序法

所谓冒泡排序法就是将比较大的数字沉在最下面，较小的浮在上面

四.快速排序算法

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

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

五.希尔排序

对于直接插入排序问题，数据量巨大时。

将数的个数设为n，取奇数k=n/2，将下标差值为k的书分为一组，构成有序序列。

再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。

重复第二步，直到k=1执行简单插入排序。

如何写成代码：

1.首先确定分的组数。

2.然后对组中元素进行插入排序。

3.然后将length/2，重复1,2步，直到length=0为止。

代码实现如下：

public void sheelSort(int[] a){ int d = a.length; while (d!=0) {
d=d/2; for (int x = 0; x < d; x++) {//分的组数
for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
int j = i - d;//j为有序序列最后一位的位数
int temp = a[i];//要插入的元素
for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。
a[j + d] = a[j];//向后移动d位
}
a[j + d] = temp;
}
}
}
}

六.堆排序,对简单选择排序的优化。

1.将序列构建成大顶堆。

2.将根节点与最后一个节点交换，然后断开最后一个节点。

3.重复第一、二步，直到所有节点断开。

六.堆排序

对简单选择排序的优化。

1.将序列构建成大顶堆。

2.将根节点与最后一个节点交换，然后断开最后一个节点。

3.重复第一、二步，直到所有节点断开。

代码实现如下：

public void heapSort(int[] a){
System.out.println("开始排序"); int arrayLength=a.length; //循环建堆
for(int i=0;i
buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
} private void swap(int[] data, int i, int j) { // TODO Auto-generated method stub
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
} //对data数组从0到lastIndex建大顶堆
private void buildMaxHeap(int[] data, int lastIndex) { // TODO Auto-generated method stub
//从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
if(data[biggerIndex]
biggerIndex++;
}
} //如果k节点的值小于其较大的子节点的值
if(data[k]
swap(data,k,biggerIndex); //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{ break;
}
}
}
}

常见的排序不止这六个，今天因为篇幅原因只能分享到这里了，喜欢我的

文章，请多多支持喔，你们的支持是我更新的动力。