常见十四种的Java算法

一、简单列出常见的Java中14种算法

序号简称英文简介1二分查找法Binary Search

​二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

2冒泡排序算法Bubble SortSEO靠我它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。3插SEO靠我入排序算法Insertion sort 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。 4快速排序算法Quick sort对冒泡算法的一种改进。是指通过一趟排序将SEO靠我要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。5希尔排序算法SEO靠我Shells Sort

​希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法

6归并排序算法Merge Sort归并排序是建立在归并操作上的一SEO靠我种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。7桶排SEO靠我序算法Bucket sort桶排序也叫箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果SEO靠我。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。8基数排序算法Radix Sort基数排序（radix SEO靠我sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以SEO靠我达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。9剪枝算法pruning aSEO靠我lgorithms在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应SEO靠我当舍弃，哪些枝条应当保留的方法。10回溯算法Backtracking回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径SEO靠我。11最短路径算法从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，FloSEO靠我yd 算法和 SPFA算法等。12最大子数组算法13最长公共子序算法14最小生成树算法

二、具体介绍

1、二分查找法

（1）算法原理：

又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，SEO靠我如果中间位置 的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小， 则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有SEO靠我待查的关键字。 （2）代码示例： /*** 二分查找* @param srcArray 源数组* @param des 目标元素* @return 如果找到则返SEO靠我回索引位置，找不到则返回-1*/ public static int binarySearch(int[] srcArray, int des) {//定义初始最小、最大索引int sSEO靠我tart = 0;int end = srcArray.length - 1;//确保不会出现重复查找，越界while (start <= end) {//计算出中间索引值 >>> 逻辑右移 也就是 SEO靠我int middle = (end + start)/2int middle = (end + start)>>>1 ;//防止溢出if (des == srcArray[middle]) {retuSEO靠我rn middle;//判断下限} else if (des < srcArray[middle]) {end = middle - 1;//判断上限} else {start = middle + SEO靠我1;}}//若没有，则返回-1return -1; }

2、冒泡排序算法

（1）算法原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。 

对每一对相邻元素做同样的工作，从开始第一对到SEO靠我结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。 

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 

（2）代码示例：

public sSEO靠我tatic void bubbleSort(int arr[]) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.SEO靠我length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tSEO靠我emp;}}} } public static void bubbleSort2(int[] a, int n) {int i, j;for (i = 0; i < SEO靠我n; i++) {//表示 n 次排序过程。for (j = 1; j < n - i; j++) {if (a[j - 1] > a[j]) {//前面的数字大于后面的数字就交换//交换 a[j-1SEO靠我]和 a[j]int temp;temp = a[j - 1];a[j - 1] = a[j];a[j] = temp;}}} }

3、插入排序算法

（1）概念：通过构建有序序列，对于未排SEO靠我序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。

（2）一个通俗的比喻：

插入排序就类似于斗地主时，整理扑克牌的情况。第一次摸牌时，左收是空的，之后每次摸牌插入到左手的牌时，都会将这张牌和左手中SEO靠我已经排好序的牌，从右到左比较，确认这张牌该放的位置。

public static void insertionSort(int arr[]) {for (int i = 1; i < arr.lengtSEO靠我h; i++) {//插入的数int insertVal = arr[i];//被插入的位置(准备和前一个数比较)int index = i - 1;//如果插入的数比被插入的数小while (indSEO靠我ex >= 0 && insertVal < arr[index]) {//将把 arr[index] 向后移动arr[index + 1] = arr[index];//让 index 向前移动inSEO靠我dex--;}//把插入的数放入合适位置arr[index + 1] = insertVal;} }

4、快速排序算法

（1）概念：快速排序是指通过一趟排序将要排序的数据分割成独立的两部分SEO靠我，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

（2）快速排序的的过程简图：

选择一个关键值作SEO靠我为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。

—— 图片来源于网络

（3）代码示例： 

/*** 快速排序** @param arr 需要排序的数组* @paraSEO靠我m start 数组的最小索引： 0* @param end 数组的最大索引： arr.length - 1* @return 排序好的数组*/ public static int[]SEO靠我 quickSort(int arr[], int start, int end) {int pivot = arr[start];int i = start;int j = end;while (iSEO靠我 < j) {while ((i < j) && (arr[j] > pivot)) {j--;}while ((i < j) && (arr[i] < pivot)) {i++;}if ((arr[SEO靠我i] == arr[j]) && (i < j)) {i++;} else {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}if (i - 1 >SEO靠我 start) arr = quickSort(arr, start, i - 1);if (j + 1 < end) arr = quickSort(arr, j + 1, end);return SEO靠我(arr); } /*** 快速排序（无返回值）* @param a 需要排序的数组* @param low 数组的最小索引： 0* @param high 数组的最SEO靠我大索引： arr.length - 1*/ public static void quickSort2(int[] a, int low, int high) {int start =SEO靠我 low;int end = high;int key = a[low];while (end > start) {//从后往前比较while (end > start && a[end] >= keSEO靠我y)//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较end--;if (a[end] <= key) {int temp = a[end];a[end] = a[sSEO靠我tart];a[start] = temp;}//从前往后比较while (end > start && a[start] <= key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位SEO靠我置start++;if (a[start] >= key) {int temp = a[start];a[start] = a[end];a[end] = temp;}//此时第一次循环比较结束，关键SEO靠我值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用}//递归if (start > low) quickSort2(a, low, sSEO靠我tart - 1);//左边序列。第一个索引位置到关键值索引-1if (end < high) quickSort2(a, end + 1, high);//右边序列。从关键值索引+1 到最后一个 SEO靠我 }

5、希尔排序算法

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

（2）代码示例：

/*SEO靠我** 希尔排序* @param a */ private static void shellSort(int[] a) {int dk = a.length / 2;while (dkSEO靠我 >= 1) {//类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了for (int i = dk; i < a.length; i++) {if (a[i] < SEO靠我a[i - dk]) {int j;int x = a[i];//x 为待插入元素a[i] = a[i - dk];for (j = i - dk; j >= 0 && x < a[j]; j = jSEO靠我 - dk) {//通过循环，逐个后移一位找到要插入的位置。a[j + dk] = a[j];}a[j + dk] = x;//插入}}dk = dk / 2;} }

6、归并排序算法

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

（2）归并排序：是建立SEO靠我在归并操作上的一种有效，稳定的排序算法。

什么是归并操作？

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如　设有数列{6，202，100，301，38，8，1}SEO靠我 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并SEO靠我后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4SEO靠我+4=11； 逆序数为14；

（2）代码示例：

/*** 归并排序* @param nums 待排序数组* @param l 开始索引：0* @param h 最大索引：nums.lengSEO靠我th - 1* @return 排序好的数组*/ public static int[] mergeSort(int[] nums, int l, int h) {if (l == hSEO靠我)return new int[]{nums[l]};int mid = l + (h - l) / 2;int[] leftArr = mergeSort(nums, l, mid); //左有序数SEO靠我组int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组int[] newNum = new int[leftArr.length + rightASEO靠我rr.length]; //新有序数组int m = 0, i = 0, j = 0;while (i < leftArr.length && j < rightArr.length) {newNumSEO靠我[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];}while (i < leftArr.length)newNum[mSEO靠我++] = leftArr[i++];while (j < rightArr.length)newNum[m++] = rightArr[j++];return newNum; }

7、SEO靠我桶排序算法

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

（2）排序过SEO靠我程：

找出待排序数组中的最大值 max、最小值 min我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1遍历SEO靠我数组 arr，计算每个元素 arr[i] 放的桶每个桶各自排序

（3）代码示例：

/*** 桶排序** @param data 待排序数组*/ public static void bucSEO靠我ketSort(int data[]){int n = data.length;int bask[][] = new int[10][n];int index[] = new int[10];int SEO靠我max = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {max = max > (Integer.toString(data[i]).length()SEO靠我) ? max : (Integer.toString(data[i]).length());}String str;for (int i = max - 1; i >= 0; i--) {for (SEO靠我int j = 0; j < n; j++) {str = "";if (Integer.toString(data[j]).length() < max) {for (int k = 0; k < SEO靠我max - Integer.toString(data[j]).length(); k++)str += "0";}str += Integer.toString(data[j]);bask[str.SEO靠我charAt(i) - 0][index[str.charAt(i) - 0]++] = data[j];}int pos = 0;for (int j = 0; j < 10; j++) {for SEO靠我(int k = 0; k < index[j]; k++) {data[pos++] = bask[j][k];}}for (int x = 0; x < 10; x++) index[x] = 0SEO靠我;} }

8、基数排序算法

（1）基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。

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

（3）代码示例：

/*** 基数排序* @param number 待排序的数组* @param d SEO靠我表示最大的数有多少位*/ public static void sort(int[] number, int d) {int k = 0;int n = 1;int mSEO靠我 = 1; //控制键值排序依据在哪一位int[][] temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9int[] order = new iSEO靠我nt[10]; //数组order[i]用来表示该位是i的数的个数while (m <= d) {for (int i = 0; i < number.length; i++) {int lsd = SEO靠我((number[i] / n) % 10);temp[lsd][order[lsd]] = number[i];order[lsd]++;}for (int i = 0; i < 10; i++) SEO靠我{if (order[i] != 0)for (int j = 0; j < order[i]; j++) {number[k] = temp[i][j];k++;}order[i] = 0;}n *SEO靠我= 10;k = 0;m++;} }

未完待续-------