【算法】【数组与矩阵模块】求数组中需要排序的最短子数组长度

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题

给定数组arr，求arr中需要排序的最短子数组的长度是多少？
如：
arr = 1,2,3,2,35,8,9
结果为5，
{3,2,35,8,9} 子数组需要排序

解决方案

原问题：
1、申请4个变量，right表示需要移动位置的最右边元素、left表示需要移动位置的最左边元素、cur表示当前游标、min表示遍历到目前的最小值
2、从右往左遍历，如果遇到cur>min的情况，则right = cur
3、再从左往右遍历，如果遇到cur > max的情况，则left = cur
原则：只要需要移动位置的元素都属于需要排序的子数组内

代码编写

java语言版本

原问题：

/*** 二轮测试：需要排序的最短子数组长度* @param arr* @return*/public static int sortLenCp1(int[] arr) {if (arr == null || arr.length == 0) {return 0;}// 边界值，为遍历到目前，最值数int bound = 0;// 遍历到目前，在最值数另一边导致顺序乱序的最左边或者最右边的数int indexleft = -1, rightIndex = -1;int i = arr.length-1;bound = arr[arr.length-1];while (i >= 0) {if (arr[i] < bound) {// 最值更新bound = arr[i];}else if (arr[i] > bound){// 更新需要移动到i右边的最左边的数indexleft = i;}i--;}// 从左到右遍历i = 0;bound = arr[0];while (i < arr.length) {if (arr[i] > bound) {bound = arr[i];}else if (arr[i] < bound){rightIndex = i;}i++;}if (indexleft == -1 && rightIndex == -1){
//            整个数组都是有序的return 0;}else{return rightIndex - indexleft + 1;}}public static void main(String[] args) {System.out.println(sortLenCp1(new int[]{1,2,3,2,35,8,9}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题就表达了一个原则，只要当前元素在排序中需要移动位置，那么一定就在需要排序的子数组中。根据这个该算法就能够在O（n）的时间内计算出子数组的长度以及子数组了。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给[e-mail]
再次感谢左大神对我算法的指点迷津！