java排序算法

1.定义
通过比较来确定输入序列<a₁,a₂,..,a_n>的元素间相对次序的排序算法称为比较排序算法。


2.算法解释

(1) 选择排序:
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
(2): 冒泡排序
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我 们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序 不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。 在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的 处理，它们已正确地排好序
(3) 插入排序
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止
(4) 快速排序

快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：

• 分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
• 递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
• 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

publicclassSort...{

/**//*
*交换算法
*/
publicstaticvoidswap(inta[],inti,intj)...{
inttmp=a[i];
a[i]=a[j];
a[j]=tmp;
}

//选择排序法
publicvoidsortSelection(int[]vec)...{
longbegin=System.currentTimeMillis();
//k次循环,增加运算时间.
for(intk=0;k<1000000;k++)...{
for(inti=0;i<vec.length;i++)...{
for(intj=i;j<vec.length;j++)...{
if(vec[j]<vec[i])...{
swap(vec,i,j);
}
}
}
}
longend=System.currentTimeMillis();
System.out.println("选择法用时为:"+(end-begin));
for(inti=0;i<vec.length;i++)...{
System.out.println(vec[i]);
}
}

//冒泡排序法
publicvoidsortBubble(int[]vec)...{
longbegin=System.currentTimeMillis();
for(intk=0;k<1000000;k++)...{
for(inti=0;i<vec.length;i++)...{
for(intj=i;j<vec.length-1;j++)...{
if(vec[j+1]<vec[j])...{
swap(vec,j+1,j);
}
}
}
}
longend=System.currentTimeMillis();
System.out.println("冒泡法用时为:"+(end-begin));
for(inti=0;i<vec.length;i++)...{
System.out.println(vec[i]);
}
}


//插入排序法
publicvoidsortInsertion(int[]vec)...{
longbegin=System.currentTimeMillis();
for(intk=0;k<1000000;k++)...{
for(inti=1;i<vec.length;i++)...{
intj=i;
while(vec[j-1]>vec[j])...{
vec[j]=vec[j-1];
j--;
if(j<=0)...{
break;
}
}
vec[j]=vec[i];
}
}
longend=System.currentTimeMillis();
System.out.println("插入法用时为:"+(end-begin));
for(inti=0;i<vec.length;i++)...{
System.out.println(vec[i]);
}
}

publicintpartition(inta[],intlow,inthigh)...{
intpivot,p_pos,i;
p_pos=low;
pivot=a[p_pos];
for(i=low+1;i<=high;i++)...{
if(a[i]<pivot)...{
p_pos++;
swap(a,p_pos,i);
}
}
swap(a,low,p_pos);
returnp_pos;
}

publicvoidquicksort(inta[],intlow,inthigh)...{
intpivot;
if(low<high)...{
pivot=partition(a,low,high);
quicksort(a,low,pivot-1);
quicksort(a,pivot+1,high);
}
}
//快速排序法
publicvoidsortQuick(int[]vec)...{
longbegin=System.currentTimeMillis();
for(intk=0;k<1000000;k++)...{
quicksort(vec,0,5);
}
longend=System.currentTimeMillis();
System.out.println("快速法用时为:"+(end-begin));
for(inti=0;i<vec.length;i++)...{
System.out.println(vec[i]);
}
}
/***//**
*@paramargs
*/
publicstaticvoidmain(String[]args)...{
//TODOAuto-generatedmethodstub
int[]vec=newint[]...{37,47,23,-5,19,56};
Sortsort=newSort();
sort.sortSelection(vec);
sort.sortBubble(vec);
sort.sortInsertion(vec);
sort.sortQuick(vec);

}

}

<iframe width="490" scrolling="no" height="150" frameborder="0" align="middle" style="width: 490px; height: 150px;" src="http://www.blogbao.com/script.aspx?userid=45735&amp;AdType=0&amp;AdstyleID=46090&amp;Direction=1" marginheight="0" marginwidth="0"></iframe>