黑马程序员——数组、常见排序

------- <a href="http://www.itheima.com" target="blank">android培训</a>、<a href="http://www.itheima.com" target="blank">java培训</a>、期待与您交流！ ----------

-内存结构

java程序在运行时，需要在内存中的分配空间。为了提高运算效率，有时空间进行了不同区域的划分，因为每一片区域都有特定的处理数据方式和内存管理方式。

栈内存

用于存储局部变量，当数据使用完，所占空间会自动释放。

堆内存

数组和对象，通过new建立的实例都存放在堆内存中

没一个实体都有内存地址值

实体中的变量都有默认初始化值

实体不再被使用，会在不确定的时间内被垃圾回收器回收

方法区、本地方法区、寄存器

数组的定义，引用，复制，垃圾回收的分析简图：

（注意：定义数组时建议写 int[] arr = new int[3] ,而不书写 int arr[] = new int[];）

-创建数组例子：

package day04Array;

public class ArrayDemo {

	public static void main(String[] args) {
		int[] arr= new int[2];//默认都赋值为0
		int arr1[]= new int[3];//不建议这样写
		
		int[] arr2= new int[]{3,1,5,5,9};//数组静态初始化
		int[] arr3= {3,1,5,5,9};//上面一句可以简化写成这样
		System.out.println(arr3[2]);
		
		int[] arr4= new int[5];
		arr4[0]= 90;
		arr4[1]= 100;
		
		int[] arr5= new int[3];
		System.out.println(arr[3]);//出现 ArrayIndexOutOfBoundsException异常
								   //即操作数组数据时，访问到了数组中不存在的角标
		arr5= null;
		System.out.println(arr5[1]);//出现NullPointerException 异常
									//空指针异常：当引用没有任何指向值 为null的情况下，该引用还在用于操作实体

	}

}

package day04Array;

public class DyadicArray {

	public static void main(String[] args) {
		
		int[] arr= new int[3];//一维数组
		int[][] arr1= new int[3][4];//定义了名称为arr1的二维数组，二维数组中有3个一维数组
		System.out.println(arr1[0][1]);//默认数组中的元素为0
		/*
		int[][] arr2= new int[3][];
		System.out.println(arr2);
		System.out.println(arr2[0]);//结果是什么？ 为什么？
		arr2[0]= new int[3];
		arr2[1]= new int[1];
		arr2[2]= new int[2];
		
		System.out.println(arr2.length);//打印二维数组arr2的长度是3；
		System.out.println(arr2[1].length);//打印二维数组中第二个一维数组长度
		*/
		
		int[][] arr3= {{3,3,2,1},{4,5,2,8},{9,1,0,3}};
		
		int sum= 0;
		for(int x=0;x<arr3.length;x++){
			for(int y=0;y<arr3[x].length;y++){
				sum +=arr3[x][y];
			}
		}
		System.out.println("sum="+sum);
	}

}

-获取数组最值的例子

package day04Array;
/**
 * 练习1：遍历数组中的元素
 * 练习2：获取数组中的最值
 */
public class GetMaxMin {

	public static void main(String[] args) {
		int[] arr= new int[]{3,1,4,6,9,11};//可以直接写出{3,1,4,6,9,11};
		traversalArray(arr);
		int max= getMax(arr);
		System.out.println("max = "+max);
		int min= getMin(arr);
		System.out.println("min = "+min);

	}
	
	//遍历数组中的元素
	public static void traversalArray(int[] arr){
		for(int x=0;x<arr.length;x++){
			if(x!=arr.length-1)
				System.out.print(arr[x]+",");
			else
				System.out.println(arr[x]);
		}
	}
	
	//获取最大值（通过比较角标方式）
	public static int getMax(int[] arr){
		int max= 0;
		for(int x=1;x<arr.length;x++){
			if(arr[x]>arr[max])
				max= x;
		}
		return arr[max];
	}
	//获取最小值（通过比较数组元素值）
	public static int getMin(int[] arr){
		int min= arr[0];
		for(int x= 1;x<arr.length;x++){
			if(arr[x]<min)
				min= arr[x];
		}
		return min;
	}
	/*
	//获取double类型数组的最大值，函数名相同，通过重载方式实现
	public static double getMax(double[] arr){
		return 0;
	}
	*/
}

-选择排序：

思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。

关键问题：在剩余的待排序记录序列中找到最小关键码记录。

简单的选择排序

1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

2、例子：

（1）一个数组的初始状态：33,87,46,9

（2）最小值为9，与第一个进行交换（9,87,46,33）

（3）最小为33，与第二个进行交换（9,33,46,87）

（4）46就是最小值，无需交换，排序完成（9,33,46,87）

3、代码实现

package day04Array;

/**
 * 选择排序的实现
 * 
 * @author Administrator
 * @date 2014-09-11
 */
public class SortDemo {

