常用Java排序算法详解
一、选择排序(SelectSort)
基本原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。
publicclassSelectSort{
publicstaticvoidselectSort(int[]array){
inti;
intj;
inttemp;
intflag;
for(i=0;i<array.length;i++){
temp=array[i];
flag=i;
for(j=i+1;j<array.length;j++){
if(array[j]<temp){
temp=array[j];
flag=j;
}
}
if(flag!=i){
array[flag]=array[i];
array[i]=temp;
}
}
}
publicstaticvoidmain(String[]args){
int[]a={5,1,9,6,7,2,8,4,3};
selectSort(a);
for(inti=0;i<a.length;i++){
System.out.print(a[i]+"");
}
}
}
二、插入排序(InsertSort)
基本原理：对于给定的一组数据，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
publicclassInsertSort{
publicstaticvoidinsertSort(int[]a){
if(a!=null){
for(inti=1;i<a.length;i++){
inttemp=a[i];
intj=i;
if(a[j-1]>temp){
while(j>=1&&a[j-1]>temp){
a[j]=a[j-1];
j--;
}
}
a[j]=temp;
}
}
}
publicstaticvoidmain(String[]args){
int[]a={5,1,7,2,8,4,3,9,6};
//int[]a=null;
insertSort(a);
for(inti=0;i<a.length;i++){
System.out.print(a[i]+"");
}
}
}
三、冒泡排序(BubbleSort)
基本原理：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前(n-1)个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。
publicclassBubbleSort{
publicstaticvoidbubbleSort(intarray[]){
inttemp=0;
intn=array.length;
for(inti=n-1;i>=0;i--){
for(intj=0;j<i;j++){
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
publicstaticvoidmain(String[]args){
inta[]={45,1,21,17,69,99,32};
bubbleSort(a);
for(inti=0;i<a.length;i++){
System.out.print(a[i]+"");
}
}
}
四、归并排序(MergeSort)
基本原理：利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。对于给定的一组记录(假设共有n个记录)，首先将每两个相邻的长度为1的子序列进行归并，得到n/2(向上取整)个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。
publicclassMergeSort{
publicstaticvoidmerge(intarray[],intp,intq,intr){
inti,j,k,n1,n2;
n1=q-p+1;
n2=r-q;
int[]L=newint[n1];
int[]R=newint[n2];
for(i=0,k=p;i<n1;i++,k++)
L[i]=array[k];
for(i=0,k=q+1;i<n2;i++,k++)
R[i]=array[k];
for(k=p,i=0,j=0;i<n1&&j<n2;k++){
if(L[i]>R[j]){
array[k]=L[i];
i++;
}else{
array[k]=R[j];
j++;
}
}
if(i<n1){
for(j=i;j<n1;j++,k++)
array[k]=L[j];
}
if(j<n2){
for(i=j;i<n2;i++,k++){
array[k]=R[i];
}
}
}
publicstaticvoidmergeSort(intarray[],intp,intr){
if(p<r){
intq=(p+r)/2;
mergeSort(array,p,q);
mergeSort(array,q+1,r);
merge(array,p,q,r);
}
}
publicstaticvoidmain(String[]args){
inta[]={5,4,9,8,7,6,0,1,3,2};
mergeSort(a,0,a.length-1);
for(intj=0;j<a.length;j++){
System.out.print(a[j]+"");
}
}
}
五、快速排序(QuickSort)
基本原理：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
publicclassQuickSort{
publicstaticvoidsort(intarray[],intlow,inthigh){
inti,j;
intindex;
if(low>=high)
return;
i=low;
j=high;
index=array[i];
while(i<j){
while(i<j&&index<=array[j])
j--;
if(i<j)
array[i++]=array[j];
while(i<j&&index>array[i])
i++;
if(i<j)
array[j--]=array[i];
}
array[i]=index;
sort(array,low,i-1);
sort(array,i+1,high);
}
publicstaticvoidquickSort(intarray[]){
sort(array,0,array.length-1);
}
publicstaticvoidmain(String[]args){
inta[]={5,8,4,6,7,1,3,9,2};
quickSort(a);
for(inti=0;i<a.length;i++){
System.out.print(a[i]+"");
}
}
}
六、希尔排序(ShellSort)
基本原理：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对减少，然后对各个子序列分别进行直接插入排序，待整个待排序序列"基本有序后"，最后再对所有元素进行一次直接插入排序。
publicclassShellSort{
publicstaticvoidshellSort(int[]a){
intlen=a.length;
inti,j;
inth;
inttemp;
for(h=len/2;h>0;h=h/2){
for(i=h;i<len;i++){
temp=a[i];
for(j=i-h;j>=0;j-=h){
if(temp<a[j]){
a[j+h]=a[j];
}else
break;
}
a[j+h]=temp;
}
}
}
publicstaticvoidmain(String[]args){
inta[]={5,4,9,8,7,6,0,1,3,2};
shellSort(a);
for(intj=0;j<a.length;j++){
System.out.print(a[j]+"");
}
}
}
七、最小堆排序(MinHeapSort)
基本原理：对于给定的n个记录，初始时把这些记录看作一颗顺序存储的二叉树，然后将其调整为一个小顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最小记录；接着讲前(n-1)个元素重新调整为一个小顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最大记录，此时可得到一个有序序列。
publicclassMinHeapSort{
publicstaticvoidadjustMinHeap(int[]a,intpos,intlen){
inttemp;
intchild;
for(temp=a[pos];2*pos+1<=len;pos=child){
child=2*pos+1;
if(child<len&&a[child]>a[child+1])
child++;
if(a[child]<temp)
a[pos]=a[child];
else
break;
}
a[pos]=temp;
}
publicstaticvoidmyMinHeapSort(int[]array){
inti;
intlen=array.length;
for(i=len/2-1;i>=0;i--){
adjustMinHeap(array,i,len-1);
}
for(i=len-1;i>=0;i--){
inttmp=array[0];
array[0]=array[i];
array[i]=tmp;
adjustMinHeap(array,0,i-1);
}
}
publicstaticvoidmain(String[]args){
int[]a={5,4,9,8,7,6,0,1,3,2};
myMinHeapSort(a);
for(inti=0;i<a.length;i++){
System.out.print(a[i]+"");
}
}
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！