冒泡排序、快速排序(快排)、KMP算法的Java完成ITeye - 牛牛娱乐

冒泡排序、快速排序(快排)、KMP算法的Java完成ITeye

2019-01-10 15:14:41 | 作者: 鑫鹏 | 标签: 算法,完成,排序 | 浏览: 275

人太懒了,好久没发文章了。今日就写点自己的算法完成吧。比较简略恐贻笑大方之家,但又觉得仍是记录下来比较好。


  前两天qq的群里有人再说他老迈不明白java但在招聘Java工程师。所以就挑选言语无关又能调查下才能的最大公约数----算法。大概是冒泡排序、快速排序(快排)、二分查找、KMP算法。
  做Java我们都懂,能够经过comparable和Comparator的办法来便利的排序,所以我们往常对这些根底的算法都陌生了。也为了训练下本身的算法逻辑,就自己试着完成了一遍。可能会和我们找的算法完成很类似,只能说简略算法的完成仍是比较难立异的。
经过Junit的办法测验的,引入了apache common的一点东西办法,但这些不重要,我们看代码吧。
package algorithm;
import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;
import org.junit.Test;
public class SortTest {
 private Integer[] generateTestArray() {
 ArrayList Integer originList = new ArrayList ();
 Random random = new Random(LocalDateTime.now().toEpochSecond(ZoneOffset.ofHours(8)));
 Stream.generate(random::nextInt).limit(20).forEach(originList::add);
 System.out.println(originList);
 Integer[] tempArr = new Integer[20];
 originList.toArray(tempArr);
 return tempArr;
 @Test
 public void nnnnn() {
 Integer[] tempArr = generateTestArray();
 for (int i = 0; i tempArr.length - 1; i++) {
 boolean swapFlag = false;
 for (int j = 0; j tempArr.length - 1 - i; j++) {
 if (tempArr[j] tempArr[j + 1]) {
 int temp = tempArr[j];
 tempArr[j] = tempArr[j + 1];
 tempArr[j + 1] = temp;
 swapFlag = true;
 if (swapFlag == false) {
 break;
 Arrays.stream(tempArr).forEach(System.out::println);
 public int middleIndex(Integer[] tempArray, int low, int high) {
 int temp = tempArray[low];
 while (low high) {
 while (low high tempArray[high] temp) {
 high--;
 tempArray[low] = tempArray[high];
 while (low high tempArray[low] temp) {
 low++;
 tempArray[high] = tempArray[low];
 tempArray[high] = temp;
 return high;
 public void recursiveByQuickSort(Integer[] tempArray, int low, int high) {
 if (low high) {
 int middleIndex = middleIndex(tempArray, low, high);
 recursiveByQuickSort(tempArray, low, middleIndex - 1);
 recursiveByQuickSort(tempArray, middleIndex + 1, high);
 @Test
 public void quickSort() {
 Integer[] tempArray = generateTestArray();
 recursiveByQuickSort(tempArray, 0, tempArray.length - 1);
 System.out.println(Arrays.asList(tempArray));
 tempArray = new Integer[]{-2127313485, -2022230754, -1525774655, -1266487529, -1246088751, -1237557299, -1220678150, -669061349, -587792801, -441728115, -388929620, -228781073, -5476750, 424415588, 631901841, 878929975, 1519073389, 1526646025, 1791609759, 2002233420};
 System.out.println(Arrays.asList(tempArray));
 System.out.println(binaryQuery(tempArray, -587792801));
 private int binaryQuery(Integer[] tempArray, int val) {
 int low = 0, high = tempArray.length - 1;
 while (low high) {
 int middle = (low + high) / 2;
 if (tempArray[middle] val) {
 low = middle + 1;
 } else if (tempArray[middle] val) {
 high = middle - 1;
 } else {
 return middle;
 if (low == high tempArray[low] == val) {
 return low;
 return -1;


package algorithm;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.junit.Test;
public class KMPTest {
 private int[] suffixMatchPrefixMatchSequence(String queryStr) {
 char[] charArray = queryStr.toCharArray();
 int charLength = charArray.length,
 lastIndex = charLength - 1;
 if (charLength = 2) {
 return null;
 final int[] matchSequence = new int[charLength];
 outFor : for (int i = 1; i charLength; i++) {
 int tempI = i;
 for (int j = 0; j lastIndex tempI charLength; j++, tempI++) {
 char ic = charArray[tempI];
 char jc = charArray[j];
 if (ic != jc) {
 matchSequence[tempI] = 0;
 break;
 matchSequence[tempI] = j + 1;// 做偏移的减法操作,所以从1开端
 if (tempI == lastIndex) {
 break outFor;
 System.out.println(StringUtils.join(matchSequence, ,));
 return matchSequence;
 public int matchedStartIndex(String targetStr, String queryStr) {
 char[] targetCharArray = targetStr.toCharArray(),
 queryCharArray = queryStr.toCharArray();
 int targetCharArrayLength = targetCharArray.length, 
 queryCharArrayLength = queryCharArray.length, 
 matchStartIndex = 0,
 queryLastIndex = queryCharArrayLength - 1;
 final int[] matchSequence = this.suffixMatchPrefixMatchSequence(queryStr);
 while (matchStartIndex targetCharArrayLength) {
 int tempMatchStartIndex = matchStartIndex;
 int i = 0;
 for (; i queryCharArrayLength tempMatchStartIndex targetCharArrayLength; i++, tempMatchStartIndex++) {
 char qc = queryCharArray[i],
 tc = targetCharArray[tempMatchStartIndex];
 if (qc == tc) {
 continue;
 break;
 if (i queryLastIndex) {// 彻底匹配后还会做+1操作,所以条件加上 
 return matchStartIndex;
 matchStartIndex += ArrayUtils.isEmpty(matchSequence) ? 1 : (i - matchSequence[i]) == 0 ? 1 : i - matchSequence[i];
 return -1;                          
			
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表牛牛娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章

阅读排行

  • 1

    java多线程(七)ITeye

    线程,倾向,目标
  • 2

    java线程池ITeye

    线程,使命,工人
  • 3
  • 4
  • 5

    修饰符ITeye

    润饰,能够,直接
  • 6
  • 7
  • 8

    第02章 根底中心ITeye

    目标,根底,中心
  • 9
  • 10