public class SortDemo {
// private static long[] arr = {6,5,2,7,1,8,4,3};
private static long[] arr = {1,2,3,4,5,6,7,8};
private static int count = 0;
/**
* 冒泡排序
* O(n2)
*/
public static void bubble(){
long temp = Long.MIN_VALUE;
int len = arr.length;
for(int j = 0;j<len;j++){
for(int i = 0;i<len-1;i++){
if(arr[i]>arr[i+1]){
temp = arr[i+1];
arr[i+1] = arr[i];
arr[i] = temp;
}
}
}
}
/**
* 选择排序
* O(n2)
*/
public static void select(){
int len = arr.length;
long temp = Long.MIN_VALUE;
int index = 0;
for(int j = 0;j<len;j++){
index = j;
for(int i = j;i<len;i++){
if(arr[i]<arr[index]){
index = i;
}
}
temp = arr[j];
arr[j] = arr[index];
arr[index] = temp;
print();
}
}
/**
* 插入排序
* O(n2)
*/
public static void insert(){
int len = arr.length;
long temp;
for(int i=1;i<len;i++){
int j = i-1;
temp = arr[i];
while(j>=0 && temp<arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
print();
}
}
/**
* 快速排序
* O(N*longN)
*/
public static void quick(){
quick(arr);
print();
}
private static long[] quick(long[] a){
if(a.length<=1)return a;
long temp = 0;
int index = 0;
for(int i = 0;i<a.length-1;i++){
if(a[i]<a[a.length-1]){
temp = a[i];
a[i] = a[index];
a[index++] = temp;
}
}
temp = a[a.length-1];
a[a.length-1] = a[index];
a[index] = temp;
if(index==0)return a;
long[] temp1 = new long[index];
long[] temp2 = new long[a.length-index-1];
System.arraycopy(a, 0, temp1, 0, index);
System.arraycopy(a, index+1, temp2, 0, a.length-index-1);
System.arraycopy(quick(temp1), 0, a, 0, index);
System.arraycopy(quick(temp2), 0, a, index+1, a.length-index-1);
return a;
}
/**
* 归并排序
* O(N*longN)
*/
public static void merge (){
arr = merge(arr);
print();
}
private static long[] merge(long[] a){
long[] c = new long[a.length];
int mid = a.length/2;
long[] temp1 = new long[mid];
long[] temp2 = new long[a.length-mid];
if(mid>1){
System.arraycopy(a, 0, temp1, 0, mid);
System.arraycopy(a, mid, temp2, 0, a.length-mid);
temp1 = merge(temp1);
temp2 = merge(temp2);
System.arraycopy(temp1, 0, a, 0, mid);
System.arraycopy(temp2, 0, a, mid, a.length-mid);
}
int i=0,j=mid,index=0;
while(i<mid && j<a.length && index<a.length-1){
if(a[i]<a[j]){
c[index++] = a[i++];
}else{
c[index++] = a[j++];
}
}
while(index<a.length && i<mid){
c[index++] = a[i++];
}
while(index<a.length && j<a.length){
c[index++] = a[j++];
}
return c;
}
public static void print(){
for(long v:arr){
System.out.print(v);
}
System.out.println();
}
public static void main(String[] args) {
quick();
}
}
java实现排序
原文：http://blog.51cto.com/12336708/2104475
