执行效率从快到慢：快速、希尔、插入、选择、冒泡排序
1.数组逆序
实现思想：第一个递增，最后一个递减
//数组元素逆序 public static void receive(int[] arr){ for (int start = 0, end = arr.length-1; start < end; start++,end--) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; receive(arr); //输出结果：9,5,8,7,2,1,6,4,3
2.选择排序
实现思想：从左往右比较找到最小值，从左往右依次排放。
// 选择排序 public static void select_sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { //选择排序的优化 int k = i; for (int j = k + 1; j < arr.length - 1; j++) { // 找到最小值的下标 if (arr[j] < arr[k]) { k = j; } } if (k != i) { int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } } }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; select_sort(arr); //输出结果：1,2,3,4,5,6,7,8,9
深入了解：https://www.cnblogs.com/shen-hua/p/5424059.html
3.冒泡排序
实现思想：从头开始，依次相邻比较，把最大的放到最后边
//冒泡排序 public static void bubbleSort(int[] arr) { //功能 //外层循环用来控制数组循环的圈数 for (int i = 0; i < arr.length-1; i++) { //j < arr.length-1 为了避免角标越界 //j < arr.length-1-i 为了比较效率,避免重复比较 //内层循环用来完成元素值比较，把大的元素值互换到后面 for (int j = 0; j < arr.length-1-i; j++) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; bubbleSort(arr); //输出结果：1,2,3,4,5,6,7,8,9
4.普通查找
实现思想：遍历数组，查找相同的元素
//普通查找 public static int getArrayIndex(int[] arr, int number) { //把数组中的元素依次与指定的数值 进行比较 for (int i = 0; i < arr.length; i++) { if (arr[i] == number) { //找到了 return i; } } return -1; }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; int arrayIndex = getArrayIndex(arr, 1); System.out.println(arrayIndex); //输出结果：3
5.二分法查找
实现思想：已知是排好序的数组，用中间元素和要查找的元素比较，大的话取左边
//二分查找法(折半查找法) public static int halfSearch(int[] arr, int number) { //定义3个变量，用来记录min, min, mid的位置 int min = 0; int max = arr.length-1; int mid = 0; while (min <= max) { mid = (min + max) / 2; //没找到更新范围，继续比较 if (arr[mid] > number) { //在左边 max = mid - 1; } else if (arr[mid] < number) { //在右边 min = mid + 1; } else { return mid; } } return -1; }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; bubbleSort(arr); int arrayIndex = halfSearch(arr, 3); System.out.println(arrayIndex); //输出结果：2
https://www.cnblogs.com/kangyi/p/4262169.html
6.快排
实现思想：小的放前边，找一个index，放最小的索引，循环一轮得到一个最小值
public static void quickSort(int[] arr) { if (null == arr) { System.out.println("传入的数组为空！！！"); } for (int i =0;i < arr.length;i++) { int index = i; for (int j = i;j < arr.length;j++) { if (arr[index] > arr[j]) { index = j; } } if (index != i) { int temp = arr[index]; arr[index] = arr[i]; arr[i] = temp; } } }
int[] arr = {3, 4, 6, 1, 2, 7, 8, 5, 9}; quickSort(arr); //输出结果：1,2,3,4,5,6,7,8,9
7.快速排序
实现思想：挖坑填数+分治法
思想：先取一个基数，下标从右向左找比基数小的，从左向右找比基数大的，找到和基数互换位置，然后进行下一轮操作，然后递归调用快排算法。
public static void quick_sort(int[] arr, int l, int r) { if (l < r) { // 确定数组下标的范围 int i = l, j = r; // 先确定基准数 int flag = arr[l]; while (i < j) { // 下标j从右往左递减，找比基数小的数 while (i < j && flag < arr[j]) j--; if (i < j) { // 找到填补基数坑 arr[i] = arr[j]; i++; } // 下标i从左往右递增，找比基数大的数 while (i < j && flag > arr[i]) i++; if (i < j) { // 找到填补新坑 arr[j] = arr[i]; j--; } } // 将原来的基准值放入中间数 arr[j] = flag; // 递归调用 // 中间数的左边递归调用 quick_sort(arr, l, i - 1); // 中间数的右边递归调用 quick_sort(arr, i + 1, r); } }
8.递归算法
优点：
1.代码简洁
2.在树的遍历算法中，递归的实现比循环多
缺点：
1.由于是函数调用自身，时间和空间消耗比较大
2.递归中很多计算都是重复的，效率比较低
递归的优化：
使用动态规划：将可能出现的结果全部计算并保存，直到得到所需要的结果
int Fib(unsigned n) { if(n==1)return 1; if(n==0)return 0; return Fib(n-1)+Fib(n-2); } int Fib(unsigned n) { int* f=new int[n+1]; f[1]=1;f[0]=0; for(int i=0;i<=n;i++); f[i]=f[i-1]+f[i-2]; int r=f[n]; return r; }
