排序算法是数据结构中的经典算法知识点，也是笔试面试中经常考察的问题，平常学的不扎实笔试时候容易出洋相，回来恶补，尤其是碰到递归很可能被问到怎么用非递归实现。。。
内部排序：
插入排序：直接插入排序
选择排序：直接选择排序
交换排序：冒泡排序，改进的冒泡排序；快速排序，非递归实现快速排序
//堆排序：。。。
//归并排序：。。。
1 import java.util.Stack; 2 3 public class SortTest { 4 5 /** 6 * 插入排序:假定指针所指数据之前的序列为有序，所要做的便是将之后的数据插入到之前的有序序列中，
具体做法是从后往前比较指针前序列与指针所指数据的大小，如果前者大于后者，则将前者后移一
位（也可以将其与前面一位交换），在向前比较，直至前者不大于前者，此时插入数据。 7 * @param a 8 */ 9 public static void insertSort(int[] a){ 10 if(a!=null){ 11 int temp,j; 12 for(int i=1;i<a.length;i++){ 13 temp = a[i]; 14 j=i; 15 if(a[j-1]>temp){ 16 while(j>=1&&a[j-1]>temp){ 17 a[j] = a[j-1]; 18 j--; 19 } 20 a[j] = temp; 21 } 22 } 23 } 24 } 25 26 27 28 29 /** 30 * 直接选择排序 31 * @param a 32 */ 33 public static void selectSort(int[] a){ 34 int i,j; 35 int temp = 0; 36 int flag = 0; 37 int n = a.length; 38 for(i=0;i<n;i++){ 39 temp = a[i]; 40 flag = i; 41 for(j=i+1;j<n;j++){ 42 if(a[j]<temp){ 43 temp = a[j]; 44 flag = j; 45 } 46 } 47 if(flag!=i){ 48 a[flag] = a[i]; 49 a[i] = temp; 50 } 51 } 52 } 53 54 55 /** 56 * 冒泡排序 57 * @param a 58 */ 59 public static void bubbleSort(int[] a){ 60 int i,j; 61 int len = a.length; 62 int tmp; 63 for(i=0;i<len;i++){ 64 for(j=0;j<len-i-1;j++){ 65 if(a[j+1]<a[j]){ 66 tmp = a[j]; 67 a[j] = a[j+1]; 68 a[j+1] = tmp; 69 } 70 } 71 } 72 73 } 74 /** 75 * 改进冒泡 76 * @param arr 77 */ 78 public void EffectBubbleSort(int[] arr, int low, int high){ 79 int i,j; 80 boolean flag = true; 81 //ture表明上一趟有交换，如果为false表明无交换已经有序，停止循环 82 for(i=low; i<high && flag; i++){ 83 flag = false; 84 for(j=high-1; j>=i; j--){ 85 if(arr[j-1]>arr[j]){ 86 int temp = arr[j]; 87 arr[j] = arr[j-1]; 88 arr[j-1] = temp; 89 flag = true; 90 } 91 } 92 } 93 } 94 /** 95 * 快速排序: 96 * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小， 97 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 98 * @param a 99 * @param low 100 * @param high 101 */ 102 public static void sort(int[] a, int low, int high){ 103 int i,j; 104 int index; 105 if(low>=high) 106 return; 107 i = low; 108 j = high; 109 index = a[i]; 110 while(i<j){ 111 while(i<j&&a[j]>=index) 112 j--; 113 if(i<j) 114 a[i++] = a[j]; 115 while(i<j&&a[i]<index) 116 i++; 117 if(i<j) 118 a[j--] = a[i]; 119 120 } 121 a[i] = index; 122 sort(a, low, i-1); 123 sort(a, i+1, high); 124 } 125 /** 126 * 快速排序另一种实现, 127 * @param a 128 * @param start 129 * @param end 130 */ 131 public static void qsort(int data[], int start, int end) { 132 if (end <= start) { 133 return; 134 } 135 int last = start; 136 for (int i = start + 1; i <= end; i++) { 137 if (data[i] < data[start]) { 138 int temp = data[++last]; 139 data[last] = data[i]; 140 data[i] = temp; 141 } 142 } 143 int temp = data[last]; 144 data[last] = data[start]; 145 data[start] = temp; 146 sort(data, start, last - 1); 147 sort(data, last + 1, end); 148 } 149 /** 150 * 快速排序非递归，参考 151 * @param array 152 * @author http://computerdragon.blog.51cto.com/6235984/1305987 153 */ 154 public void quicksort(int[] array) { 155 if (array == null || array.length == 1) return; 156 //存放开始与结束索引 157 Stack<Integer> s = new Stack<Integer>(); 158 //压栈 159 s.push(0); 160 s.push(array.length - 1); 161 //利用循环里实现 162 while (!s.empty()) { 163 int right = s.pop(); 164 int left = s.pop(); 165 //如果最大索引小于等于左边索引，说明结束了 166 if (right <= left) continue; 167 168 int i = partition(array, left, right); 169 if (left < i - 1) { 170 s.push(left); 171 s.push(i - 1); 172 } 173 if (i + 1 < right) { 174 s.push(i+1); 175 s.push(right); 176 } 177 } 178 } 179 //找到轴心，进行交换,上面qsort()中扫描交换的实现也可行 180 public int partition (int[] data, int first, int end) 181 { 182 int temp; 183 int i=first,j=end; 184 if(first<end) 185 { 186 temp=data[i]; 187 //当i=j的时候，则说明扫描完成了 188 while(i<j) 189 { 190 //从右边向左边扫描找到一个小于temp的元素 191 while(j>i&&data[j]>temp)j--; 192 if(i<j) 193 { 194 //将该元素赋值给temp 195 data[i]=data[j]; 196 //赋值后就应该将i+1指向下一个序号 197 i++; 198 } 199 200 //然后从左边向右边开始扫描，找到一个大于temp的元素 201 while(i<j&&temp>data[i])i++; 202 if(i<j) 203 { 204 //将该元素赋值给temp 205 data[j]=data[i]; 206 //赋值后就应该将j-1指向前一个序号 207 j--; 208 } 209 } 210 //将轴数据放在i位置中 211 data[i]=temp; 212 } 213 return i; 214 215 } 216