基于比较的内排序——温故而知新
引言
排序和检索是数据数据的两个关键部分，排序是想尽快有序组织数据，检索则是想尽快查找数据。
最近发现对这个知识点里的部分内容生疏，所以特此做个总结。
环境
IDE：Eclipse
语言：Java
排序分类
排序算法在实现方法上被分为两个大类，我们今天讲的是基于比较的排序算法，非比较算法我们稍后再谈。
几大排序概览
一、性能
| 名称 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | O() | O(1) | 不稳定 |
| 冒泡排序 | O() | O(1) | 稳定 |
| 插入排序 | O() | O(1) | 稳定 |
| shell排序 | O() | O(1) | 不稳定 |
| 堆排序 | O(nlgn) | O(1) | 不稳定 |
| 归并排序 | O(nlgn) | O(n) | 稳定 |
| 快速排序 | O(nlgn) | O(lgn) | 不稳定 |
二、具体介绍
A、选择排序
简介：每次选择最大或者最小的元素放到指定位置。
每次交换必然导致元素顺序的变换，所以是不稳定的。
public int[] selectSort(int[] a) {
int len=a.length;
for(int i=0;i<len;i++) {
for(int j=i+1;j<len;j++) {
if(a[j]>a[i]) {
int tmp=a[j];
a[j]=a[i];
a[i]=tmp;
}
}
}
return a;
} in：
int a[]= {3,4,5,1,8,4,9,2};
out：
9 8 5 4 4 3 2 1
B、冒泡排序
简介：从指定位置开始，每次比较相邻元素，按照排序规则不断交换元素位置，在动态上看起来就像是一个不断往上冒得泡。
一个元素在冒泡过程中，不会改变其余元素的相对位置，因为他是一个个进行比较和位置交换的，不想选择排序跨位置交换，所以冒泡排序是稳定的。
public void bubbleSort(int []a) {
for(int i=0;i<a.length;i++) {
boolean flag=false;
for(int j=a.length-1;j>i;j--) {
if(a[j]>a[j-1]) {
int temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
flag=true;
}
}
// 如果该轮没有交换说明数组已经有序，直接退出；
if(!flag) break;
}
} in:
int a[]= {4,5,1,8,4,9,2};
out:
9 8 5 4 4 2 1
C、插入排序
简介：维护两个数组，一个有序，另一个无序，每次从无序数组中取一个元素，在有序数组中按固定顺序比较找到位置插入即可。麻烦点在于后面元素的挪动。
同样，插入一个元素不会改变元素的相对位置，所以也是稳定的。
//个人改进版，边找位置边挪，不用先找到位置再挪。
public void insertSort(int[] a) {
for(int i=1;i<a.length;i++) {
int flag=i-1;int num=a[i];
//不断往前比较，如果前面的数比他大，该数往后挪。
while(flag>=0 && a[flag]>num) {
a[flag+1]=a[flag];
flag--;
}
a[flag+1]=num;
}
} in:
int a[]= {8,5,1,4,9,2};
out:
1 2 4 5 8 9
D、归并排序
简介：两个有序数组如何合并成一个有序数组？假设两个数组都是从小到大排序，我们只要不断比较两个元素的头元素，把较小的元素拿出来接在新开的数组里面就可以了。采用递归的方式实现。
合并时，相同元素排放规则是固定的，所以归并排序也是稳定排序。
因为需要一个数组b来做中转，所以空间代价为O(n).
public void mergeSort(int start,int end,int[] a,int []b) {
if(start==end) return ;
int mid=(start+end)/2;
//递归分解
mergeSort(start,mid,a,b);
mergeSort(mid+1,end,a,b);
for(int i=start;i<=end;i++) {
b[i]=a[i];
}
int i1=start,i2=mid+1;
//合并数组
for(int j=start;j<=end;j++){
if(i1 == mid+1)
a[j]=b[i2++];
else if(i2 > end)
a[j]=b[i1++];
else if(b[i1]<b[i2])
a[j]=b[i1++];
else
a[j]=b[i2++];
}
return ;
} in:
int a[]= {8,5,1,4,9,2};
out:
1 2 4 5 8 9
E、快速排序
简介：寻找一个轴值，通过交换把数组分为两部分，轴值左边的都比它小(大),轴值右边的都比它大(小)；
因为涉及到轴值的多次交换，所以这个算法是不稳定的。
因为使用了递归，而且我们是把中间值作为轴值，所以空间复杂度为O(logn)。
//交换数组元素
public void swap(int[] a,int i,int j) {
if(i==j) return ;
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
//不断交换，并且返回轴值的最终位置。
public int part(int a[],int l,int r,int pivot) {
do{
while(a[++l]<pivot);
while(l<r && pivot<a[--r]);
swap(a,l,r);
}while(l<r);
return l;
}
//递归实现整体排序
public void quickSort(int[] a,int i,int j) {
if(j<=i) return ;
int pivot=(i+j)/2;
swap(a,pivot,j);
int k=part(a,i-1,j,a[j]);
swap(a,k,j);
quickSort(a,i,k-1);
quickSort(a,k+1,j);
} in：
int a[]= {8,5,1,4,9,2};
out：
1 2 4 5 8 9
F、堆排序
简介：了解最大(小)堆的性质，堆里的元素我们可以通过数组来存储。通过不断地堆的“下沉”操作，实现不断堆中寻找到最大(小)元素，这种本质和选择排序一样。
但由于堆是一种树结构存储，所以我们的时间代价降为了O(lgn)。
//堆类
class Heap{
private int[] heaparr;
private int maxsize;
private int n;
public Heap(int[] h,int num,int max ) {
heaparr=h;
n=num;
maxsize=max;
}
public void swap(int[] a,int i,int j) {
if(i==j) return ;
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
private void siftDown(int pos) {
while(!isLeaf(pos)) {
int j=leftChild(pos);int rc=rightChild(pos);
if(rc<n && heaparr[rc]>heaparr[j])
j=rc;
if(heaparr[pos]>heaparr[j]) return ;
swap(heaparr,pos,j);
pos=j;
}
}
public void removeFirst() {
if(n>0) {
swap(heaparr,0,--n);
if(n!=0) siftDown(0);
}
}
public int leftChild(int pos) {
return 2*pos+1;
}
public int rightChild(int pos) {
return 2*pos+2;
}
public boolean isLeaf(int pos) {
return (pos>=n/2 && pos<n);
}
public void heapsort() {
for(int i=0;i<n;i++) {
removeFirst();
}
}
} in:
int a[]= {8,5,1,4,9,2};
out:
1 2 4 9 5 8
G、希尔排序
简介：希尔排序本质上也是插入排序，只是对插入排序做了一定的优化。因为插入排序在数组较为有序的代价是线性的，所以整体思路是将整个数组局部有序化，关于具体的复杂度迄今没有具体论证，我们不加论证的给出代价为O()
private void shellSort(int[] a) {
for (int r = a.length / 2; r >= 1; r /= 2) {
for (int i = r; i < a.length; i += r) {
int temp = a[i];
int j = i - r;
while (j >= 0 && temp < a[j]) {
a[j + r] = a[j];
j -= r;
}
a[j + r] = temp;
}
}
} in:
int a[]= {8,5,1,4,9,2};
out:
1 2 4 5 8 9
总结
排序是重要的基础知识，很多地方排序也要注意到稳定性、时间代价、空间代价问题，所以我们应该要熟记几种排序的特征。我们也注意到效率高的代码在空间复杂度上存在着一定要求，可见时间复杂度和空间复杂度这两个总是在互相制衡，而现在的倾向是时间往往比空间更重要，因为存储设备容量一直在不断扩大，高效率的算法更让人青睐。