排序算法
package Suanfa;
public class Suanfa1 {
public static void sort(Comparable[] a) {
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w)<0;//判断v是否小于w
}
public static void exch(Comparable[] a,int i,int j) {
Comparable t=a[i];//将数组位置i和位置j元素交换
a[i]=a[j];
a[j]=t;
}
public static void show (Comparable[] a) {
for (int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
public static boolean isSorted (Comparable[] a) {
for(int i=1;i<a.length;i++) //判断是否全都有序
if(less(a[i],a[i-1]))return false;
return true;
}
public static void main(String[] args) {
String[] a= {"A","F","C","E","D"};
sort(a);
assert isSorted(a);
show(a);
}
}
选择排序
首先找到数组中最小的元素，将它和数组中的第一个元素交换。再次，在剩下的元素中找到最小的，和第二个元素交换。如此往复，直到所有元素都有序。
不断的在剩下数组中找最小的，然后和未排序的第一个交换。
public static void SelectSort(Comparable[] a) {
//按升序排序
int len=a.length;
for (int i=0;i<len;i++) {
int min=i;//定义初始化的最小数索引，不断的在内循环中更新最小数索引
for (int j=i;j<len;j++) {
if (less(a[j],a[min])) min=j;
}
exch(a,i,min);//在外循环，交换最小索引和当前索引
}
}
选择排序的内循环就是找出当前元素（包含）后面的所有元素中的最小元素。然后在外循环中交换当前元素和最小元素。
因此交换的总次数为len。
对于长度为N的数组，选择排序需要N^2/2次比较和N次交换。
总共有N次交换，总共需要比较（N-1）+（N-2）+（N-3）+（N-4）+.....+2+1=N(N-1)/2~N^2/2
特点：
运行时间和输入无关，每一次找出剩余数组的最小元素并能为下次排序提供任何信息。一个已排序的数组和随机数组排序时间相同。
数据移动是最少的，每次都只交换两个数组元素，总共只交换N次。
时间复杂度为O（n^2），空间复杂度为O（1）。
冒泡排序
相邻的元素两两比较，顺序相反则交换，每次都将最大的元素排到最后。若是倒序，则每次交换比较的次数是N+N-1+N-2+...+1=N(N-1)/2，时间复杂度为O（n2）
public static void BubbleSort(Comparable[] a) {
int N=a.length;
for(int i=0;i<N-1;i++) {
for(int j=0;j<N-i-1;j++) {
if(less(a[j+1],a[j])) {
exch(a,j,j+1);
}
}
}
}第一要遍历所有元素将最大元素移到（不断的交换）最右端，之后遍历前面还未排序的元素，将次大的元素移到倒数第二位置。
插入排序
插入排序是将未排序的数组（右侧），插入到已排序的数组（左侧），从后向前扫描，插入到左侧已排序的数组中，使得左侧始终保持有序。
插入排序所需要的时间取决有输入元素的初始顺序。
1.从第一个元素开始，该元素可以认为已经有序。
2.取出下一个元素，在已经排序的数组中，从后向前扫描。
3.如果该元素（已排序）大于新元素（未排序），则将两元素交换。
4.当所有比新元素大的所有元素都交换完后，该新元素就插入到已排序数组中。
public static void InserSort(Comparable[] a) {
int len=a.length;
for (int i=1;i<len;i++) {
for (int j=i;j>0&&less(a[j],a[j-1]);j--) {
exch(a,j,j-1);
}
}
}
对于随机排序的长度为N且主键不重复的数组，平均情况下，插入排序需要~N^2/4次比较以及N^2/4次交换。最坏情况下需要N^2/2次比较和N^2/2次交换。最好情况下需要N-1次比较和0次交换。
倒置：是指数组中两个顺序颠倒的两个元素。
插入排序需要交换操作和数组中倒置的数量相同，需要比较次数大于等于倒置的数量，小于等于倒置的数量加上数组大小再减一。
要大幅度提高插入排序的速度，需要在内循环中，将较大元素向右移动而不是总是不断的交换两个元素。（这样访问数组的次数能减半）。
对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间都是平凡级别的，两者之间的比是一个较小的常数。
插入排序平均时间复杂度O(n^2)，最好O(n)，平均O(n^2)，辅助空间O(1)
希尔排序
希尔排序是一种基于插入排序的快速排序算法。
希尔排序是使得数组中任意间隔为h的元素都是有序的。这样的数组称为h有序数组。
希尔排序一次能够移动h位，而插入排序一次只能移动1位。
将h按照N/3逐渐递减。
public static void ShellSort(Comparable[] a) {
int len=a.length;
int h=1;
while(h<len/3) h=3*h+1;
//得到最大的h，再逐渐h/3，直到h=1
while(h>=1) {
for(int i=h;i<len;i++) {
//将i从h到len，虽然最开始只是两个h有序数组比较，但之后会有更多的h有序数组比较
for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h) {
exch(a,j,j-h);
//每次都将a[j]和a[j-h],a[j-2*h]...元素交换，即每次移动可以移动h位
}
}
h=h/3;
}
}
希尔排序又称为递减增量排序，这里选择的递增序列为h=3*h+1。
如何选取递增序列也是重要问题。
希尔排序是一种不稳定排序算法，排序时间为
平均O(nlogn)~O(n^2)，最好情况为O(n^1.3)，最坏情况为O(n^2).辅助空间O(1)
冒泡排序
package newSuanfa;
/*
* 冒泡排序
* 相邻元素进行比较，如果顺序相反就进行交换，这样没一次外循环都会讲最大的元素浮到顶端（从小到大排序）
* 每次内循环都会重复从0到len-1相邻比较。
* 在冒泡排序中，如果某一趟执行完毕之后，没有做任何一次交换操作，比如数组[5,4,1,2,3],执行了两次外循环之后，分别将5和4调整到最终位置[1,2,3,4,5]。
* 此时执行第三次循环之后一次交换也没有做，则说明已经是有序的。
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
for(int i=0;i<arr.length;i++) {
boolean flag=true;
for(int j=0;j<arr.length;j++) {
if(arr[j]>arr[j+1]) {
swap(arr,i,j);
flag=false;
}
}
if(flag) {
break;
}
}
}
public static void swap(int[] arr,int i,int j) {
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
参考：https://www.cnblogs.com/chengxiao/p/6103002.html