常见Java排序算法

1.冒泡排序 (相邻元素相互比较，如有n个元素，需要n-1次比较)

public class BubbleSort{

public static void main (String[ ] args){

int array[ ] = new int[5];

array[0] =1;

array[1] = 0;

array[2] = 2;

array[3] = 4;

array[4] = 3;

for(int i =0;i<array.length ;i++){

for( int j =i+1;j<array.length;j++){

if(array[i]>array[j]){ //如果不需要升序排列，可以这样写array [i]< array [j]

int temp = array[j];

array[j] = array[i];

array [i] = temp;

}

for ( int t ; array){

system.out.println( ‘t =' +t);

}

}

}

}

2.选择排序（基本思路： 从所有元素中选择一个最小元素 a[i]放在 a[0] （即让最小元素 a[i] 与 a[0]
交换） ， 作为第一轮； 第二轮是从 a[1]开始到最后的各个元素中选择一个最小元素， 放在 a[1]
中；……依次类推。n 个数要进行（n－1）轮。比较的次数与冒泡法一样多，但是在每一轮
中只进行一次交换，比冒泡法的交换次数少，相对于冒泡法效率高。）

public class SelectionSort{

public static void main (String[] args){
int array[] = new int[5];
array[0] = 4;
array[1] = 5;
array[2] = 1;
array[3] = 3;
array[4] = 2;
int temp ;
for (int i = 0;i<array.length ;i++){
int lowIndex =i;
for(int j = i+1;j<array.length;j++){

if (array[j]<array[lowIndex]){
lowIndex = j;
}
}
temp = array[i];
array[i] = array[lowIndex];
array[lowIndex] = temp;

}
for(int i :array){
System.out.println("t="+i);
}

}


}

3：插入法排序

基本思路： 每拿到一个元素， 都要将这个元素与所有它之前的元素遍历比较一遍， 让符
合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。
举个例子来说， 就用前面的数组， 我们要对一个有 5 个元素的数组进行升序排列， 假设
第一个元素的值被假定为已排好序了，那么我们就将第 2 个元素与数组中的部分进行比较，
如果第 2 个元素的值较小，则将它插入到第 1 个元素的前面，现在就有两个元素排好序了，
我们再将没有排序的元素与排好序的元素列表进行比较， 同样，如果小于第一个元素，就将
它插入到第一个元素前面， 但是，如果大于第一个元素的话， 我们就将它再与第 2 个元素的
值进行比较， 小于的话就排在第 2 个元素前面，大于的话，就排在第 2 个元素的后面。 以此
类推，直到最后一个元素排好序。

public classInsert {
public static void main(String[] args) {
// 需要排序的数组，目前是按照升序排列的
int a[] = new int[5];
a[0] = 3;
a[1] = 4;
a[2] = 1;
a[3] = 5;
a[4] = 2;
// 插入法排序
int temp;
for(int i = 1; i < a.length; i++) {// i=1开始，因为第一个元素认为
//是已经排好序了的
for(int j = i; (j > 0) && (a[j] < a[j - 1]); j--) {
//交换
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
// 检测一下排序的结果
for(int i : a) {
System.out.println("i="+ i);

}
}
}

4：希尔(Shell)法排序

public class Test {
public static void main(String[] args) {
// 需要排序的数组，目前是按照升序排列的
int a[] = new int[5];
a[0] = 3;
a[1] = 4;
a[2] = 1;
a[3] = 5;
a[4] = 2;
// shell法排序
int j = 0;
int temp = 0;
//分组
for(int increment = a.length / 2; increment > 0; increment /= 2)
{
//每个组内排序
for(int i = increment; i < a.length; i++) {
temp = a[i];
for(j = i; j >= increment; j -= increment) {
if(temp < a[j - increment]){
a[j] = a[j - increment];
}else{
break;
}
}
a[j] = temp;
}
}
// 检测一下排序的结果
for(int i2 : a) {
System.out.println("i="+ i2);
}
}
}

5：数组排序

事实上， 数组的排序不用那么麻烦， 上面只是想让大家对一些基本的排序算法有了解
而已。在 java.util.Arrays 类中有一个静态方法 sort，可以用这个类的 sort 方法来对数组进行
排序。
示例如下：
public classTest {
public static voidmain(String[] args) {
// 需要排序的数组，目前是按照升序排列的
inta[] = new int[5];
a[0] = 3;
a[1] = 4;
a[2] = 1;
a[3] = 5;
a[4] = 2;
//数组排序
java.util.Arrays.sort(a);
// 检测一下排序的结果
for(inti2 : a) {
System.out.println("i="+ i2);

}
}
}
注意：现在的 sort 方法都是升序的，要想实现降序的，还需要 Comparator 的知识，这
个在后面会学到。