递归与排序算法
递归
自己调用自己调用方法时传入不同的参数，使代码更加简洁
递归的调用机制:
-
每次调用方法时，会创建一个新的栈空间(独立的)，以及私有的局部变量(独立不会相互影响)
-
当方法使用的是引用变量时,每个开辟的栈空间共用这一引用变量
-
递归必须无限向递归结束条件靠近，否则会出现StackOverFlowError栈溢出错误
-
递归可以解决的问题
-
问题描述是递归的(阶乘，斐波那契数列)
-
问题的解法是递归的(汉诺塔问题)
-
数据结构递归的(树的遍历，图的深度优先搜索)
八大排序算法
分类：
-
内部排序：使用内存进行排序
-
外部排序：使用外部存储排序
内部排序分类：
-
插入排序
-
直接插入排序
-
希尔排序
-
-
交换排序
-
冒泡排序
-
快速排序
-
-
选择排序
-
简单选择排序
-
堆排序
-
-
归并排序
-
基数排序
冒泡排序-时间复杂度O(n2)
算法规则:
遍历数组如果遇到逆序则进行数据交换
public class BubbleSort
{
public static void main(String[] args)
{
int arr[]= {1,2,3,5,4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr【】 待排序数组
public static void bubbleSort(int arr[]) {
boolean flag=false;//作为标记数组数据是否发生交换
int temp;//作为交换数据的临时变量
//外层控制循环次数
for(int i=0;i<arr.length-1;i++) {
System.out.println("第"+i+"次排序");
//内层控制数据排序
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=true;
}
}
if(!flag) {
break;
}else {
flag=false;
}
}
}
}
冒泡算法优化：
定义一个标记变量flag，判断flag的值是否发生改变，若没改变则数组已经有序则可以提前跳出循环
选择排序-时间复杂度O(2)
算法规则：遍历数组，将每次遍历得到的最小值，与起始位置数据做交换
arr[0]-arr[n-1],找出最小值与arr[0]交换
arr[1]-arr[n-1],找出最小值与arr[1]交换,以此类推
public class SelectSort
{
public static void main(String[] args)
{
int arr[]= {101,34,119,1,-1,90,123};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序数组
public static void selectSort(int arr[]) {
int min;//最小值记录
int minIndex;//最小值下标记录
//外层控制循环次数
for(int i=0;i<arr.length-1;i++) {
min=arr[i];
minIndex=i;
//内层从i开始遍历数组进行排序
for(int j=i+1;j<arr.length-1;j++) {
//存在小于临时最小值则替换最小值并记录下标
if(arr[j]<min){
min=arr[j];
minIndex=j;
}
}
//数据交换
if(minIndex!=i) {
arr[minIndex]=arr[i];
arr[i]=min;
}
}
}
}
选择排序优化:
判断最小值位置是否发生改变，若没有则不需要进行数据交换
插入排序-时间复杂度O(n2)
算法规则:
假定两个数组，一个是原数组(大小为n-1)，一个是有序数组(大小为1，存放原数组的第一个元素)。将原数组中的数据依次取出放入有序数组中的适当位置，将原数组数据取出完毕后，则排序完毕
public class InsertSort
{
public static void main(String[] args)
{
int arr[]= {101,34,119,1,-1,89};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序数组
public static void insertSort(int arr[]) {
int value,insertIndex;
//假定第一个为有序，从下一位开始插入
for(int i=1;i<arr.length;i++) {
value=arr[i];
insertIndex=i-1;
//循环条件：插入位置没到数组第一位以及插入位置数据大于待插入数据
while(insertIndex>=0 && arr[insertIndex]>value) {
arr[insertIndex+1]=arr[insertIndex];//插入位置数据后移
insertIndex--;//插入位置前移
}
//找到插入位置
if(insertIndex!=i) {
arr[++insertIndex]=value;
}
}
}
}
算法优化：
判断插入位置是否发生改变决定是否进行数据插入
希尔排序-时间复杂度O(nlog2n)
算法规则:
将数组按照一定增量分组，对每组进行插入排序，继续减少增量，插入排序，当增量减少为1时，则进行最后的插入排序，结果即为有序的
public class ShellSort
{
public static void main(String[] args)
{
int arr[]= {8,9,1,7,2,3,5,4,6,0,11,0,12,3,7};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序数组
public static void shellSort(int arr[]) {
int value,index;
//定义增量(组数),每次除以2
for(int gap=arr.length/2;gap>0;gap/=2) {
//组内进行插入排序
for(int i=gap;i<arr.length;i++) {
value=arr[i];
//循环条件：当插入位置(i-gap)>=0并且插入位置的值大于待插入数据
while(i-gap>=0&&arr[i-gap]>value) {
arr[i]=arr[i-gap];
i-=gap;
}
//找到插入位置
arr[i]=value;
}
}
}
}
快速排序-时间复杂度O(nlog2n)
算法规则：
将数组按照大于小于中间值分类，向左向右递归得到有序数组
public class QuickSort
{
public static void main(String[] args)
{
int arr[]= {-9,78,0,23,-567,70};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
//arr[]待排序数组，left数组左边索引，right数组右边索引
public static void quickSort(int arr[],int left,int right) {
int l=left;//当前数组左索引
int r=right;//当前数组右索引
int pivot=arr[(left+right)/2];//中间值用于判断数据
int temp;
while(l<r) {
//找左边大于等于中间值的数据
while(arr[l]<pivot) {
l++;
}
//找右边大于等于中间值的数据
while(arr[r]>pivot) {
r--;
}
//判断是否循环结束
if(l>=r) {
break;
}
//左右数据交换
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
//防止存在相同值时死循环
if(arr[l]==pivot) {
r--;
}