1.对基本数据类型的数组的排序

(1)Arrays类中的sort()使用的是“经过调优的快速排序法”;

(2)比如int[]，double[]，char[]等基数据类型的数组，Arrays类之只是提供了默认的升序排列，没有提供相应的降序排列方法。

(3)要对基础类型的数组进行降序排序，需要将这些数组转化为对应的封装类数组，如Integer[]，Double[]，Character[]等，对这些类数组进行排序。(其实还不如先进行升序排序，自己在转为降序)。

用默认的升序对数组排序

函数原型：

• static void sort(int[] a) 对指定的 int 型数组按数字升序进行排序。
• static void sort(int[] a, int fromIndex, int toIndex) 对指定 int 型数组的指定范围按数字升序进行排序。

代码实例

import java.util.Arrays;
public class ArraysSort_11 {
    public static void main(String args[])
    {
        int[] a={1,4,-1,5,0};
        Arrays.sort(a);
        //数组a[]的内容变为{-1,0,1,4,5}
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+"  ");
    }
}

2.对复合数据类型的数据的排序

函数原型：
(1)public static void sort(T[] a，Comparator c) 根据指定比较器产生的顺序对指定对象数组进行排序。

(2)public static void sort(T[] a，int fromIndex，int toIndex，Comparator c) 根据指定比较器产生的顺序对指定对象数组的指定范围进行排序。

说明：这个两个排序算法是“经过调优的合并排序”算法。
代码实例

package com.shuzu;

import java.util.Arrays;
import java.util.Comparator;

public class fuhepaixu {
	Point[] arr;
	fuhepaixu(){
		arr =new Point[4];
		for(int i=0;i<4;i++) {
			arr[i]=new Point();
		}
	}
	public static void main(String args[]) {
		fuhepaixu f =new fuhepaixu();
		f.arr[0].x=1;
		f.arr[1].x=2;
		f.arr[2].x=0;
		f.arr[3].x=4;
		f.arr[0].y=2;	
		f.arr[1].y=3;
		f.arr[2].y=1;
		f.arr[3].y=0;
		Arrays.sort(f.arr,new myComparator());
		for(int j=0;j<4;j++) {
			System.out.println("("+f.arr[j].x+","+f.arr[j].y+")");
		}
	}

}

class Point{
	int x;
	int y;
}

class myComparator implements Comparator{
	public int compare(Object arg0,Object arg1) {
		Point t1 =(Point)arg0;
		Point t2 =(Point)arg1;
		if(t1.x!=t2.x) {
			return t1.x>t2.x?1:-1;
		}
		else {
			return t1.y>t2.y?1:-1;
		}
	}
}

Comparator是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足要求时，可写一个比较器来完成两个对象之间大小的比较。Comparator体现了一种策略模式(strategy design pattern)，就是不改变对象自身，而用一个策略对象(strategy object)来改变它的行为。

PS：关于？：公式
a>b?A:B
意思是如果a>b则这个式子的值为A；
否则值为B

1.快速排序：首先是最简单的Array.sort，直接进行排序：

public static void main(String[] args) {        
        int[] arr = {4,3,5,1,7,9,3};
        Arrays.sort(arr);
        for (int i : arr){
            System.out.println(i);
        }

点击运行即可输出已排序的数组数字。

2.部分排序法：使用Array.sort还可进行选择想要排序的部分数字，如将下角标编号为1~4的数字进行排序，其他数字顺序不变。

public static void main(String[] args) {        
        int[] arr = {4,3,5,1,2,9,3,0};        
        Arrays.sort(arr,1,4);        
        for (int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+",");
        }
    }

输出结果为：4,1,3,5,2,9,3,0, 可见仅下标为1~4的数字进行了排序。

3.冒泡排序法：顾名思义，从下到上，两两进行比较，越小的越往上，从而形成由小到大的排序。

