[TOC] # 基础算法 - 快速排序 - 冒泡排序 - 递归算法 ## 快速排序 ```java /** * @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] ```java /** * @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)); } } } ``` ## 递归算法 - 其实递归算法很简单，简单点就是自己调用自己的方法，有条件判断什么时候停止！ ```java /** * @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); } } ```