注:以下代码摘抄自《Java 编程手记-从实践中学习java》一书,摘抄目的用于学习和共享。
1 冒泡排序
//冒泡排序:遍历整个数组,在遍历中依次对相邻元素进行比较,如果两者次序不对,则交换它们的位置本例是从大到小排序),其结果是元素较大值犹如“水泡”一样浮到数组前面。然后再次遍历数组,重复上述过程直至把所有元素移到适合的位置。
public
class BubbleSort{
public static void main(String[]
args){
int
score[]={900,878,891,904,865,912,868,870,898,903};
//打印数组元素
System.out.print("未排序结果:");
for(int
i=0;i<score.length;i++){
System.out.print(score[i]+" ");
}
System.out.println();
//冒泡排序算法:从大到小排序
for(int i=0;i<score.length;i++){
for(int
j=0;j<score.length-i-1;j++){
if(score[j]<score[j+1]){
int temp=score[j];
score[j]=score[j+1];
score[j+1]=temp;
}
}
//每遍历一次数组的结果
System.out.print("第"+(i+1)+"次冒泡:");
for(int
k=0;k<score.length;k++){
System.out.print(score[k]+" ");
}
System.out.println();
}
//最终排序的结果
System.out.print("最终排序结果:");
for(int i=0;i<score.length;i++){
System.out.print(score[i]+"
");
}
System.out.println();
}
}
2 插入排序
//插入排序:将要排序的数组分为有序部分和无序部分,每次从无序部分取出一个元素插入到有序部分的适合位置。通常在排序开始前,有序部分为数组的第一个元素。
public
class InseretionSort{
public static void main(String[]
args){
int
score[]={900,878,891,904,865,912,868,870,898,903};
//打印数组元素
System.out.print("未排序结果:");
for(int
i=0;i<score.length;i++){
System.out.print(score[i]+" ");
}
System.out.println();
//插入排序算法:从大到小排序
for(int i=1;i<score.length;i++){
for(int
j=i;j>0;j--){
if(score[j]>score[j-1]){
int temp=score[j];
score[j]=score[j-1];
score[j-1]=temp;
}
}
//每遍历一次数组的结果
System.out.print("第"+i+"次插入:");
for(int
k=0;k<score.length;k++){
System.out.print(score[k]+" ");
}
System.out.println();
}
//最终排序的结果
System.out.print("最终排序结果:");
for(int i=0;i<score.length;i++){
System.out.print(score[i]+"
");
}
System.out.println();
}
}
3
选择排序
//选择排序:每一趟都从待排序的数组元素中选择最大(或最小)的一个元素,并放在已排序好的数列后面。一直重复上述动作,直至把待排序的数组元素排完。
public
class SelectSort{
public static void main(String[]
args){
int
score[]={900,878,891,904,865,912,868,870,898,903};
//打印数组元素
System.out.print("未排序结果:");
for(int
i=0;i<score.length;i++){
System.out.print(score[i]+" ");
}
System.out.println();
//选择排序:从大到小排序
for(int
i=0;i<score.length;i++){
int lowIndex=i;
for(int
j=i+1;j<score.length;j++){
if(score[j]>score[lowIndex]){//找出最大的元素的下标,并记录
lowIndex=j;
}
}
//每一次遍历后,将最大的元素找出并和相应元素交换位置。
int
temp=score[i];
score[i]=score[lowIndex];
score[lowIndex]=temp;
//每遍历一次数组的结果
System.out.print("第"+(i+1)+"次选择:");
for(int
k=0;k<score.length;k++){
System.out.print(score[k]+" ");
}
System.out.println();
}
//最终排序的结果
System.out.print("最终排序结果:");
for(int i=0;i<score.length;i++){
System.out.print(score[i]+"
");
}
System.out.println();
}
}
4 希尔排序
//希尔排序:是直接插入排序的改进,该方法又称缩小增量排序。思想是将整个无序列分割成若干个小的子序列后,再分别进行插入排序,然后依次缩减增量再次排序,待到增量足够小时,对全体元素直接进行插入排序。
public
class ShellSort{
public static void main(String[]
args){
int
score[]={900,878,891,904,865,912,868,870,898,903};
//打印数组元素
System.out.print("未排序结果:");
for(int
i=0;i<score.length;i++){
System.out.print(score[i]+" ");
}
System.out.println();
//希尔排序:从大到小排序
for(int
incre=score.length/2;incre>0;incre=incre/2){//刚开始增量为5,后来为2,最后为1.
for(int
i=incre;i<score.length;i++){
int
temp=score[i];
int j=0;
for(j=i;j>=incre;j=j-incre){
if(temp>score[j-incre]){//刚开始增量为5时,score[5]和score[0]比较,若score[5]>score[0],则因temp保存score[5]的值,把score[0]赋值给score[5],相当于交换这两个数组元素的值,最终使score[0]保持较大的值。然后score[6]和score[1]比较,依次这样。
score[j]=score[j-incre];
}else{
break;
}
}
score[j]=temp;
}
}
//最终排序的结果
System.out.print("最终排序结果:");
for(int i=0;i<score.length;i++){
System.out.print(score[i]+"
");
}
System.out.println();
}
}
5 快速排序
//快速排序:当今公认的最好的排序算法之一,它是对冒泡排序的一种改进。思想是将要排序的数组氛围独立的两部分,气质一部分的所有数组元素值比另一部分的所有元素值都要小,而每一小部分数组的排序有可以继续分解为更小的两部分,这样递归分解下去,直到数组长度的大小最大为2.
public
class QuickSort{
public static void main(String[] args){
int array[]={2,44,23,5,34,13,29,6,24,26,18,10,25,12,17};
array=quickSort(array,0,array.length-1);
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
System.out.println();
}
//快速排序算法
public static
int[] quickSort(int[] arr,int lowIndex,int highIndex){
if(lowIndex < highIndex){
int s = arr[lowIndex];
int i = lowIndex;
int j = highIndex+1;
while(true){
while(i+1<arr.length&&arr[++i]<s) ;
//向右寻找大于S的数组元素的索引
while(j-1>-1&&arr[--j]>s);
//向左寻找小于S的数组元素的索引
if(i>=j){
break;
}else{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[lowIndex]= arr[j];
arr[j] = s;
quickSort(arr,lowIndex,j-1);
quickSort(arr,j+1,highIndex);
}
return arr;
}
}