#排序算法总结
1.冒泡排序
解释：
所谓冒泡排序，就是如同水里的泡泡一样，将合适的值一次次往上冒，直到所有数据全部处理完成。
在数据中的解释就是：从第一个数开始，每次都将前一个数与后一个数作比较，如果前一个数大于后一个数，则将两者交换位置（否则不交换），此时，后一个数值已变化，然后再将后一个数与后后一个数作比较，重复操作，直到所有的数都比较完成。
算法过程：
先定义一个外循环，控制整个排序次数（排序次数为数据的个数），然后再内嵌一个内循环，在内循环中进行每次排序的比较，内循环的比较次数为：数据个数-当前排序次数，因为，比如说，在第一次比较时，比较得出的结果一定是数据中的最大值，并排在最后，此时，最大值已知，不用再进行比较了，以此类推，每次都会减少一次比较。
时间复杂度：
第一次循环n，第二次循环n，综合为O(n^2)。
算法实现：
public class test1 {
public static void main(String[] args) {
int[] nums = {5,2,1,4,3,};
//下面进行冒泡排序
for(int i = 0;i < nums.length-2;i++) { //外层循环控制排序次数
for(int j = 0;j < nums.length-1-i;j++) { //内存循环控制每趟比较次数
if(nums[j] > nums[j+1]) { //交换位置操作
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
for(int x : nums) {
System.out.print(x + " ");
}
}
}
2.选择排序
解释：
所谓选择排序，就是每次选择出当前比较数据的最小值，然后将其传递到数据的前面。
算法过程：
第一步：定义一个外层循环，控制排序次数，循环次数为数据个数-1。
第二步：定义一个变量k，这个变量等于外层循环的次数的起始值 i ,目的是存放当前需要操作的数据的第一个数，以便与后面的数比较。
第三步：定义一个内层循环，这个内层循环代表着当前需要比较的次数，起始值为k+1，因为k是当前数据的第一个位置，不需要让自己比自己，结束位置为数据末端，即数据的长度。
第四步：将k位置的数与数据比较，如果比较的数小于k位置的数，则将这个索引赋给k，以此类推，最后每次比较结束都会找到当前数据的最小值。
第五步，将第i的位置的数据与k的数据交换，即将最小值放到前面。
第六步：再次操作以上步骤，直到数据全部完成。
时间复杂度：
O(n^2)
算法实现：
public class test1 {
public static void selectSort01(int[] nums) {
for(int i = 0;i < nums.length-1;i++) { //外层循环定义排序次数
int k = i; //获取每次操作的数据的第一个数据的索引，也就是每次从需要比较的第一个数开始（已经比较出的最小数不需要再比较）
for(int j = i + 1;j < nums.length;j++) {//内层循环将从第一个数开始往后比较。
if(nums[j] < nums[k]) { //判断前一个数和后一个数之间的大小
k = j; //后一个数如果小于前一个数，则将二者的索引交换
}
}
//上述得出当前比较数据的最小值
//下方较当前的最小值，与当前比较数据的开头数据进行交互，最小值将会传递到开始的位置，这个数及位置将不会参与下次比较
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}
public static void main(String[] args) {
int[] nums = {2,5,6,3,0,-4};
selectSort01(nums);
for(int x : nums) {
System.out.print(x + " ");
}
}
}
3.插入排序
解释：
所谓插入排序，就是将后面的数与前面的数比较，如果后面的数小于前面的数，就将后面的数插入到前面的数的前面。
算法过程：
所谓插入排序，就是从第二个数开始，依次向前比较，如果前面一个数小于这个数，那么就将前面一个数右移，将前面一个数的位置赋空（看了代码就明白），然后再比较这个数与前前一个数，如果前前一个数大于这个数，则将这个前前的数赋给这个空位置，前前一个数的原位置则就代表了空，重复以上操作，最后将空位置补上当前操作的数即可，直到全部比较完成。
时间复杂度：
O(n^2);
代码实现：
public static void insertSort(int[] nums) {
for(int i = 1;i < nums.length;i++) {
int target = nums[i]; //获得需要放到确定位置的元素
int j = i;
while(j > 0 && target < nums[j-1]) {
//判断所要比较的数的索引是否到了最开始的位置，并且比较的数是否小于其前面一个数
nums[j] = nums[j-1];
//如果判断成立，则将前一个数的数据右移，此时前一个数的位置为空，目的是用来存放目标值。
j--; //将索引-1，即再比较前面一个数(先减再比较）
}
nums[j] = target;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = {1,5,3,6,7};
insertSort(nums);
for(int num : nums) {
System.out.print(num);
}
}
}
4.快速排序
解释：
一个效率极其高的排序算法。
算法过程：
先设定一个基准（一般为数组最左边的数）。一个从左往右开始检索的起始索引，一个从右往左开始检索的起始索引（如果左索引大于有索引，则被认定为不合法，无需进行一下操作，须提前判断）。
然后先从数组右边开始向左边检索，直到检索的数小于基准（前提是该索引不能小于左边的索引），即先暂停，取出这个位置的索引 j。
然后再从左往右检索，直到检索的数大于基准（前提是该索引不能大于当前右边的索引），即先暂停。取出这个位置的索引 i。
交换两个索引位置的数。（在两种索引不相等的前提下，继续循环上述操作）。
当两个索引相遇时，此时索引右边的数就是全部大于基准的数，索引左边的数就是全部小于基准的数。
然后将相遇索引位置的数与基准交换。
然后分别递归相遇索引右边的数组和左边的数组（不含索引）
最终排序成功。
时间复杂度：
O(nlogn)；
注意问题：
每次检索时，必须先从右边开始检索，因为j在变，i < j始终需要成立。当然还得根据具体情况而定，这是个注意点。
代码实现：
public static void quickSort(int[] arr,int left,int right) {
if(left > right) { //判断左索引是否大于右索引，如果是，则不合法。直接返回退出排序。
return;
}
int base = arr[left]; //设置基准，一般为最左边的数
int i = left; //设定从左往右检索角标的实时位置
int j = right; //设定从有往左检索角标的实时位置
while(i != j) {
//从右往左检索比基准小的数，找到即先停下，且必须先从右往左执行
while(arr[j] >= base && i < j) {
j--;
}
//从左往右检索比基准大的数，找到即先停下
while(arr[i] <= base && i < j) {
i++;
}
//通过上述两个循环必定找到指定数，然后将两个数交换
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
//上述循环结束代表i==j了，即两个角标重合
//此时将基准与重合位置的数交换
arr[left] = arr[i];
arr[i] = base;
//递归继续执行上述操作
//递归排序左边的数
quickSort(arr, left, i - 1);
//递归排序有边的数
quickSort(arr, i+1, right);
}
#查找算法总结
1.二分查找（折半查找）
解释：
在一个事先排好序的数组中，查找一个数所在的索引位置。
算法过程：
*提前准备：
定义一个方法，设定两个参数，第一个为排好序的数组，第二个为需要查询的数。在方法内部定义三个变量，分别为top(代表每次查找部分的第一个数的索引)，bottom(代表每次查找部分的最后一个数的索引)，mid(代表每次查找部分的中间位置的数，mid=(top+bottom)/2)。
*过程：
首判断我们每次执行后的top和bottom是否不在同一位置，如果不在，则代表全部查完了也没找到，此时须返回查询失败标志，反之，代表还有数可查，继续查询。
每次查询的时候mid都会变成当前查询部分的中间值索引，然后判断该中间值是否与查询的数相等，若相等，则返回该中间值索引，查询成功。否则，判断，该中间值是大于查询值还是小于查询值。如果大于查询值，则代表查询的值一定在中间值索引的左边，否则，在其右边。此时，目标数组就会变成需要查询的部分，然后改变top和bottom及mid到对应的新值。重复执行以上过程，直到查询成功或失败。
代码实现：
public static int search(int[] nums,int num) {
int top = 0;
int bottom = nums.length - 1;
while(top <= bottom) {
int mid = (top + bottom)/2;
if(num == nums[mid]) {
return mid;
}else if(num < nums[mid]) { //代表目标数num在数组的左边
bottom = mid - 1;
mid = (top + bottom)/2;
}else { //代表目标数num在数组的右边
top = mid + 1;
mid = (top + bottom)/2;
}
}
return -1; //查询失败返回值
}