排序算法汇总
各类排序算法时间空间复杂度如下表所示：
1：直接选择排序：
排序思想：
选取当前最小（最大）的数据放置在当前状态下的最前面的位置，一直轮循，直到所有序列都有序为止：
代码实现：
public void sort(int a[]){
int length = a.length;
for(int i =0;i<length;i++){
int min = i;
for(int j =i+1;j<length;j++){
if(a[min]>a[j]){
min = j;
}
}
if(min !=i){
int temp = a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
}
示例：
[9,5,2,4,3]
i = 0;
根据内部循环，选取当前状态(i = 0)下最小的的值为2，此时下标j为3，将2放置在当前状态下的最前面a[i]处
该循环后序列为：
[2,5,9,4,3]
再进一步循环，直到i = 5,循环终止，序列有序
时间复杂度分析：
改排序需要经过两重循环，假定有n个元素，则其需要经历n*n次循环才能结束，所以其时间复杂度为O(n^2)
空间复杂度分析：
该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)
2：插入排序
排序思想：
将整个待排序的序列分成两个部分，前半部分是有序的序列，后半部分为无需部分，然后将后半部分的元素依次添加到前半部分的有序序列中，前半部分为有序序列，因此只需要将后半部分取出来的数据插入到合适的位置即可，直到后半部分为空；
代码实现：
public void sort(int target[]){
int length = target.length;
for(int i=1;i<length;i++){
for(int j = i;j>0;j--){
if(target[j]>target[j-1]) {
int temp = target[j];
target[j]=target[j-1];
target[j-1]=temp;
}else{
break;
}
}
}
}
示例：
[1,4,2,5,3]
将数据分成两个序列[1] 和 [4,2,5,3]
将4 加入到前半部分中,此时序列为[1,4] 和 [2,5,3]
将2 加入到前半部分中,此时序列为[1,2，4] 和 [5,3]
直到最后序列有序
时间复杂度分析：
该算法基础步骤执行的次数为：(1+n)*n/2,其数量级在n2,因此其时间复杂度为O(n2)
最好情况为整个序列有序，每次只需移动后半部分的一个元素到前半部分，移动次数为n，故为O(n)
空间复杂度分析：
该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)
3:希尔排序
排序思想：
希尔排序(Shell)是插入排序的升级版，假设一个序列是倒叙的，现在要求对这个数列正序排列，在数组基数较大的情况下，将最后的元素移动到最前面需要经历n-1次的比较，比较次数较多，元素移动较多，排序效率自然低下，希尔排序，是在这样的情况下产生的，其实想思想是先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高，这样元素移动跨度较大，效率也自然的得到提升；
希尔排序的步长可以自定义，下面，我选用步长为3
代码实现：
public void sort(int target[]){
int length = target.length;
int h = 1;
while(h<length/3) h = 3*h+1;（步长）
while(h >=1){
for(int i = h;i<length;i++){
for(int j = i;j>=h;j-=h){
if(target[j]<target[j-h]){
int temp = target[j];
target[j]=target[j-h];
target[j-h] = temp;
}
}
}
h=h/3;
}
}
时间复杂度分析：
希尔排序的时间复杂度与选择的步长度有关
空间复杂度：
该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)
