- 选择排序
1、选择排序的思想
选择整个数组中最小的元素和第一个位置交换，然后在剩下的元素中选择最小的元素和第二个位置交换，以此类推
2、复杂度 n^2
- 插入排序
1、插入排序的思想
2、复杂度 n^2
当前索引（哨兵）左边的元素都是有序的，但是他们最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动
- 希尔排序
1、希尔排序的思想
使数组中任意间隔为h的数组都是有序的
2、希尔排序为什么快？
他权衡了子数组的规模和有序性
3、希尔排序的复杂度
小于n^2
- 归并排序
1、归并排序的思想
将数组递归不断的分成两半，分别排序，再把最后的结果合并起来，是一种分治的思想
2、复杂度： 线性对数
3、缺点：需要额外的空间，额外的空间和数组长度成正比
- 快排
- 三分向快排
package com.javalearn.suanfa;
import java.util.Arrays;
/**
* Created by buguniao on 16/2/21.
*/
public class QuickSort extends SuanFaTemplate {
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
double[] arr = quickSort.getRandomArray(100000);
long time = quickSort.run(arr);
System.out.println("time cost : " + time);
// System.out.println(Arrays.toString(arr));
}
@Override
public long run(double[] arr) {
long t1= System.currentTimeMillis();
sort(arr,0,arr.length-1);
long t2=System.currentTimeMillis();
return t2-t1;
}
public void sort(double[] arr,int lo,int hi){
if(lo>hi){
return;
}
double v= arr[lo];
int i=lo;
int j=hi;
while(i!=j){
while(i<j && arr[j]>=v){
j--;
}
while(i<j && arr[i]<=v){
i++;
}
if(i<j){
exchange(arr,i,j);
}
}
double t = arr[i];
arr[i]=v;
arr[lo]=t;
sort(arr,lo,i-1);
sort(arr,i+1,hi);
}
}
package com.javalearn.suanfa;
/**
* Created by buguniao on 16/2/21.
*/
public class QuickSort3Way extends SuanFaTemplate {
public static void main(String[] args) {
QuickSort3Way quickSort = new QuickSort3Way();
double[] arr = quickSort.getRandomArray(1000000000);
long time = quickSort.run(arr);
System.out.println("time cost : " + time);
}
@Override
public long run(double[] arr) {
long t1=System.currentTimeMillis();
sort(arr,0,arr.length-1);
long t2=System.currentTimeMillis();
return t2-t1;
}
public void sort(double[] arr,int lo,int hi){
if(lo>=hi){
return;
}
int lt=lo;
int gt=hi;
int i=lo+1;
double v = arr[lo];
while(i<=gt){
if(arr[i]>v){
exchange(arr,i,gt--);
}else if(arr[i]<v){
exchange(arr,lt++,i++);
}else{
i++;
}
}
sort(arr,lo,lt-1);
sort(arr,gt+1,hi);
}
}