	public static void main(String[] args){
		int[] arr= {33,87,9,46};
		System.out.print("数组排序前：");
		traversalArray(arr);
		System.out.print("数组排序后：");
		//selectSort(arr);//执行选择排序
		bubbleSort(arr);
		traversalArray(arr);
		
		//Arrays.sort(arr);java中已经定义好的一种排序方法，开发中，我们经常直接使用该方法来对数据进行排序
	}
	//优化排序中交换数据元素的部分代码
	public static void swap(int[] arr,int a,int b){
		int temp= arr[a];
		arr[a]= arr[b];
		arr[b]= temp;
	}
	//选择排序实现（操作就是原数组，不需要返回）
	//内循环结束一次，最值出现在头角标位置上
	public static void selectSort(int[] arr){
		for(int x=0;x<arr.length-1;x++){
			for(int y=x+1;y<arr.length;y++){
				if(arr[x]>arr[y]){//可以修改排序顺序
					/*
					int temp= arr[x];
					arr[x]= arr[y];
					arr[y]= temp;
					*/
					swap(arr,x,y);
				}
			}
		}
	}
	

	//遍历数组中的元素
	public static void traversalArray(int[] arr){
		System.out.print("[");
		for(int x=0;x<arr.length;x++){
			if(x!=arr.length-1)
				System.out.print(arr[x]+",");
			else
				System.out.println(arr[x]+"]");
		}
	}
}

4、分析

简单选择排序是不稳定的排序

时间复杂度：T(n)=O(n2)

-交换排序

冒泡排序

基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

代码实现：

package day04Array;


public class SortDemo {

	public static void main(String[] args){
		int[] arr= {2,4,9,1,5};
		System.out.print("数组排序前：");
		traversalArray(arr);
		System.out.print("数组排序后：");
		//selectSort(arr);//执行选择排序
		bubbleSort(arr);
		traversalArray(arr);
		
		//Arrays.sort(arr);java中已经定义好的一种排序方法，开发中，我们经常直接使用该方法来对数据进行排序
	}
	//优化排序中交换数据元素的部分代码
	public static void swap(int[] arr,int a,int b){
		int temp= arr[a];
		arr[a]= arr[b];
		arr[b]= temp;
	}
	
	//冒泡排序实现
	public static void bubbleSort(int[] arr){
		for(int x=0;x<arr.length-1;x++){
			for(int y=0;y<arr.length-x-1;y++){
				if(arr[y]>arr[y+1]){
					/*
					int temp= arr[y];
					arr[y]= arr[y+1];
					arr[y+1]= temp;
					*/
					swap(arr,y,y+1);
				}
			}
		}
	}

	//遍历数组中的元素
	public static void traversalArray(int[] arr){
		System.out.print("[");
		for(int x=0;x<arr.length;x++){
			if(x!=arr.length-1)
				System.out.print(arr[x]+",");
			else
				System.out.println(arr[x]+"]");
		}
	}
}

分析：

冒泡排序是一种稳定的排序方法　

若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)

若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)

起泡排序平均时间复杂度为O(n2)

基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

代码实现：

package day04Array;
/**
 * 折半查找特点：可以提高效率，但必须要保证该数组时有序的数组
 * 折半查找扩展练习：有一个有序的数组，想要将一个元素插入到该数组中，并且保证该
 * 					数组还是有序的（其实就是找出要插入的位置角标）
 */
public class SearchInArray {

	public static void main(String[] args) {
		//任意查找
		int[] arr= {2,8,11,5,9,4,35};
		int index= getIndex(arr,5);
		System.out.println("index= "+index);
		//折半查找
		int[] arr1= {1,4,6,11,55,120};
		int x= halfSearch_2(arr1, 11);
		System.out.println(x);
	}
	
	//折半查找实现方式2：
	public static int halfSearch_2(int[] arr,int key){
		int min= 0,max= arr.length-1,mid;
		while(min<=max){
			mid= (min+max)>>1;
			if(key>arr[mid])
				min= mid+1;
			else if(key<arr[mid])
				max= mid-1;
			else
				return mid;
		}
		return -1;//返回min可以解决扩展练习
	}
	//折半查找实现方式1：
	public static int halfSearch(int[] arr,int key){
		int max,min,mid;
		min= 0;
		max=arr.length-1;
		mid= (max+min)/2;
		while(arr[mid]!=key){
			if(key>arr[mid])
				min= mid+1;
			else if(key<arr[mid])
				max= mid-1;
			if(min>max)
				return -1;
			mid= (max+min)/2;
		}
		return mid;
		
	}
	
	//功能：获取key第一次出现在数组中的位置，如果返回是-1，则表示该key在数组中不存在
	public static int getIndex(int[] arr,int key){
		for(int x=0;x<arr.length;x++){
			if(arr[x]== key)
				return x;
		}
		return -1;
	}

}

分析：

快速排序是不稳定的排序。

快速排序的时间复杂度为O(nlogn)。

当n较大时使用快排比较好，当序列基本有序时用快排反而不好

最后

以上就是隐形猎豹为你收集整理的黑马程序员——数组、常见排序的全部内容，希望文章能够帮你解决黑马程序员——数组、常见排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。