亲宝软件园·资讯

展开

递归与排序算法

leo_host 人气:0

算法

递归

自己调用自己调用方法时传入不同的参数,使代码更加简洁

递归的调用机制:

  • 每次调用方法时,会创建一个新的栈空间(独立的),以及私有的局部变量(独立不会相互影响)

  • 当方法使用的是引用变量时,每个开辟的栈空间共用这一引用变量

  • 递归必须无限向递归结束条件靠近,否则会出现StackOverFlowError栈溢出错误

  • 当方法执行结束或这遇到返回时,谁调用就返回到那一层中

递归可以解决的问题

  • 问题描述是递归的(阶乘,斐波那契数列)

  • 问题的解法是递归的(汉诺塔问题)

  • 数据结构递归的(树的遍历,图的深度优先搜索)

八大排序算法

分类:

  1. 内部排序:使用内存进行排序

  2. 外部排序:使用外部存储排序

内部排序分类:

  1. 插入排序

    • 直接插入排序

    • 希尔排序

  2. 交换排序

    • 冒泡排序

    • 快速排序

  3. 选择排序

    • 简单选择排序

    • 堆排序

  4. 归并排序

  5. 基数排序

冒泡排序-时间复杂度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--;
}
if(arr[r]==pivot) {
l++;
}
}
if(l==r) {
l++;
r--;
}
//向左递归
if(left<r) {
quickSort(arr,left,r);
}

//向右递归
if(l<right) {
quickSort(arr, l, right);
}
}
}

归并排序-时间复杂度O(nlog2n)


算法规则:

采用分治策略,将数组分割值至大小为1的有序数组再依次进行合并,合并到最终的数据即为有序数组

public class MergeSort
{
public static void main(String[] args)
{
int arr[]= {8,4,5,7,1,3,6,2};
int temp[]=new int[arr.length];
mergeSort(arr, temp, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}

//分割
public static void mergeSort(int arr[],int temp[],int left,int right) {
if(left<right) {
//计算两组有序数组间隔索引(中间索引)
int mid=(left+right)/2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid+1, right);
merge(arr, temp, left, right, mid);

}
}

//归并
//arr[],待排序数组
//temp[]临时数组
//left左边有序数组索引
//reght右边有序数组索引
//mid中间索引
public static void merge(int arr[],int temp[],int left,int right,int mid) {
int i=left;//左边索引
int j=mid+1;//右边索引
int t=0;//临时数组索引
//1遍历两个有序数组将数据加入临时数组中
while(i<=mid&&j<=right) {
//左边小
if(arr[i]<arr[j]) {
temp[t]=arr[i];
t++;
i++;
}else {
temp[t]=arr[j];
t++;
j++;
}
}
//2将剩余数组数据加入临时数组中
while(i<=mid) {
//左边数组有剩余
temp[t]=arr[i];
t++;
i++;
}
while(j<=right) {
//右边数组有剩余
temp[t]=arr[j];
t++;
j++;
}
t=0;
//3拷贝临时数组数据到数据中
int innerIndex=left;
while(innerIndex<=right) {
arr[innerIndex]=temp[t];
innerIndex++;
t++;
}
}
}

 

基数排序-时间复杂度O(n*k)

算法思想:

将数据按照个位十位百位千位等排序,放入代表(0,1,2,3,4,5,6,7,8,9)的十个桶中,进行最大数位数次排序,最终可得到有序数组

例如541,若按个位排则放入第二个桶中,若按百位排则放入第五个桶

//桶排序
public class BucketSort
{
public static void main(String[] args)
{
int arr[]= {53,3,542,748,12,214};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}

public static void bucketSort(int arr[]) {
int max=0;
int number;
for(int value:arr) {
if(value>max) {
max=value;
}
}
int maxLength=(max+"").length();
//定义十个桶代表十个数字,每个桶的大小为最大数字的位数
int buckets[][]=new int[10][maxLength];
//定义一个数组记录每个桶内的数量
int indexs[]=new int[10];

for(int i=1,j=0;j<maxLength;i*=10,j+=1) {
//1将数据按个位十位百位千位数字大小排序放入对应桶内
for(int value:arr) {
number=value/i%10;//计算排序位的值
buckets[number][indexs[number]]=value;//存值
indexs[number]++;//索引+1
}
int index=0;
//2将数据从桶内取出并将索引数组清零
for(int b=0;b<indexs.length;b++) {
if(indexs[b]!=0) {
//桶内有数据
for(int p=0;p<indexs[b];p++) {
arr[index++]=buckets[b][p];
}
}
indexs[b]=0;
}
}
}
}
!!!此例子仅作整数排序,若做负数排序修改部分代码即可,思想一样,可以参照
   https://code.i-harness.com/zh-CN/q/e98fa9

 

堆排序


待更新

加载全部内容

相关教程
猜你喜欢
用户评论