前言：在学习java中个人认为算法是很有必要学习的。因为在同等的项目任务中懂得算法的会比不懂算法的效率要高并且代码要规范很多。当然在一些框架底层也用到了一些算法。在此具体谈一下java的十大算法，不会贴太多的源码只会浅谈一下。因为觉得代码和生活一样得具体的应用不能死板宁套。
十大算法排序如下图所示：
图片.png
)
冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
/**
* @author Lining
* 冒泡排序
* @date 2020/3/21 15:23
*/
@Test
public void updateTest3(int[] array){
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) { //相邻元素两两相比
int temp = array[j + 1]; //元素交换位置
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}
快速排序
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
* 快速排序
* @author Lining
* @date 2020/3/21 16:14
*/
public class QuickSort {
public static int[] QuickSort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
int smallIndex = partition(array, start, end);
if (smallIndex > start)
QuickSort(array, start, smallIndex - 1);
if (smallIndex < end)
QuickSort(array, smallIndex + 1, end);
return array;
}
public static int partition(int[] array, int start, int end) {
int pivot = (int) (start + Math.random() * (end - start + 1));
int smallIndex = start - 1;
swap(array, pivot, end);
for (int i = start; i <= end; i++)
if (array[i] <= array[end]) {
smallIndex++;
if (i > smallIndex)
swap(array, i, smallIndex);
}
return smallIndex;
}
/**
* 交换数组内两个元素
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
选择排序
在没有排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已经排序的序列的末尾，一直循环，直到排列完毕
/**
* @author Lining
* 选择排序
* @date 2020/3/21 15:34
*/
public class selectionSort{
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];//交换位置
array[i] = temp;
}
return array;
}
}
归并排序
将已经有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并.
import java.util.Arrays;
/**
* 归并排序
* @author Lining
* @date 2020/3/21 16:09
*/
public class MergeSort {
public static int[] MergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
/**
* 归并排序——将两段排序好的数组结合成一个排序数组
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
}
堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
/**
* 堆排序
* @author Lining
* @date 2020/3/21 16:18
*/
public class HeapSort {
public static void adjustHeap(int[] data,int i, int len) {
int temp, j;
temp = data[i];
for (j = 2 * i; j < len; j *= 2) { //沿关键字较大的孩子结点向下筛选
if (j < len && data[j] < data[j + 1]) {
++j; //j为关键字中较大记录的下标
}
if (temp >= data[j]) {
break;
}
data[i] = data[j];
i = j;
}
data[i] = temp;
}
public static void heapSort(int[] data) {
int i;
for (i = data.length / 2 - 1; i >= 0; i--) { //构建一个大顶堆
adjustHeap(data, i, data.length - 1);
}
for (i = data.length - 1; i >= 0; i--) { //将堆顶记录和当前未经排序子序列的最后一个记录交换
int temp = data[0];
data[0] = data[i];
data[i] = temp;
adjustHeap(data, 0, i - 1); //将a中前i-1个记录重新调整为大顶堆
}
}
}
计数排序
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
import java.util.Arrays;
/**
* 记数排序
* @author Lining
* @date 2020/3/21 16:51
*/
public class CountingSort {
public static int[] CountingSort(int[] array) {
if (array.length == 0) return array;
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return array;
}
}
桶排序
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。
import java.util.ArrayList;
/**
* 桶排序
* @author Lining
* @date 2020/3/21
*/
public class BucketSort {
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// 找到最大值最小值
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
if (bucketSize == 1) { // 如果带排序数组中有重复数字时
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
}
这篇文章有点苍白，因为感觉算法没什么好讲的和数学题一样一百年公式都不会换，记死了就行！！！
