------- android培训、java培训、期待与您交流！----------
几种排序方法的总结
常见的排序方有:选择排序,冒泡排序,快速排序等
1 选择排序:每个数都跟数组中的每个数循环比较,如果这个数比它小,那么就将这两个数位置置换
等每个数都比较完后,数组就按照从小到大进行排序了
例子讲解:
对下面的数组用选择排序进行排序
int[]arr={3,22,55,66,11,36,8,90,110};
思路:
先拿第一个数arr[0],循环的跟数组中每个数循环比较,如果arr[0]大于跟它比较的数,那么这两个数就交换位置,否则位置不动
当第一轮比较完毕后,arr[0]就是数组中的最小值了
代码演示:
//arr[0]循环的跟数组的其他元素比较
for(int x=1;arr.length;x++)
{
//如果符合条件就把两个数的位置置换
if(arr[0]>arr[x])
{
int temp=arr[0];
arr[0]=arr[x];
arr[x]=temp;
}
}
再拿第二个数arr[1],循环的跟数组中每个数循环比较,如果arr[1]大于跟它比较的数,那么这两个数就交换位置,否则位置不动
当第一轮比较完毕后,arr[1]比arr[0]大,但是小于数组中的其他值
//arr[1]循环的跟数组的其他元素比较
for(int x=2;arr.length;x++)
{
//如果符合条件就把两个数的位置置换
if(arr[1]>arr[x])
{
int temp=arr[1];
arr[1]=arr[x];
arr[x]=temp;
}
}
......
依据分析推出
数组的每一个元素都要循环的相互比较,所以要定义一个外循环,固定x的值,来进行比较
注意:x=arr.length-1的时候只剩下一个数了,不用比较了,所以外循环的x最大取到arr.length-2
外循环:
for(intx=0;x<arr.length-1;x++)
{
}
内循环就是判断条件,然后交换位置
for(inty=x+1;y<arr.length;y++)
{
if(arr[x]>arr[y])
{
int temp=arr[x];
arr[x]=arr[y];
arr[y]=temp;
}
}
2 冒泡排序:一个数组,第一次从第一个数开始,前一个数跟后一个数,做比较,如果前一个数比后一个数大,就把两个数的位置置换,否则不变,比较一趟后,最大的数就在最后面了(冒泡),然后从第二个数开始,前一个数跟后一个数做比较,如果前一个数比后一个数大,就把两个数的位置置换,通过循环比较后,从倒数第二个数开始,它跟最后一个数比较过后,数组就按照从小到大排序了
代码步骤和思路分析
第一次从第一个数开始比较
for(intx=0;x<arr.length;x++)
{
if(arr[x]>arr[x+1])
{
int temp=arr[x];
arr[x]=arr[x+1];
arr[x+1]=temp;
}
}
第二次从第二个数开始比较
for(intx=1;x<arr.length;x++)
{
if(arr[x]>arr[x+1])
{
int temp=arr[x];
arr[x]=arr[x+1];
arr[x+1]=temp;
}
}
.......
分析得知,x是变化的,所以要定义一个外循环控制x的值
外循环:
for(inty=0;y<arr.length-1;y++)
{
}
由上面得知,内循环x的初始化值,是随着外循环y的变化而变化的,不难推出冒泡排序的核心代码是:
for(inty=0;y<arr.length-1;y++)
{
//这里要注意角标越界问题x最多只能取到arr.length-2 ,因为x+1最大是arr.length-1 如果x=arr.length-1的话x+1就越界了
for(intx=y;x<arr.length-1;x++)
{
if(arr[x]>arr[x+1])
{
int temp=arr[x];
arr[x]=arr[x+1];
arr[x+1]=temp;
}
}
}
3 快速排序:快速排序的思路:先从数列中取出一个数作为基准数。分区过程，将比这个数大的数全放到它的右边，小于它的数全放到它的左边,再对左右区间重复第二步，直到各区间只有一个数。
思路和步骤:
int[] arr={23, 22, 11, 66, 55, 36, 8, 10, 110};
角标 0 1 2 3 4 5 6 7 8
定义一个临时变量temp记录数组中某一个值,通常是最左边,或者最右边的值赋给临时变量,这个值作为中间值
这里我们假设temp=arr[0],那么这时候就相当于把数组中的第一个元素挖空了,就要想办法把这个坑填回去
我们通常的做法是:
从数组的最后数起,找一个比中间值小的数填补arr[0]的空位
所以角标的初始值是arr.length-1
int j=arr.length-1
我们这里找到了arr[7]<temp,所以就把arr[0]=arr[7]
我们发现j不断的在减少,总有减到负数的时候,那么这就越界了,我们要为while循环设定一个界限j>=0
while(j>i&&arr[j]>temp)
{
j=j-1
}
找到比temp小的值后,就把arr[j]赋给arr[0],把这个坑给填了,填完坑之后,arr[0]肯定是比中间值小了,所以arr[0]不用再比较了,角标要加一
if(i<j)
{
arr[i]=arr[j];
i=i+1
}
右边把左边的坑添了之后,左边倒是完整了,但是右边又有坑了
这时候从左边开始找一个比中间值大的数,找到之后把右边的坑填上
while(i<j&&arr[i]<temp)
{
i++
}
if(i<j)
{
arr[j]=arr[i];
j++;
}
当i=j的时候第一轮比较结束,中间值放在i的角标上
然后我们再调用本函数,递归操作,直到只有一个元素为止
快速排序的代码如下
public static voidquickSort(int[] arr,int left,int right)
{
int i = left;//记录区间起始位置
int j = right;//记录区间末尾位置
//排序出口是left==right
if (left < right)
{
int temp = arr[left];//设置临时变量，记录参照点
while(i!=j)
{
//固定i，从右开始寻找小于参照的元素
while(i<j && arr[j]>temp)
{
j--;
}
//找到后将其放在i的位置
if (i<j)
{
arr[i] = arr[j];
i++;
}
//此时j固定，从左开始寻找大于参照的的元素
while(i<j && arr[i]<temp)
{
i++;
}
//找到后将其放在j的位置
if (i<j)
{
arr[j] = arr[i];
j--;
}
}
//当i==j时说明该区间的分配结束，将参照放置在其最终位置，i或j
arr[i] = temp;
//递归调用排序左区间
quickSort(arr,left,i-1);
//递归调用排序右区间
quickSort(arr,i+1,right);
}
}
4 排序的补充:
java.uti.*;
Arrays.sort(int [] arr) 把数组传进去也可以进行排序,是按照从小到大排序的,实际上它是封装了排序方法在里面,有了这个我们就不用自己写
排序方法了,直接调用就完事了.
数组的查找:折半查找,一定要是有序的数组才行
5 求最值
1)求数组的最大值
int[]arr={3,22,55,66,11,36,8,90,110};
求最大值的第一种方法:
思路:求最大值肯定要遍历数组的了,所以要用到for循环
先定义一个临时变量max用来存储最大值,变量的初始化值为arr[0]
遍历数组,循环的跟max比较,如果max<arr[x] 把arr[x]赋给max, 否则就不用变
代码步骤:
int[]arr={3,22,55,66,11,36,8,90,110};
int max=arr[0];
//遍历数组
for(intx=1;x<arr.length;x++)
{
//如果max<arr[x] 把arr[x]赋给max, 否则就不用变
if(max<arr[x])
{
int temp=max;
max=arr[x];
arr[x]=temp;
}
}
求最大值的第二种方法:
int[]arr={3,22,55,66,11,36,8,90,110};
Arrays.sort(arr);//调用Arrays.sort方法,数组默认为从小到大排序
int max=arr[arr.length-1];
求最大值的第三种方法:
int[]arr={3,22,55,66,11,36,8,90,110};
int max=arr[0];
int min=arr[0];
for(intx=1;x<arr.length;x++)
{
max=Math.max(max,arr[x]); //调用Math函数的max方法,返回两个数的较大的值
min=Math.min(min,arr[x]); ////调用Math函数的min方法,返回两个数的较小的值
}
------- android培训、java培训、期待与您交流！----------