近期终于弄懂了六种算法，写个小博客记录下
一、六种算法解析：
1、直接插入排序：
（1）、算法思想：每次抽取一个数据，与前面排好的数据相比较，找到相应的位置插入，然后抽取下一个数据；
（2）、算法特点：保证每一次遍历后，前面的数据都是排序好的；
（2）、代码：
public static int[] Insert(int[] Arr){
int pos;
int temp;
for(int i=1;i<Arr.length;i++){
temp=Arr[i]; //待插入的数
pos=i-1; //待插入的位置
while(pos>=0&&(temp<Arr[pos])){
Arr[pos+1]=Arr[pos]; //将比较大的数往后移
pos--; //pos--即是让temp与前面的数继续比较大小
System.out.print(Arr[pos+1]+",");
}
Arr[pos+1]=temp;
System.out.print(Arr[pos+1]+"\n");
};
return Arr;
}
2、选择排序
（1）、算法思想：从第一个数开始，每次将这个数和后面最小的数比较，如果这个数比最小的数大，则交换位置；
（2）、算法特点：每一次循环遍历后，都能找到此时最小的数据排序好；
（3）、代码：
public static int[] selectSort1(int[] Arr){
int temp;
int pos;
for(int i=0;i<Arr.length-1;i++){
//将当前位置的数
temp=Arr[i];
pos=i;
//选出i后面最小的数，保存在temp中，最后当前位置的数Arr[i]与后面最小的数交换
for(int j=i+1;j<Arr.length;j++){
if(temp>Arr[j]){
temp=Arr[j];
pos=j;
}
}
Arr[pos]=Arr[i];
Arr[i]=temp;
}
return Arr;
}
3、冒泡排序：
（1）、算法思想：从后往前，相邻两个数比较大小，将小的数排在大数的前面；
（2）、算法特点：每一次遍历都能得到当前最小值；
（3）、代码：
public static int[] Bubble1(int[] Arr){
int temp;
for(int i=1;i<Arr.length;i++){
for(int j=Arr.length-1;j>=i;j--){
//相邻两个数据比较大小
if(Arr[j]<Arr[j-1]){
temp=Arr[j];
Arr[j]=Arr[j-1];
Arr[j-1]=temp;
}
}
}
return Arr;
}
4、交换排序：
（1）、算法思想：可以与前面的选择排序对比下，此时的交换排序是“将当前遍历的起始数字与后面的每一个数比较，一旦比后面数据大，则交换”
（2）、算法特点：每一次遍历，总能将当前循环最小数字找到；
（3）、代码：
public static int[] Exchange1(int[] Arr){
int temp;
for(int i=0;i<Arr.length-1;i++){
for(int j=i+1;j<Arr.length;j++){
//当前数据与其后面的数据逐一比较
if(Arr[j]<Arr[i]){
temp=Arr[i];
Arr[i]=Arr[j];
Arr[j]=temp;
}
}
}
return Arr;
}
5、快速排序：
（1）、算法思想：首先要确定一个关键字（例如取第一个数据），两个游标，一个游标i是指向该关键字的，另一个游标j指向最右边的数据；如果关键字比最右边的数大，则交换两个数据，关键字由游标j指向，并且i++；否则，j--，关键字的游标不变，直至i=j时，一次遍历结束；之后，以此关键字为界将左边的数据和右边的数据按照前面的方法分别取关键字遍历，直至排序完毕；
（2）、算法特点：每一次遍历都能将关键字放置正确的位置，并且关键字左边的数据都比关键字小，关键字右边的数据比关键字都要大；
（3）、代码：
public static int[] Quick(int[] Arr,int left,int right){
int i=left;
int j=right;
int temp;
int key=Arr[i];
do{
if(Arr[i]>Arr[j]){
temp=Arr[i];
Arr[i]=Arr[j];
Arr[j]=temp;
}
if(key==Arr[i]){
j--;
}else if(key==Arr[j]){
i++;
}
}while(i<j);
if(left<j){
Quick(Arr,left,j-1);
}
if(right>i){
Quick(Arr,i+1,right);
}
return Arr;
}
注：开始学习时，总是弄不清楚关键字与两个游标的关系，不清楚游标如何变化；
6、希尔排序：
（1）、算法思想：希尔排序是直接插入排序的改良版，设置一个d=n/2，每一次遍历时都有d/=2;然后将原先要排序的数列分成若干小组，在组内进行直接插入排序；
（2）、算法特点：每一遍历后，总能在组内排序好；
（3）、代码：
public static int[] Shell(int[] Arr){
int d=Arr.length;
int temp;
while(d>0){
d=d/2;
for(int i=0;i<d;i++){
for(int j=i;j+d<Arr.length;j+=d){
int k=j;
//在组内进行直接插入排序
while(k>=i&&Arr[k]>Arr[k+d]){
temp=Arr[k];
Arr[k]=Arr[k+d];
Arr[k+d]=temp;
k-=d;
}
}
}
}
注：刚开始写代码时，只是将原先的数列根据d值分了很多小组，然后每个组内相邻两个数据比较大小，如果前面的比后面的大，则交换，后面的数据再与更后面的数据比较大小，却没有使用到插入排序中的算法思想，交换后，原先后面的数据应该与更前面的数据继续比较大小，直至找到合适的位置存放好；
二、排序算法比较：
1、算法的时间复杂度：
（1）、冒泡排序：max：O(n2)；min：1；
（2）、选择排序：O(n2)；
（3）、插入排序：O(n2)；
（4）、快速排序：max：O(n2)；min：1；
（5）、堆排序：O(n2)；
（6）、归并排序：O(nlog2n)；
2、算法的稳定性：
（1）、稳定的算法有：插入排序、冒泡排序、二叉树排序、二路归并排序以及其他线性排序；
（2）、不稳定的算法有：选择排序、希尔排序、快速排序和堆排序，希尔排序；
3、根据不同的情况选择不同的算法：
（1）、当n比较小，且对稳定性不作要求时，应用选择排序；对稳定性有要求时，应选用插入排序或者冒泡排序；
（2）、当n比较大时，关键字元素比较随机，对稳定性没有要求的时候应用快速排序，希尔排序；
（3）、当n比较大时，关键字元素可能出现本身是有序的，且对稳定性有要求，空间允许的情况下，应使用归并排序；
（4）、当n比较大时，关键字可能本身有序，但对稳定性没有要求时，可使用堆排序；