黑马程序员技术交流社区

标题: 看好多小伙伴都问排序的问题和算法的问题~~给大家分享一个 [打印本页]

作者: killuakillua898 时间: 2013-10-8 20:50
标题: 看好多小伙伴都问排序的问题和算法的问题~~给大家分享一个

数组中常见的算法

1. 获取数组中的极值1). 获取数组中的最大值 (最小值的思路相反)

(1). 思路1：

临时变量作为值最大的元素，初始化存放数组的第一个元素。

(2). 思路2：(存放元素的角标是比较正统的做法)

临时变量作为值最大的元素对应的角标(也就是索引0)，初始化为0。

[java] view plaincopy

/**
* 获取传入的数组的最大的索引值
* @param arr:要获取最大值的数组
* @return
*/
private static int getMaxIndex(int[] arr) {
//定义数组最大值的索引为数组的第一个元素角标0
int maxIndex =0;
//遍历数组中的每一个元素
for(int i=0; i<arr.length; i++){
//如果遍历到的数组元素的值比现有的最大值还大，就更新数组最大值的索引位置
if(arr >arr[maxIndex])
//把数值最大的索引值更新
maxIndex=i;
}
//返回找到的数组最大值对应的索引值
return maxIndex;
}
//测试程序
public static void main(String[] args) {
//定义要获取最大值的数组
int[] arr ={42, 111, 112, 35, 635};
//通过getMaxIndex方法获取数组中最大元素的索引值
int maxIndex =getMaxIndex(arr);
//打印获取到的数组最大的值的索引和对应的值
System.out.println("数组中最大的元素的位置: arr["+maxIndex+"] ="+ arr[maxIndex] );
}

2). 获取数组中的最大值
思路和获取数组的最小值类似。

作者: killuakillua898 时间: 2013-10-8 20:50
2. 数组中的排序算法
以从小到大排序作为案例
1). 选择排序 select sort
(1). 选择排序的基本思想：
[1]. 每次都拿数组中特定位置上的值和该位置以后的所有元素依次比较，如果这个元素比后面的元素的值大，那就换位。否则不换位。
[2]. 即使在一次循环中即使有换位发生，也仍然那这个值变化但是位置还是不变化的元素继续和数组中的该元素以后位置的元素进行比较。
[3]. 图例进行说明：

【*】选择排序形象记忆图：

特点：
{1}. 完成第n次循环之后，索引位置为0、1、2、…、n-1的元素是依次是这个数组的第1 min(最小的)、第2 min、第3 min、….、第n min的元素。
{2}.第x次循环能确定出第x-1位置上为数组的第x min的元素。（一定记住！！）
{3}. 完成一次循环，低位索引的元素固定下来
(2). 选择排序的示例代码
技巧：循环到最后一个角标的时候，只剩下一个元素，所以不用比较。
[java] view plaincopy
/**
   * 1. 选择排序
   */
public static void selectSort(int[] arr){
   for(int i=0; i<arr.length-1; i++){ //最后一个元素不用比较
         for(int j=i+1; j<arr.length; j++){
            if(arr[i] >arr[j]){
               swap(arr,i, j);
            }
         }
   }
}

[java] view plaincopy
/**
* 数组元素互换位置
*/
private static void swap(int[] arr, int x, int y){
int temp =arr[x];
arr[x]=arr[y];
arr[y]=temp;
}<span style="font-family: Arial, Helvetica, sans-serif;"> </span>
2). 冒泡排序 bubble sort
(1). 冒泡排序的基本思想：
[1]. 每次都是从第0位开始，相邻元素依次比较，如果低位的元素值大于相邻高位索引的元素的值，就换位。否则高位索引的元素和他下一个元素作比较。依次进行。
[2]. 图例说明

****特点：
{2}. ***第x次循环能确定出倒数第x-1位置上为数组的第x max的元素。****（一定记住！！）
{3}. 完成一次循环，高位索引的元素固定下来
【*】冒泡排序形象记忆图：

(2). 冒泡排序的实例代码
技巧：内层循环主要是a[j+1]和a[j]相邻元素之间的比较
这两个角标都要满足数组长度不越界
j+1 <=arr.length-1-i
j <=arr.length -1-i
不等式的交集 j<= arr.length –i-1
[java] view plaincopy
/**
   * 2. 冒泡排序
   */
public static void bubbleSort(int[] arr){
   for(int i=0; i<arr.length; i++){
         for(int j=0; j< arr.length-i-1; j++){
            swap(arr,j+1, j);
         }
   }
}

这是转自大神的帖子真心很有帮助  大家仔细看过的话会发现算法再也不是梦！！！！！希望大家有不会的多多交流~~我也是看过以后受益匪浅

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2