Arrays.sort() 采用了2种排序算法 -- 基本类型数据使用快速排序法，对象数组使用归并排序.
java的Collections.sort算法调用的是归并排序，它是稳定排序
方法一：直接插入
1.基本思路：
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
2.代码实现：
（1）首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，从第二个数字开始插入，排序好。再依次插入第三个。。。
（2）设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
（3）从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。
（4）将当前数放置到空着的位置，即j+1。
public static void insertSort(int[] data){
int temp;
for(int i=1;i<data.length;i++){//取第i个数,插入前边的有序的序列
temp = data[i];
int j;
for(j =i-1;j>=0;j--){//从第i-1的位置上开始比较
if(data[j]>temp){//若前面的数大，则往后挪一位
data[j+1] = data[j];
}else {
break;//否则，说明要插入的数比较大
}
}
data[j+1] = temp;//找到这个位置，插入数据
}
}
3.时间复杂度和空间复杂度：
直接插入排序的平均复杂度为O(n²)，最坏时间复杂度：O(n²)，空间复杂度：O(1)，没有分配内存。
方法二：希尔排序
1.定义：
针对直接插入排序的下效率问题，有人对次进行了改进与升级，这就是现在的希尔排序。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
2.基本思路：
数的个数为length，i=length/2，将下标差值为i的数分为一组，构成有序序列。
再取i=i/2 ，将下标差值为i的数分为一组，构成有序序列。
重复第二步，直到k=1执行简单插入排序。
思路
（1）希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
（2）由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。
（3）希尔排序举例：
3.代码实现：
（1）首先确定每一组序列的下标的间隔，循环每次需要的间隔：int i = length/2; i >0 ; i /= 2
（2）然后将每一组序列中元素进行插入排序，第二组第一个插入的数字是第一组第一个插入数字之后的那个数组，从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列，不是一个一个子序列循环，而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。
（3）直到i=0为止。
public static void shellSort(int[] array){
int length = array.length;
for (int i = length/2; i >0 ; i /= 2) {//序列的间隔，一直到间隔为一，这时候就只有一个子序列
for (int j=i;j<length;j++){//从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列
int temp = array[j];//里面就是直接插入算法
int k;
for(k = j-i; k>=0;k -= i){//实现各个数字插入排序到不同的序列中，直到间隔为1的时候，只有一个序列，就是完全的一个直接插入排序
if(temp< array[k]){
array[k+i] = array[k];
}else{
break;
}
}
array[k+i] = temp;//把数字插入到位置上
}
}
System.out.println(Arrays.toString(array));
}
4.时间复杂度和空间复杂度：
希尔排序的平均时间复杂度为O(n²)，空间复杂度O(1) 。
方法三：简单选择
1.基本思路：
基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。
2.代码实现：
（1）确定要插入最小值的位置，从0开始到最后int i = 0; i <len ; i++
（2）将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较，再把最小值存放到min
（3）将最小值所在位置上的数字和开始位置上的数字交换
public static void selectSort(int[] array){
int len = array.length;
for (int i = 0; i <len ; i++) {//确定每次开始的位置
int min = array[i];//设定开始数字为最小的值最小值
int flag = i;
for(int j=i+1;j<len;j++){//把最小值存放到min,从开始数字向后一个个和min比较，再把最小值存放到min
if(min>array[j]){
min = array[j];
flag = j;
}
}
if(flag != i){
array[flag] = array[i];
array[i] = min;
}
}
}
3.时间复杂度：
简单选择排序时间复杂度：O（n^2）
方法四：堆排序
1.基本思路：
（1）若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：
任意一节点指针 i：父节点：i==0 ? null : (i-1)/2
左孩子：2*i + 1
右孩子：2*i + 2
（2）堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；
（3）建立大根堆：
n个节点的完全二叉树array[0，...，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。
对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。
之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。
反复利用上述调整堆的方法建堆，直到根节点。
（4）堆排序：（大根堆）
①将存放在array[0，...，n-1]中的n个元素建成初始堆；
②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；
③将数组中array[0，...，n-1]前n-1个元素再次形成大根堆，再重复第②③步，直到堆中仅剩下一个元素为止。
2.代码实现：
public static int[] buildMaxHeap(int[] array,int length){//截取数组从0到length，构建大根堆
for (int i = (length-2)/2; i >=0 ; i--) {//从最后一个有子结点的结点开始调整，（减一）一直调节到根节点
adjustDownToUp(array,i,length);
}
return array;
}
private static void adjustDownToUp(int[] array, int i, int length) {//i要调整的结点
int temp = array[i];
//int j = i*2+1;//取得左孩子
for (int j=i*2+1;j<length;j=j*2+1){//从该节点一直调节到叶子结点，因为上层调节改变之后，会影响下层结构，所以一直循环到叶子结点。
if(j+1<length && array[j]<array[j+1]){//有又孩子，且右孩子数值更大
j++;//取更大结点的索引
}
if(temp<array[j]){//根节点比最大的值小
array[i] = array[j];//调整根节点的值为最大值
i=j;//把空余的位置给i
//array[j] = temp;
}
}
array[i] = temp;//找到最后空余的位置，填上向下调整的值
}
public static void heapSort(int[] array){
int len = array.length;
int temp;
for (int i = len; i >0; i--) {
array=buildMaxHeap(array,i);
temp = array[0];
array[0] = array[i-1];
array[i-1]=temp;
}
System.out.println(Arrays.toString(array));
}
3.时间复杂度：
时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);
方法五：冒泡排序
1.基本思路：
一次冒泡将序列中从头到尾所有元素两两比较，将最大的放在最后面。
将剩余序列中所有元素再次两两比较，将最大的放在最后面。
重复第二步，直到只剩下一个数。
2.代码实现：
public static void bubbleSort(int[] array){
for (int i = 0; i <array.length ; i++) {//第i冒泡,一次冒泡，会确定一个最大值
for (int j = 0; j <array.length-i-1 ; j++) {//从头一直到已经确定的位置前，两两比较
int temp = array[j];
if(array[j]>array[j+1]){
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
3.时间复杂度：
冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1),它是一种稳定的排序算法。
方法六：快排
1.基本思路：
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2.代码实现：
public static void quickSprt(int[] array,int low,int high){
if(low>=high) return;
int left = low;
int right = high;
int pivot = array[left];//设立基准点
while (left<right){
while (left<right && array[right]>pivot)//从右向左，大数位置不变
right--;
array[left] = array[right];//把小数移到左边
while (left < right && array[left]<pivot) //从左向右，小数位置不变
left++;
array[right] = array[left];//把大数移到右边
}
array[left]=pivot;
quickSprt(array,low,left-1);
quickSprt(array,left+1,high);
}
3.时间复杂度：
虽然 快排的时间复杂度达到了 O(n²)，但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。
方法七：归并排序
1.基本思路：
对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表（直到剩余一个数字），在对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。
（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
（4）重复步骤3直到某一指针达到序列尾
（5）将另一序列剩下的所有元素直接复制到合并序列尾
2.代码实现：
//归并排序
public static int[] mergeSort(int[] array,int low,int high){
if(low<high){
int mid = (low+high)/2;
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
merge(array,low,mid,high);//归并
}
return array;
} private static void merge(int[] array, int low, int mid, int high) {
int i = low;//指针，前一个序列的头指针
int j = mid+1;//指针，后一个序列的头指针
int[] temp = new int[high-low+1];
int k=0;
while (i<=mid && j<= high){
if (array[i]<array[j]){//从头比较两个序列，小的放入临时数组temp
temp[k++] = array[i++];//前一个序列指针后移一位
}else {
temp[k++] = array[j++];//后一个序列指针后移一位
} }
//最后只会剩下一组序列
while (i<=mid){
temp[k++] = array[i++];//把前一个指针剩余的数字放入临时数组
}
while (j<=high){
temp[k++] = array[j++];//把后一个指针剩余的数字放入临时数组
} for (int m = 0; m <high-low+1 ; m++) {
array[low+m] = temp[m];
} }
3.时间复杂度：
时间复杂度：O(nlog2n)
方法八：基数排序
1.基本思路：
（1）按照所有的数的个位数，在0---9 的基数序列中，把各个数字排入，每一个数字基数上也是一个序列。
（2）将新序列取出按基数顺序取出，形成新数组。
（3）再按照十位数字进行排序，插入到基数序列，循环（1）（2）
2.代码实现：
public static void baseSort(int[] array){
ArrayList<ArrayList<Integer>> queue = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i <10 ; i++) {
ArrayList<Integer> queue2 = new ArrayList<Integer>();
queue.add(queue2);//创建一个基数从0---9 每个数字上都是一个list
}
//找到最大值，并判断最大值是几位数
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(max<array[i]){
max = array[i];
}
}
int time = 0;
while(max>0){
max /= 10;
time++;
}
for (int i = 0; i < time; i++) {//循环每一个位数（个位、十位、百位）
for (int j = 0; j <array.length ; j++) {//循环数组，取每一个值
int x = array[j] % (int)Math.pow(10,i+1) / (int)Math.pow(10,i);
ArrayList<Integer> queue3 = queue.get(x);;
queue3.add(array[j]);
queue.set(x,queue3);
}
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue4 = queue.get(k);
array[count] = queue4.get(0);
queue4.remove(0);
count++;
}
}
}
}
3.时间复杂度：
时间复杂度：O(nlog2n)
总结：
| 排序算法 | 思路 | 排序算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 |
空间复杂度 （辅助存储） |
是否稳定 |
| 插入排序 | 将一个数字插入已经排列好的序列中 | 直接插入法 | O(N) | O(N2) | O(N2) | O(1) | 稳定 |
| 希尔排序 | O(N) | O(N1.3) | O(N2) | O(1) | 不稳定 | ||
| 选择排序 | 每一次循环都是选择出最小（最大）的数字放到数组最前面（最后面）的位置 | 简单选择 | O(N) | O(N2) | O(N2) | O(1) | 不稳定 |
| 堆排序 | O(N*log2N) | O(N*log2N) | O(N*log2N) | O(1) | 不稳定 | ||
| 交换排序 |
（冒泡）两两交换，大的后移，再次两两交换 （快速）和基准交换，比基准大排右边，比基准小排左边 |
冒泡排序 | O(N) | O(N2) | O(N2) | O(1) | 稳定 |
| 快速排序 | O(N*log2N) | O(N*log2N) | O(N2) | O(log2n)~O(n) | 不稳定 | ||
| 归并排序 | O(N*log2N) | O(N*log2N) | O(N*log2N) | O(n) | 稳定 | ||
| 基数排序 | O(d(r+n)) | O(d(r+n)) | O(d(r+n)) | O(rd+n) | 稳定 | ||