排序算法是数据结构中的经典算法知识点，也是笔试面试中经常考察的问题，平常学的不扎实笔试时候容易出洋相，回来恶补，尤其是碰到递归很可能被问到怎么用非递归实现。。。
内部排序：
插入排序：直接插入排序
选择排序：直接选择排序
交换排序：冒泡排序，改进的冒泡排序；快速排序，非递归实现快速排序
//堆排序：。。。
//归并排序：。。。
import java.util.Stack;
public class SortTest {
/**
* 插入排序:假定指针所指数据之前的序列为有序，所要做的便是将之后的数据插入到之前的有序序列中，
具体做法是从后往前比较指针前序列与指针所指数据的大小，如果前者大于后者，则将前者后移一
位（也可以将其与前面一位交换），在向前比较，直至前者不大于前者，此时插入数据。
* @param a
*/
public static void insertSort(int[] a){
if(a!=null){
int temp,j;
for(int i=1;i<a.length;i++){
temp = a[i];
j=i;
if(a[j-1]>temp){
while(j>=1&&a[j-1]>temp){
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
}
}
/**
* 直接选择排序
* @param a
*/
public static void selectSort(int[] a){
int i,j;
int temp = 0;
int flag = 0;
int n = a.length;
for(i=0;i<n;i++){
temp = a[i];
flag = i;
for(j=i+1;j<n;j++){
if(a[j]<temp){
temp = a[j];
flag = j;
}
}
if(flag!=i){
a[flag] = a[i];
a[i] = temp;
}
}
}
/**
* 冒泡排序
* @param a
*/
public static void bubbleSort(int[] a){
int i,j;
int len = a.length;
int tmp;
for(i=0;i<len;i++){
for(j=0;j<len-i-1;j++){
if(a[j+1]<a[j]){
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
/**
* 改进冒泡
* @param arr
*/
public void EffectBubbleSort(int[] arr, int low, int high){
int i,j;
boolean flag = true;
//ture表明上一趟有交换，如果为false表明无交换已经有序，停止循环
for(i=low; i<high && flag; i++){
flag = false;
for(j=high-1; j>=i; j--){
if(arr[j-1]>arr[j]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
}
}
/**
* 快速排序:
* 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小，
* 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* @param a
* @param low
* @param high
*/
public static void sort(int[] a, int low, int high){
int i,j;
int index;
if(low>=high)
return;
i = low;
j = high;
index = a[i];
while(i<j){
while(i<j&&a[j]>=index)
j--;
if(i<j)
a[i++] = a[j];
while(i<j&&a[i]<index)
i++;
if(i<j)
a[j--] = a[i];
}
a[i] = index;
sort(a, low, i-1);
sort(a, i+1, high);
}
/**
* 快速排序另一种实现,
* @param a
* @param start
* @param end
*/
public static void qsort(int data[], int start, int end) {
if (end <= start) {
return;
}
int last = start;
for (int i = start + 1; i <= end; i++) {
if (data[i] < data[start]) {
int temp = data[++last];
data[last] = data[i];
data[i] = temp;
}
}
int temp = data[last];
data[last] = data[start];
data[start] = temp;
sort(data, start, last - 1);
sort(data, last + 1, end);
}
/**
* 快速排序非递归，参考
* @param array
* @author http://computerdragon.blog.51cto.com/6235984/1305987
*/
public void quicksort(int[] array) {
if (array == null || array.length == 1) return;
//存放开始与结束索引
Stack<Integer> s = new Stack<Integer>();
//压栈
s.push(0);
s.push(array.length - 1);
//利用循环里实现
while (!s.empty()) {
int right = s.pop();
int left = s.pop();
//如果最大索引小于等于左边索引，说明结束了
if (right <= left) continue;
int i = partition(array, left, right);
if (left < i - 1) {
s.push(left);
s.push(i - 1);
}
if (i + 1 < right) {
s.push(i+1);
s.push(right);
}
}
}
//找到轴心，进行交换,上面qsort()中扫描交换的实现也可行
public int partition (int[] data, int first, int end)
{
int temp;
int i=first,j=end;
if(first<end)
{
temp=data[i];
//当i=j的时候，则说明扫描完成了
while(i<j)
{
//从右边向左边扫描找到一个小于temp的元素
while(j>i&&data[j]>temp)j--;
if(i<j)
{
//将该元素赋值给temp
data[i]=data[j];
//赋值后就应该将i+1指向下一个序号
i++;
}
//然后从左边向右边开始扫描，找到一个大于temp的元素
while(i<j&&temp>data[i])i++;
if(i<j)
{
//将该元素赋值给temp
data[j]=data[i];
//赋值后就应该将j-1指向前一个序号
j--;
}
}
//将轴数据放在i位置中
data[i]=temp;
}
return i;
}