选择排序
选择排序就是遍历数组找到最小的元素，与第一个交换位置；第一个已经排好序了，而后从第二个开始往后遍历，找到最小的元素，与第二个元素交换位置。而后从第三个元素开始往后遍历比较......直至所有元素排好序。
选择排序不占用额外空间，时间复杂度为O(n2)。
动图演示（图片来源于网络）
插入排序
插入排序即从第二个元素开始往后遍历，遍历到的元素与前面的元素比较，如果比自己前一个元素小，就与前一个元素交换位置，又与自己前一个位置的元素比较，比前一个小就交换，直到前一个元素比自己大。又在原位置往后遍历。
插入排序最好的情况就是已经排好序的数组，时间复杂度为O(n);
插入排序最差的情况就是逆序的数组，时间复杂度为O(n2);
动图演示（图片来源于网络）
冒泡排序
冒泡排序就是每次遍历把最大的数放在最后面，时间复杂度为O(n2)
动图演示（图片来源于网络）
shell（希尔）排序
希尔排序是插入排序的优化。设置一个gap值（步长），根据步长将数组元素分组，i，i+gap，i+gap+gap....一组，将组内元素排序。然后将步长减小（减半），再分组排序。直到步长等于一，进行一次插入排序。
为什么最后进行一次插入排序，而说希尔排序是插入排序的优化呢？
因为插入排序的时间复杂度在O(n)—O(n^2)之间，插入排序和数组的有序性有关，如果是逆序则需要O(n^2)，而希尔排序最后一次插入排序之前数组已经局部有序了，所以能提高效率，减少时间复杂度。
希尔排序的时间复杂度为O(n^1.3)—O(n^2)。
快速排序
设置两个变量 low、high，排序开始时：low=0，high=size-1。
整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
循环 2-3 步骤，直到 low=high，该位置就是基准位置。
把基准数据赋给当前位置。
第一趟找到的基准位置，作为下一趟的分界点。
递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。
最终就会得到排序好的数组。
快速排序时间复杂度为：O(nlogn);
代码展示：
1 package sort; 2 3 import java.util.Random; 4 5 public class Sort { 6 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 int arry[]= new int[10]; 10 11 getarry(arry); 12 selectionsort(arry); 13 System.out.println("选择排序："); 14 printout(arry); 15 16 System.out.println(); 17 System.out.println("插入排序："); 18 getarry(arry); 19 insertionsort(arry); 20 printout(arry); 21 22 System.out.println(); 23 System.out.println("Shell排序："); 24 getarry(arry); 25 shellsort(arry); 26 printout(arry); 27 28 System.out.println(); 29 System.out.println("快速排序："); 30 getarry(arry); 31 quicksort(arry,0,arry.length-1); 32 printout(arry); 33 } 34 35 //数组输出 36 public static void printout(int []arry){ 37 for(int i=0;i<arry.length;i++) 38 { 39 System.out.print(arry[i]+" "); 40 } 41 } 42 43 //生成随机数组 44 public static void getarry(int [] a){ 45 Random rand=new Random(); 46 for(int i=0;i<a.length;i++) 47 { 48 a[i]=rand.nextInt(100)+1; 49 } 50 } 51 52 53 //交换 54 public static void exch(int [] a,int i,int j) { 55 int n=a.length; 56 if(i<0 || j>n ||i>n||j<0) 57 System.out.println("error"); 58 int tem=0; 59 tem=a[j]; 60 a[j]=a[i]; 61 a[i]=tem; 62 } 63 64 //选择排序 65 public static void selectionsort(int [] a) { 66 int n=a.length; 67 for (int i=0;i<n;i++){ 68 for(int j=i+1;j<n;j++){ 69 if(a[j]<a[i]){ 70 exch(a,i,j); 71 } 72 } 73 } 74 } 75 76 //插入排序 77 public static void insertionsort(int [] a) { 78 int n=a.length; 79 //int k=0; 80 for(int i=1;i<n;i++){ 81 for(int j=i;j>0;j--){ 82 /* 83 * if(a[j]<a[j-1] exch(a,j,j-1); 这种方式也能排序，但是计算复杂度更高 84 */ 85 if(a[j]>a[j-1]) break; //如果前一个数比自己小，就不用往前查找了，直接看后一个数。 86 exch(a,j,j-1); 87 } 88 } 89 } 90 91 //shell排序 92 public static void shellsort(int [] a){ 93 int n=a.length; 94 for(int gap=n/2;gap>0;gap/=2){ 95 for(int i=gap;i<n;i++){ 96 for(int j=i;j-gap>=0;j-=gap){ 97 /* if(a[j-gap]>a[j]){ 98 exch(a,j-gap,j); 99 }*/ 100 // if(a[j-gap]<a[j]) continue; 101 if(a[j-gap]<a[j]) break;//如果这组前一个数比自己小，则不用进行交换。直接退出 102 exch(a,j-gap,j); 103 } 104 } 105 } 106 } 107 108 //快速排序 109 public static void quicksort(int []a,int low,int high){ 110 if(low<high){ //如果low小于high说明排好序了，递归边界 111 int i=low,j=high; 112 int key=a[i]; //key是基准数，取数组第一个数，即a[low]； 113 while(i<j){ //当low<high才继续排序，若low>high说明该数组已经根据基准数分为两部分，需要再把key左右两边分为两部分排序 114 while(i<j && a[j]>=key) j--; //从队尾找比key大的数，如果小于等于key，则j--； 115 if(i<j) a[i]=a[j]; //此时已经找到比key小的数，如果满足i<j，则将a[j]赋值给a[i]；把比key小的数放到前面 116 while(i<j && a[i]<=key) i++; //从队头开始找比key大的数，如果小于等于key，继续往后找即：i++ 117 if(i<j) a[j]=a[i]; //跳出上一个循环说明已经找到比key大的数，或i=j；若满足i<j，将a[i]赋值给a[j]，把比key大的数放到后面; 118 } 119 a[i]=key; //跳出循环说明i已经等于j，则将key放到中间位置，此时key前面都是比key小的数，key后面都是比key大的数。 120 quicksort(a,low,i-1); //基准数前半部分，继续递归细分 121 quicksort(a,i+1,high); //基准数后半部分，继续递归细分 122 } 123 } 124 }