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