#排序模板
public abstract class Sort<T extends Comparable<T>> {
public abstract void sort(T[] nums);
protected boolean less(T v,T w){
return v.compareTo(w)<0;
}
protected void swap(T[] a,int i,int j){
T t=a[i];
a[i]=a[j];
a[j]=t;
}
}
##选择排序
/**
* 选择排序：选出最小的一个放到第一个位置，再在第二个位置选出最小的
* 放到第二个位置
* 时间复杂度：N*N/2+N次交换，空间复杂度1.
*/
import Sort.Sort;
class Selection <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int len=nums.length;
for(int i=0;i<len;i++){
int min=i;
for(int j=1;j<len;j++){
if(less(nums[j],nums[min])){
min=j;
}
}
swap(nums,i,min);
}
}
}
##冒泡排序
/**
* 冒泡排序：从后往前遍历，从左到右不断和相邻的比较交换，不断的让最大的或者最小的冒泡到最后
* 优化：加个flag，初始化为false，如果遍历一遍之后没有元素交换说明已经有序直接退出。
*/
import Sort.Sort;
class BubbleSort <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
boolean flag=false;
int len=nums.length;
for(int i=len-1;i>0&&!flag;i--){
for(int j=0;j<i;j++){
flag=true;
if(less(nums[j+1],nums[j])){
flag=false;
swap(nums,j,j+1);
}
}
}
}
}
##插入排序
/**
* 插入排序：从头开始插，然后形成有序部分
* 说白了就是交换逆序对
*
*/
import Sort.Sort;
class InsertSort <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int len=nums.length;
for (int i=0;i<len;i++){
for(int j=i;j<len&&less(nums[j],nums[j-1]);j++){
swap(nums,j,j-1);
}
}
}
}
##希尔排序
/**
* 希尔排序：是插入排序的优化，插入排序是一个一个交换，每次交换一个
* 希尔排序是每次交换大于一个。给定一个h，对间隔h的进行比较交换
* h逐渐减小，最后h=1.数组有序。
*/
import Sort.Sort;
class InsertSort <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
int len=nums.length;
int h=1;
while(h<len/3){
h=3*h+1;
}
while(h>=1){
for (int i=h;i<len;i++){
for(int j=i;j>=h&&less(nums[j],nums[j-h]);j-=h){
swap(nums,j,j-h);
}
}
h=h/3;
}
}
}
##归并排序
/**
* 归并排序：将数组分成两部分，分别进行排序，然后归并起来
* 初始化一个复制数组
*/
import Sort.Sort;
class InsertSort <T extends Comparable<T>> extends Sort<T> {
T[] aux;
@Override
public void sort(T[] nums) {
//自顶向下归并排序
aux=(T[]) new Comparable[nums.length];
sort(nums,0,nums.length-1);
}
private void sort(T[] nums, int l, int h) {
if(l>=h){
return;
}
int mid=(l+h)<<1;
sort(nums,l,mid);
sort(nums,mid+1,h);
merge(nums,l,mid,h);
}
public void merge(T[] nums,int l,int m,int h){
int i=l;
int j=m+1;
for(int k=l;k<=h;k++){
aux[k]=nums[k];
}
for(int k=l;k<=h;k++){
if(i>l){
nums[k]=aux[j++];
}
else if(j>h){
nums[k]=aux[i++];
}
else if(aux[i].compareTo(aux[j])<=0){
nums[k]=aux[i++];
}else{
nums[k]=aux[j++];
}
}
}
}
##快速排序
/**
* 快速排序：首先先把数据随机打乱，然后选取一个值，然后让比这个数大的在前，小的在后。
* 然后在分别对这两个数组排序
*/
import Sort.Sort;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
class QuickSort <T extends Comparable<T>> extends Sort<T> {
@Override
public void sort(T[] nums) {
shuffle(nums);
sort(nums,0,nums.length-1);
}
private void shuffle(T[] nums) {
List<Comparable> list=Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
private void sort(T[] nums, int l, int h) {
if(h<=l){
return;
}
int j=patition(nums,l,h);
sort(nums,l,j-1);
sort(nums,j+1,h);
}
private int patition(T[] nums, int l, int h) {
int i=l;
int j=h+1;
T v=nums[l];
while(true){
while(less(nums[++i],v)&&i!=h);
while(less(v,nums[--j])&&j!=l);
if(i>=j){
break;
}
swap(nums,i,j);
}
swap(nums,l,j);
return j;
}
}
###快排性能分析
快排是原地排序，很考验选取的数的值，和数据的随机度，最好的情况下每次都能将数组对半分这样递归调用次数最少，复杂度是O(n*log(n))
最坏的情况是数组有序，找最小或者最大的元素，这样就是冒泡排序类似，复杂度O(n*n/2)
因此我们可以优化快排：
#当小数组的情况时，可以使用插入排序，插入排序快
#选取标准值的时候可以用三数取中，最好的情况时每次都能取到中位数，但是代价太高，可以取三个数，比大小找到中间那个当中位数。
#三向切分，对于有大量重复元素的时候可以使用三向切分，小于，等于，大于。
private void sort(T[] nums, int l, int h) {
if(h<=l){
return;
}
int lt=l,i=l+1,gt=h+1;
T v=nums[l];
while(i<=gt){
int cmp=nums[i].compareTo(v);
if(cmp<0){
swap(nums,++i,lt++);
}else if(cmp>0){
swap(nums,--gt,i);
}else{
i++;
}
}
sort(nums,l,lt-1);
sort(nums,gt+1,h);
}
##扩展，利用快排，选出第k个数。
public T select(T[] nums,int k){
int i=0;
int h=nums.length-1;
while(h>i){
int j=patition(nums,i,h);
if(j==k){
return nums[k];
}else if(j>k){
h=j-1;
}else{
i=j+1;
}
}
return nums[k];
}
private int patition(T[] nums, int l, int h) {
int i=l;
int j=h+1;
T v=nums[l];
while(true){
while(less(nums[++i],v)&&i!=h);
while(less(v,nums[--j])&&j!=l);
if(i>=j){
break;
}
swap(nums,i,j);
}
swap(nums,l,j);
return j;
}
##堆排序
/**
* 堆排序：堆中的节点总是大于等于子节点，堆是完全二叉树，因此如果节点k，k的子节点分别是2k+1,2k+2,(0是下标的时候)
*/
import Sort.Sort;
class Heap <T extends Comparable<T>> extends Sort<T> {
public T[] heap;
public int N=0;
public Heap(int maxN){
this.heap=(T[]) new Comparable[maxN+1];
}
public boolean isEmpty(){
return N==0;
}
public int size(){
return N;
}
public boolean less(int i,int j){
return heap[i].compareTo(heap[j])<0;
}
private void swap(int i,int j){
T t=heap[i];
heap[i]=heap[j];
heap[j]=t;
}
//上浮
public void swim(int k){
while(k>1&&less(k/2,k)){
swap(k/2,k);
k=k/2;
}
}
//下沉
public void sink(int k){
while(2*k<=N){
int j=2*k;
if(j<N&&less(j,j+1)){
j++;
}
if(!less(k,j)){
break;
}
swap(k,j);
k=j;
}
}
public void insert(Comparable v){
heap[++N]= (T) v;
swim(N);
}
public T delMax(){
T max=heap[1];
swap(1,N--);
heap[N+1]=null;
sink(1);
return max;
}
//堆排序，无序数组也可以从头到尾上浮，从尾到头下沉。从尾到头，速度比较快因为这样在双方子节点有序，就会遍历一半即可
@Override
public void sort(T[] nums) {
N=nums.length-1;
for(int i=N/2;i>=0;i--){
sink(i);
}
while(N>1){
swap(1,N--);
sink(1);
}
}
}
###分析
一个堆的高度是log(n),所以插入删除复杂度是log(n)，堆排序是对N个上浮下沉是n*log(n)、
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
##########总结
稳定性：是否改变原来数组中元素的相对位置。
冒泡排序，插入排序，归并排序。
算法 稳定性 时间复杂度 空间复杂度 备注
选择排序 × N2 1
冒泡排序 √ N2 1
插入排序 √ N ~ N2 1 时间复杂度和初始顺序有关
希尔排序 × N 的若干倍乘于递增序列的长度 1 改进版插入排序
快速排序 × NlogN logN
三向切分快速排序 × N ~ NlogN logN 适用于有大量重复主键
归并排序 √ NlogN N
堆排序 × NlogN 1 无法利用局部性原理
###快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
###java的排序算法实现
java主要的排序方法是java.util.Arrays.sort
对于原始数据类型使用三向切分快排
对于引用类型使用归并排序
网易公司福利 153人发布
