排序算法.docx
《排序算法.docx》由会员分享，可在线阅读，更多相关《排序算法.docx（24页珍藏版）》请在冰点文库上搜索。
排序算法
数据结构算法面试总结：
全部机测通过。
。
。
。
。
。
。
//插入排序：
适用于少量的输入，O（n^2）=i；
publicint[]insertSort（int[]array）{
for（inti=0;i inttemp=array[i]; intj=i;
while（j>0&&array[j-1]> temp ）{//将当前元素插入已排好序的数组，判断当前元素和其他元素大小
array[j]=array[j-1];
j--; }
array[j]=temp; }
returnarray; }
//希尔排序：
插入排序的升级版，不稳定，O（n^2）
publicint[]shellSort（int[]array）{
for（intgap=array.length/2;gap>0;gap=（int）（gap==2?
1:
（gap/2.2）））{
for（inti=gap;i inttemp=array[i];
intj=i;
while（j>=gap&&array[j-gap]>array[j]）{
array[j]=array[j-gap];
j-=gap;
array[j]=temp;
}
//for（;j>=gap&&array[j-gap]>array[j];j-=gap）{
//array[j]=array[j-gap];
//array[j-gap]=temp;
//}
}
}
returnarray;
}
//选择排序
publicstaticvoidselectSort（int[]list）{
for（inti=0;i intposi=i;//位置
inttemp=list[i];//值
//找最小的元素
for（intj=i+1;j if（list[j] temp=list[j];//循环整个未排序的数组，找出其中最小的元素付给temp
posi=j; } }
//交换位置
list[posi]=list[i];//交换temp和第i个位置的数值
list[i]=temp; } }
//递归格式的归并排序
publicListmergeSort（Listlist）{
if（list.size（）>1）{
ListlowList=newArrayList（）;
ListsameList=newArrayList（）;
ListupList=newArrayList（）;
intmiddle=list.get（list.size（）/2）;
for（Integertemp:
list）{
if（temp lowList.add（temp）;
}elseif（temp>middle）{
upList.add（temp）;
}else{
sameList.add（temp）;
}
}
mergeSort（lowList）;
mergeSort（upList）;
list.clear（）;
list.addAll（lowList）;
list.addAll（sameList）;
list.addAll（upList）;
}
returnlist;
}
/**
* 冒泡排序
*时间复杂度：
n^2;
*/
publicclassBubbleSort{
publicstaticvoidmain（String[]args）{
BubbleSortbs=newBubbleSort（）;
int[]a={1,6,5,4,3,2,1};
int[]c={0};
int[]b=bs.bubbleSort1（c）;
for（inti=0;i System.out.print（a[i]+","）; } }
publicint[]bubbleSort（int[]a）{
//从小到大
inttemp=0;
for（inti=0;i for（intj=0;j if（a[j]>a[j+1]）{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp; } } }
returna; }
publicint[]bubbleSort1（int[]a）{ //从大到小
inttemp=0;
for（inti=0;i for（intj=0;j if（a[j] temp=a[j+1];
a[j+1]=a[j];
a[j]=temp; } } }
returna; }}
/**
* 快速排序
*时间复杂度：
nlog（n）;
*/
packagecom.lyz.test0829;
publicclassQuickSort{
publicstaticvoidmain（String[]args）{
int[]a={1,3,2,4,9,6,7,7,8};
QuickSortqs=newQuickSort（）;
qs.quick（a）;
for（inti=0;i System.out.print（a[i]+""）; } }
publicint getMiddle（int[]list,intlow,inthigh）{
inttemp=list[low];
while（low while（low=temp）{
high--;//中轴的元素和最高位进行比较，若最高位大，则high指针左移一位 }
list[low]=list[high];//若最高位小则交换位置
while（low low++; }
list[high]=list[low]; }
list[low]=temp;//记录中轴的值
returnlow;//返回中轴位置 }
publicvoid_quickSort（int[]list,intlow,inthigh）{
if（low intmiddle=getMiddle（list,low,high）;
_quickSort（list,low,middle-1）;//递归
_quickSort（list,middle+1,high）; } }
publicvoidquick（int[]a2）{
if（a2.length>0）{
_quickSort（a2,0,a2.length-1）; } }}
/**
* 链表
*/
//定义节点
privateclassNode{
Nodeprevious;
Objectobject;
Nodenext;
}
packagecom.lyz.test0901;
publicclassMyLinkeList{
privateNodefirst;//首节点
privateNodelast;//末尾节点
privateintsize;//链表大小
publicstaticvoidmain（String[]args）{
MyLinkeListlist=newMyLinkeList（）;
list.add（"aaaa"）;
list.add（"bbbb"）;
list.add（"cccc"）;
list.add（"dddd"）;
System.out.println（"size:
"+list.size）;
System.out.println（"get:
"+list.get
（1））;
list.remove
（1）;
System.out.println（"remove:
"+list.get
（1））;
list.add（1,"bbbb"）;
System.out.println（"save:
"+list.get
（1））; }
//增加节点
publicvoidadd（Objectobj）{
//考虑首节点是否为空
Nodenode=newNode（）;
if（first==null）{
//新建一个节点
node.next=null;
node.object=obj;
node.previous=null;
//将首尾节点都指向该节点
first=node;
last=node;
}else{
//直接在last节点后面增加新节点
node.object=obj;
node.previous=last;
node.next=null;
last.next=node;
//再新建一个末尾节点
last=node; }
size++;//增加大小 }
//得到节点
publicObjectget（intindex）{
isOutOfIndex（index）;
returngetNode（index）.object;}
//插入节点
publicvoidadd（intindex,Objectobj）{
Nodetemp=getNode（index）;
NodenewNode=newNode（）;
if（temp!
=null）{
NodepreNode=temp.previous;
newNode.next=temp;
newNode.object=obj;
newNode.previous=preNode;
preNode.next=newNode; } }
//删除指定位置的节点
publicvoidremove（intindex）{
Nodetemp=getNode（index）;
if（temp!
=null）{
NodepreNode=temp.previous;
NodenextNode=temp.next;
preNode.next=nextNode;
nextNode.previous=preNode;
size--; } }
publicintsize（）{
returnsize; }
//得到第i个节点
publicNodegetNode（intindex）{
if（first==null）{
returnnull;
}else{
Nodetemp=first;
for（inti=0;i temp=temp.next;//循环遍历链表到第index个node
}
returntemp;
}
}
//判断下表是否越界
publicvoidisOutOfIndex（intindex）{
booleanflag=true;
if（index<0||index>=size）{
try{
thrownewException（）;
}catch（Exceptione）{
e.printStackTrace（）;
}
}
}
}
栈：
数组实现
packagecom.lyz.test0829;
publicclassMyStack{
privateObject[]obj=newObject[10];
privateintsize=0;
privatevoidresize（）{
Object[]temp=newObject[obj.length*3/2+1];
for（inti=0;i temp[i]=obj[i];
obj[i]=null;
}
obj=temp;
}
publicbooleanpush（Tdata）{
if（size>=obj.length）{
resize（）;
}else{
obj[size++]=data;
}
returntrue;
}
publicTpop（）{
if（size==0）{
returnnull;
}else{
return（T）obj[size--];
}
}
publicbooleanisEmpty（）{
returnsize==0;
}
}
packagecom.lyz.test0829;
链表实现
publicclassNodeStack{
privateNodetop;
privateintsize;
publicNodeStack（）{
top=null;
size=0;
}
publicbooleanpush（Tt）{
Nodenode=newNode（）;
node.data=t;
node.pre=top;
top=node;
size++;
returntrue;
}
publicTpop（）{
if（top!
=null）{
Nodenode=top;
top=node.pre;
size--;
return（T）node;
}
returnnull;
}
privatefinalclassNode{
privateNodepre;
privateTdata;
}
}
packagecom.lyz.test0829;
importjava.util.Stack;
//用栈将十进制数变为n进制
publicclassConversion{
publicstaticvoidmain（String[]args）{
System.out.println（conversion（8,2））;
}
publicstaticStringconversion（intnum,intbase）{
Stackstack=newStack（）;
Integerresult=num;
while（true）{
stack.push（result%base）;
result=result/base;
if（result==0）{
break;
}
}
StringBuffersb=newStringBuffer（）;
while（（stack.pop（））!
=null）{
sb.append（result）;
}
returnsb.toString（）;
} }
map
如果equals为true则hashcode码相等；
map里面的键的判断依赖于equals方法；
index>>1:
index除以2；
元素的查找：
list里面查找元素，看index的值大小而判断从前查找还是从后面开始查找；
classEntity{
Objectkey;
Objectvalue;
publicEntity（Objectkey,Objectvalue）{
super（）;
this.key=key;
this.value=value;
}
}
publicclassTestMap{
List[]arr=newArrayList[990];//声明一个键值对对象:
数组加链表
intsize;//大小
publicvoidput（Objectkey,Objectvalue）{
//数组加链表实现：
在数组里面放链表的头部地址信息，
//每个链表存放哈希码一样的元素
Entitye=newEntity（key,value）;
inta=key.hashCode（）%73;
a=a<0?
-a:
a;//判断是否为负数
if（arr[a]==null）{
Listlist=newArrayList（）;
arr[a]=list;
list.add（e）;
}else{
//判断键值是否重复
Listlist=arr[a];//得到的arr[a]为一个链表，直接给链表添加元素
for（inti=0;i Entitye2=（Entity）list.get（i）;
if（e2.key.equals（key））{
e2.value=value;
}
}
arr[a].add（e）;
}
size++;
}
finalEntrygetEntry（Objectkey）{
inthash=（key==null）?
0:
hash（key）;
for（Entrye= table[indexFor（hash,table.length）];
e!
=null;
e=e.next）{
Objectk;
if（e.hash==hash&&
（（k=e.key）==key||（key!
=null&&key.equals（k））））
returne;
}
returnnull;
}
set:
无序不重复底层通过Map实现（值放在map的key中）
publicclassMyHashSet{
HashMapmap;
privatestaticfinalObjectPRESERNT=newObject（）;
publicMyHashSet（）{
map=newHashMap（）;
}
publicvoidadd（Objecto）{
map.put（o,PRESERNT）; } }
publicTreeSet（）{
this（newTreeMap（））;
}
迭代器：
Iterator
泛型：
T（type）,V（value）,E（element）——
获取值：
1、强制类型转换；避免classCastException：
instanseof
JDK1.7之后：
intx=（int）object;包装了由object到Integer然后到int的过程；
优点：
1、安全：
进行类型检查，不使用时只能强制装换造成数据丢失；
2、方便：
进行类型装换，在获取值得时候自动拆箱进行类型转换；
注意：
1、使用时指定类型，且只能为指定类型
2、不能使用静态属性，静态方法，
3、接口中泛型只能使用在方法中，不能使用在全局常亮中，接口默认的为finalde;
4、泛型方法：
修饰符后面，返回类型前面publicstaticvoidtest（Tt）
staticFiledir=newFile（"d:
/fileTest"）;
staticFileOutputStreamfout;;
staticObjectOutputStreamobjOut;
staticFileInputStreamfin;
staticObjectInputStreamobjIn;
publicstaticvoidmain（String[]args）throwsIOException{
FileOptionfo=newFileO
升级会员 