欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

冒泡排序、快速排序(快排)、KMP算法的Java实现

程序员文章站 2022-05-17 12:32:34
...
人太懒了,好久没发文章了。今天就写点自己的算法实现吧。比较简单恐贻笑大方之家,但又觉得还是记录下来比较好。


  前两天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;
	}
	
	
	@Test
	public void test() {
		
		String targetStr = "56132asdasdasfsf4dasa123",
				queryStr = "dasa123";
		System.out.println(this.matchedStartIndex(targetStr, queryStr));
	}
}