一.数组
1.一维数组
(1).数组的定义
数据类型 数组名[]=new 数据类型[大小]
public class Demo1 {
public static void main(String[] args) {
//第一种定义方式
int arr[];
arr=new int[5];
//第二种定义方式
int arr2[]=new int[5];
//第三种定义方式
int[] arr3;
arr3=new int[5];
//第四种定义方式
int arr4[]={1,2,3,4};
}
}
(2).对象数组
假设一个养狗场有4只狗, 名字分别是花花, 白白, 黑黑, 红红, 体重分别为4.5Kg, 5.6Kg, 7.8Kg, 9.0Kg, 计算出平均体重, 并找出体重最大的狗的名字.
import java.io.*;
public class Demo2 {
public static void main(String[] args) {
try {
//输入流
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader bReader=new BufferedReader(isr); //定义一个对象数组,可以存放4只狗的对象数组
Dog dogs[]=new Dog[4];
//给对象赋值
for(int i=0;i<dogs.length;i++){
//这里要创建dog[i]对象
dogs[i]=new Dog();
System.out.println("请输入第"+(i+1)+"狗的名字:");
String dogName=bReader.readLine();
dogs[i].setName(dogName); System.out.println("请输入第"+(i+1)+"狗的体重:");
String dogWeight=bReader.readLine();
float dWeight=Float.parseFloat(dogWeight);
dogs[i].setWeight(dWeight);
} //总体重
float allWeight=0;
//平均体重
float averWeight=0;
for(int i=0;i<dogs.length;i++){
allWeight+=dogs[i].getWeight();
}
averWeight=allWeight/dogs.length;
System.out.println("平均体重为:"+averWeight); //体重最大的
float maxWeight=dogs[0].getWeight();
int maxWeightIndex=0;
for(int i=1;i<dogs.length;i++){
if(maxWeight<dogs[i].getWeight()){
maxWeight=dogs[i].getWeight();
maxWeightIndex=i;
}
}
System.out.println("体重最大的狗是:"+dogs[maxWeightIndex].getName()+
" 体重为:"+dogs[maxWeightIndex].getWeight());
} catch (Exception e) {
e.printStackTrace();
}
}
} class Dog {
private String name;
private float weight;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public float getWeight() {
return weight;
}
public void setWeight(float weight) {
this.weight = weight;
}
}
运行结果：
请输入第1狗的名字:
花花
请输入第1狗的体重:
4.5
请输入第2狗的名字:
白白
请输入第2狗的体重:
5.6
请输入第3狗的名字:
黑黑
请输入第3狗的体重:
7.8
请输入第4狗的名字:
红红
请输入第4狗的体重:
9.0
平均体重为:6.7250004
体重最大的狗是:红红 体重为:9.0
(3).数组小结
①数组可存放同一类型的数据;
②简单数据类型(int, float...)数组可直接赋值, 对象数组在定义后,赋值时需要再次为每个对象分配空间;
③数组大小必须事先指定;
④数组名可理解为指向数组首地址的引用;
⑤数组的下标是从0开始编号的.
2.多维数组
二维数组的定义
数据类型 数组名[][]=new 数据类型[大小][大小]
二.排序
这里主要介绍了七种常用的排序方法, 包括冒泡排序, 选择排序, 直接插入排序, 希尔排序, 堆排序, 归并排序和快速排序. 这里主要参考了《大话数据结构》和《MoreWindows白话经典算法之七大排序第2版(高清)》", 下载链接为http://download.csdn.net/detail/morewindows/4560056
1.冒泡排序
class BubbleSort {
/**
* 冒泡排序方法1,从小到大
* 如果经过一趟排序之后没有任何交换,说明已经排好序了,不需要再进行下去了
* @param arr 待排序数组
*/
public void bubbleSort1(int arr[]) {
//标记位
boolean Flag=true;
int k=arr.length;
while(Flag) {
Flag=false;
for(int j=1;j<k;j++) {
//如果前面的数大于后面的数,则交换这两个数
if(arr[j-1]>arr[j]) {
arr[j-1]^=arr[j];
arr[j]^=arr[j-1];
arr[j-1]^=arr[j];
Flag=true;
}
}
k--;
}
}
/**
* 冒泡排序方法2,从小到大
* 如果有100个数的数组,仅前面10个无序,后面90个都已经排好序了且大于前面10个数字
* 那么在第一趟遍历后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经
* 有序了,记录下这个位置,第二次只要从数组头部遍历到这个位置就可以了
* @param arr 待排序数组
*/
public void bubbleSort2(int arr[]) {
//标记位置的标记位
int Flag=arr.length;
int k;
while(Flag>0) {
k=Flag;
Flag=0;
for(int j=1;j<k;j++) {
if(arr[j-1]>arr[j]) {
arr[j-1]^=arr[j];
arr[j]^=arr[j-1];
arr[j-1]^=arr[j];
//更新记录交换位置的变量Flag
Flag=j;
}
}
}
}
}
2.选择排序
class SelectSort {
/**
* 选择排序,从小到大
* @param arr 待排序数组
*/
public void selectSort(int arr[]) {
int length=arr.length;
//最小值的下标索引
int minIndex;
for(int i=0;i<length;i++) {
minIndex=i;
for(int j=i+1;j<length;j++) {
if(arr[j]<arr[minIndex]) {
minIndex=j;
}
}
if(minIndex!=i) {
if(arr[minIndex]!=arr[i]) {
arr[minIndex]^=arr[i];
arr[i]^=arr[minIndex];
arr[minIndex]^=arr[i];
}
}
}
}
}
3.插入排序
class InsertSort {
/**
* 插入排序,从小到大
* 即每次arr[i]先和前面一个数据arr[i-1]比较,如果arr[i]>arr[i-1],说明arr[0...i]也是有序的,无须调整
* 否则就令j=i-1,temp=arr[i],然后一边将数据arr[j]向后移动一边向前搜索,当有数据arr[j]<arr[i]时停止
* 并将temp放到arr[j+1]处
* @param arr 待排序数组
*/
public void insertSort(int arr[]) {
int length=arr.length;
int temp=0,j=0;
for(int i=1;i<length;i++) {
//比前面的数小
if(arr[i]<arr[i-1]) {
temp=arr[i];
//向后移动
for(j=i-1;j>=0 && arr[j]>temp;j--) {
arr[j+1]=arr[j];
}
arr[j+1]=temp;
}
}
}
}
4.希尔排序
class ShellSort {
/**
* 希尔排序,从小到大
* 希尔排序的实质就是分组插入排序,又称缩小增量排序
* @param arr 待排序数组
*/
public void shellSort(int arr[]) {
//gap为步长
int i,j,gap;
int length=arr.length;
//步长
for(gap=length/2;gap>0;gap/=2) {
//分组
for(i=0;i<gap;i++) {
//每一组进行插入排序
for(j=i+gap;j<length;j+=gap) {
if(arr[j]<arr[j-gap]) {
int temp=arr[j];
int k=j-gap;
while(k>=0 && arr[k]>temp) {
arr[k+gap]=arr[k];
k-=gap;
}
arr[k+gap]=temp;
}
}
}
}
}
}
5.堆排序
class HeapSort {
/**
* 堆排序,从大到小
* @param arr 待排序数组
*/
public void heapSort(int arr[]) {
int length=arr.length;
//建立最小堆
for(int i=length/2-1;i>=0;i--) {
heapAdjust(arr,i,length);
}
//堆排序
//构建小顶堆,排序的结果是由大到小
for(int i=length-1;i>=1;i--) {
//将小顶堆的顶部arr[0]与arr[i]依次交换
if(arr[i]!=arr[0]) {
arr[i]^=arr[0];
arr[0]^=arr[i];
arr[i]^=arr[0];
}
//重新构建小顶堆
heapAdjust(arr,0,i);
}
}
/**
* 堆调整
* @param arr 待排序数组
* @param i 从i节点开始调整,从0开始计算,第i节点的子节点为2*i+1,2*i+2
* @param n 节点总数
*/
private void heapAdjust(int arr[],int i,int n) {
//定义变量
int j,temp;
temp=arr[i];
j=2*i+1;
while(j<n) {
//在左右节点中找最小的节点
if(j+1<n && arr[j+1]<arr[j]) {
j++;
}
//不需要调整
if(arr[j]>=temp) {
break;
}
//把较小的节点往上移动,替换它的父节点
arr[i]=arr[j];
i=j;
j=2*i+1;
}
arr[i]=temp;
}
}
6.归并排序
class MergeSort {
/**
* 归并排序,从小到大
* @param arr 待排序数组
*/
public void mergeSort(int arr[]) {
int length=arr.length;
//创建一个和待排序数组同样大小临时数组
int temp[]=new int[length];
//归并排序
merge_sort(arr, 0, length-1, temp);
}
/**
* 归并排序
* @param arr 待排序数组
* @param first 起始下标
* @param last 终点下标
* @param temp 临时数组
*/
private void merge_sort(int arr[],int first,int last,int temp[]) {
if(first<last) {
int mid=(first+last)/2;
//左边有序
merge_sort(arr, 0, mid, temp);
//右边有序
merge_sort(arr, mid+1, last, temp);
//再将两个有序数组合并
merge_array(arr, first, mid, last, temp);
}
}
/**
* 合并两个有序数组
* @param arr 待排序数组
* @param first 起始下标
* @param mid 中间下标
* @param last 终点下标
* @param temp 临时数组
*/
private void merge_array(int arr[],int first,int mid,int last,int temp[]) {
int i=first,j=mid+1;
int m=mid,n=last;
int k=0;
while(i<=m && j<=n) {
if(arr[i]<arr[j]) {
temp[k++]=arr[i++];
}else {
temp[k++]=arr[j++];
}
}
while(i<=m) {
temp[k++]=arr[i++];
}
while(j<=n) {
temp[k++]=arr[j++];
}
for(i=0;i<k;i++) {
arr[first+i]=temp[i];
}
}
}
7.快速排序
import java.util.*;
public class Demo9 {
public static void main(String[] args) {
//关于Java中生成特定区间里的随机数见http://blog.sina.com.cn/s/blog_59aebaa10100ct47.html
//生成8000000个[1,9000000]之间的随机数
Random random=new Random();
int length=8000000;
int arr[]=new int[length];
for(int i=0;i<length;i++) {
arr[i]=random.nextInt(9000000)+1;
} //快速排序
QuickSort qSort=new QuickSort();
//关于统计程序运行时间见http://blog.csdn.net/uyu2yiyi/article/details/6267990
//排序开始时间
long startTime=System.currentTimeMillis();
qSort.quickSort(arr);
//排序结束时间
long endTime=System.currentTimeMillis();
System.out.println("快速排序时间为:"+(endTime-startTime)+"毫秒");
}
} class QuickSort {
/**
* 快速排序,从小到大
* @param arr 待排序数组
*/
public void quickSort(int arr[]) {
quick_sort(arr, 0, arr.length-1);
} /**
* 快速排序
* @param arr 待排序数组
* @param first 起点下标
* @param last 终点下标
*/
private void quick_sort(int arr[],int first,int last) {
//枢轴
int pivot;
if(first<last) {
//将子表一分为二
pivot=partition(arr, first, last);
//对低子表进行排序
quick_sort(arr, first, pivot-1);
//对高子表进行排序
quick_sort(arr, pivot+1, last);
}
} /**
* 找到划分子表的位置
* @param arr 待排序数组
* @param first 起点下标
* @param last 终点下标
* @return 划分子表的位置
*/
private int partition(int arr[],int first,int last) {
int pivotkey=arr[first];
while(first<last) {
while(first<last && arr[last]>=pivotkey) {
last--;
}
arr[first]=arr[last];
while(first<last && arr[first]<=pivotkey) {
first++;
}
arr[last]=arr[first];
}
arr[first]=pivotkey;
return first;
} }
三.查找
查找有很多方法, 如二分查找, 插值查找, 斐波那契查找, 二叉树查找, 哈希表查找等, 这里仅给出二分查找.
public class Demo10 {
public static void main(String[] args) {
//待查找数组必须是从小到大有序的
int arr[]={1,4,9,20,47,69};
int pos=-1;
int key=47;
BinarySearch bSearch=new BinarySearch();
if( (pos=bSearch.binarySearch(arr, key))!=-1 ) {
System.out.println("找到了该关键字,其在数组中的下标为: "+pos);
}else {
System.out.println("没有找到该关键字");
}
}
}
class BinarySearch {
/**
* 二分查找,其前提是查找的数组是从小到大有序的
* @param arr 待查找数组
* @param key 待插值关键字
* @return 如果找到,则返回该关键字在数组中的位;没找到则返回-1
*/
public int binarySearch(int arr[],int key) {
int low,high,mid;
low=0;
high=arr.length-1;
while(low<=high) {
mid=low+(high-low)/2;
if(key>arr[mid]) {
low=mid+1;
}else if(key<arr[mid]) {
high=mid-1;
}else {
//找到,返回下标
return mid;
}
}
//没找到
return -1;
}
}