本文共 3913 字，大约阅读时间需要 13 分钟。

执行效率从快到慢：快速、希尔、插入、选择、冒泡排序

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;}