Java 基础算法 | Eddie'Blog
Java 基础算法

Java 基础算法

eddie 374 2020-09-03

基础算法

  • 快速排序
  • 冒泡排序
  • 递归算法

快速排序

/**
 * @author eddie.lee
 * @ProjectName test
 * @Package com.lwc.test.test
 * @ClassName QuickSort
 * @description
 * @modified by
 */
public class QuickSort {

	private static void QuickSort(int[] array, int start, int end) {
		if (start < end) {
			// 初始化保存基元
			int key = array[start];
			// 初始化i,j
			int i = start, j;
			for (j = start + 1; j <= end; j++) {
				// 如果此处元素小于基元,则把此元素和i+1处元素交换,并将i加1,如大于或等于基元则继续循环
				if (array[j] < key) {
					int temp = array[j];
					array[j] = array[i + 1];
					array[i + 1] = temp;
					i++;
				}
			}
			// 交换i处元素和基元
			array[start] = array[i];
			array[i] = key;
			// 递归调用
			QuickSort(array, start, i - 1);
			QuickSort(array, i + 1, end);
		}
	}

	public static void main(String[] args) {
		int[] array = new int[] { 11, 213, 134, 44, 77, 78, 23, 43 };
		QuickSort(array, 0, array.length - 1);
		for (int i = 0; i < array.length; i++) {
			System.out.println("第[" + (i + 1) + "]轮,排序结果:" + array[i]);
		}
	}
}

冒泡排序

源数据:2, 1, 3, 4, 5

排序结果:[1, 2, 3, 4, 5]

/**
 * @author eddie.lee
 * @ProjectName test
 * @Package com.lwc.test.test
 * @ClassName BubbleOptimization
 * @description 冒泡排序的性能分析和算法优化(外层循环优化)
 * @modified by
 */
public class BubbleOptimization {

	/**
	 * 问题: 有的冒泡经过第一轮的交换已经是有序的了,如:2 1 3 4。数据越多的时候越慢,非常不适合大数据的排序
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int arr[] = { 2, 1, 3, 4, 5 };
		int temp;
		int flag;
		for (int i = 0; i < arr.length - 1; i++) {
			flag = 0;
			for (int j = 0; j < arr.length - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					flag = 1;
				}
			}
			if (flag == 0) {
				return;
			}
			/**
			 * 解决办法 如果用一个flag来判断一下,当前数组是否已经有序,如果有序就退出循环,这样可以明显的提高冒泡排序的性能。
			 */
			System.out.println("第[" + (i + 1) + "]轮,排序结果:" + Arrays.toString(arr));
		}
	}

}

递归算法

  • 其实递归算法很简单,简单点就是自己调用自己的方法,有条件判断什么时候停止!
/**
 * @author eddie.lee
 * @ProjectName test
 * @Package com.lwc.test.test
 * @ClassName test12
 * @description 递归算法
 * @modified by
 */
public class test12 {

	/**
	 * 开始传入的是10,所以开始是由 else 起始 = (10,9,8,7,6,5,4,3,2,1),因为一直 i != 1 , 所以一直 else 直到 i == 1 开始,在一直 (1,2,3,4,5,6,7,8,9,10)
	 * 
	 * @param i = 10
	 *
	 * @return 3628800
	 */
	public static long factorial(int i) {
		// 递归体
		if (i == 1) {
			return 1;
			// 递归头
		} else {
			return i * factorial(i - 1);
		}
	}

	/**
	 * 递归是一种常见的解决问题的方法,寄把问题逐渐简单化。递归的基本思想就是 “自己调用自己”,一个使用递归技术的方法会直接或间接的调用自己
     * 
	 * 递归构造包括两个部分: 
     *                      定义递归头。什么时候不调用自身方法,如果没有头,将陷入死循环 
     *                      递归体。什么时候需要调用自身方法
	 *
	 * 其实递归算法很简单,简单点就是自己调用自己的方法,有条件判断什么时候停止!
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		long num = factorial(10);
		System.out.println(num);

	}

}


# Java