public static void bubble(int[] arr){        
        int temp;
        //根据角标进行比较，
        for(int i = 0; i<arr.length; i++){
            //j是数组的最后一个角标
            for (int j = arr.length-1; j > i; j--) {                
                if (arr[j] < arr[j - 1]) {
                    //从后往前进行比较，小数往前，一轮之后最小数就在最前面了
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }    
    public static void main(String[] args) {    
        int[] arr = {3,22,5,3,66,2,9};        
        bubble(arr);        
        //使用foreach循环输出
        for(int x : arr){
            System.out.println(x);
        }
        //使用字符串表达形式输出，输出形式更为直观        
        System.out.println(Arrays.toString(arr));
    }

1.冒泡排序(Bubble Sort)

冒泡排序的思想：
       从序列的一端开始向另一端冒泡，可以从左往右冒泡，也可以从右往左冒泡，依次比较相邻的两个数的大小(比大还是比小看要求)。

import java.util.Arrays;
//冒泡排序
public class BubbleSort_01 {
	public static void main(String[] args) {
		int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		for (int i = 0; i < a.length-1; i++) {
			for (int j = 0; j < a.length-1-i; j++) {
				if (a[j]>a[j+1]) {
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
				}
			}
		}
		System.out.println(Arrays.toString(a));
	}
}

2.选择排序(Select Sort)

选择排序的思想：
       首先，找到数组中最小(最大)的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小(最大)的元素，拎出来，和数组的第二个元素交换位置，如此循环，知道整个数组排序完成。

import java.util.Arrays;
//选择排序:先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。
public class SelectSort_02 {
	public static void main(String[] args) {
        //标记第一个为待比较的数
        //然后从后面遍历与第一个数比较
        //如果小,就交换最小值
        //保存最小元素的下标
        //找到最小值后，将最小的值放到第一的位置，进行下一遍循环
        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        for (int i = 0; i < a.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[index]) {
                    index = j;
                }
            }
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
        System.out.println(Arrays.toString(a));
    }
}

3.插入排序(Insert Sort)

插入排序的思想：
       和我们打扑克牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。
       那如果我们不是从牌堆中摸牌，而是左手里面初始化就是一堆乱牌呢？一样的套路，我们把牌往手的右边挪一挪，把手的左边空出一点位置来，然后再乱牌中抽一张出来，插入到左边，再抽一张出来，插入到左边，每次插入都插入到适合的位置时刻保持左手里的牌是有序的，知道右边的牌抽完，则排序完毕。
       在第一轮中，从未排序区域随机拿出一个数字，既然是随机，那我们就获取第一个，然后插入到已排序区域中，此时已排序区域是空，那么就不做比较，默认自身已经是有序的了(在写代码时候，从下标为1的元素开始即可)。

import java.util.Arrays;
 //插入排序:定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。
    public static void main(String[] args) {
        //长度不减1，是因为要留多一个位置方便插入数
        //定义待插入的数
        //找到待插入数的前一个数的下标
        //拿a[i]与a[i-1]的前面数组比较
        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        for (int i = 0; i < a.length; i++) {
            int insertValue = a[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertValue < a[insertIndex]) {
                a[insertIndex + 1] = a[insertIndex];
                insertIndex--;
            }
            a[insertIndex + 1] = insertValue;
        }
        System.out.println(Arrays.toString(a));
    }
}

4.希尔排序(Shell Sort)

希尔排序的思想：
       首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序。
       增量这里可以有所不同，比如有10个数要进行排序，你设置的增量是4，那么a[0],a[4]与a[8]，a[1],a[6]与a[9]是一组，分组进行插入排序，之后再缩小增量，再进行插入排序。

import java.util.Arrays;
//希尔排序：插入排序的升级
public class ShellSort_04 {
        //将整个数组分为若干个子数组
        //遍历各组的元素
        //交换元素
        int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        for (int gap = a.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < a.length; i++) {
                for (int j = i - gap; j >= 0; j = j - gap) {
                    if (a[j] > a[j + gap]) {
                        int temp = a[j];
                        a[j] = a[j + gap];
                        a[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
}

5.快速排序(Quick Sort)

6.归并排序(Merge Sort)

7.堆排序(Heap Sort)

8.计数排序 (Count Sort)

9.桶排序(Bucket Sort)

10.基数排序(Raix Sort)

其他排序方法请参考：这篇博客 或者 这篇博客