基础算法
- 快速排序
- 冒泡排序
- 递归算法
快速排序
/**
* @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);
}
}
