排序算法
-------1. 插入排序
-----------直接插入排序
-----------希尔插入排序
-------2. 交换排序
-----------冒泡排序
-----------快速排序
-------3. 选择排序
-----------直接选择排序
-----------堆排序
-------4. 归并排序
-------5. 基数数排序
一般企业会让你说出几种排序算法，而且要求你用一种排序算法给一个数组排序，查看你的变成和代码编写的熟练程度。
下面我将给大家介绍四种常见而且常考的排序算法：
1. 直接插入排序
------算法思想：------------------------
2.要处理的数据A和前面的数据依次比较(从前向后)，如果该数据比前面数据小，
* 将该点作为插入点，备份数据A，
* 将插入点之后处理数据A之前的数据整体向后移动覆盖A的位置，
* 然后将备份数据插入到插入点的位置
3.取下一个待处理数据，执行步骤2
4.循环步骤3直到，需要处理的数据为0
------代码实现：------------------------
public void straightInsertionSort(double[] sorted){
//获取待排序数组的长度
int sortedLen = sorted.length;
//从第二个数据开始处理，下标为1
for(int i=1;i<sortedLen;i++){
//j表示待处理数据前面的数据的下标，j的首位置为0
for(int j=0;j<=i-1;j++){
//如果发现处理数据比前面的数据小，则将，此时的 j 作为插入点
// i 为处理元素位置
//如果想要从大到小排序只需要将if语句中的<变成>即可
if(sorted[i]<sorted[j]){
//备份处理元素
double back = sorted[i];
//将插入点之后的元素依次向后移动覆盖处理元素位置
for(int k=i;k>j;k--){
sorted[k]=sorted[k-1];
}
//将处理元素插入到插入点位置
sorted[j]=back;
//第一趟排序完成退出内层循环
break;
}
}
}
}
－－2. 冒泡排序
冒泡排序对部分以排序的数据进行排序操作，速度可以很快，但是对于一点顺序都没有的数据，排序效率将会非常差。
------算法思想：--------------------
冒泡排序即可以从前向后扫描也可以从后向前扫描，这里以从后向前
扫描为例。
从后向前扫描数据清单，将出现乱序的相邻的两个数据交换位置，继续向前扫描。
这样如果是从大到小的冒泡排序排序，扫描一遍之后，最大的数据将出现在数据清单的首位，
再扫描一遍第二大的数据将出现在第二号位置，一直重复扫描操作，直到全部数据有序
------代码实现：------------------------
public void bubbleSort(double[] sorted){
//获取数据的长度
int sortedLen=sorted.length;
// i 代表扫描次数
for(int i=1;i<=sortedLen;i++){
//定义一个有序标志
boolean flag=true;
//从后向前扫描，所以 j 的其实位置为sortedLen-1
//每扫描一次将出现一个最大元素排在前面并有序，所一下一次扫描的长度将减少一个
//即扫描的结束位置的下标为 i-1
for(int j=sortedLen-1;j>i-1;j--){
//如果发现后面元素比相邻的前面的元素大，就交换位置
if(sorted[j]>sorted[j-1]){
sorted[j] = sorted[j]+sorted[j-1];
sorted[j-1] = sorted[j]-sorted[j-1];
sorted[j] = sorted[j] - sorted[j-1];
//如果有数据交换说明，排序数据不是有序的
flag= false;
}
}
//如果标志没有改变，说明排序数据是有序的，无需排序了，直接退出
if(flag){
return;
}
}
}
－－3. 快速排序：
------算法思想-------------
快速排序也为交换排序的一种，它的算法思想是
1. 在排序数据中选择一个值指定为pivotKey，将大于pivotKey的数据方到右边，
将小于pivotKey的数据放到左边，
2. 取pivotKey左边的数据递归执行1，取pivotKey右边的数据递归执行1
------代码实现：------------------------
public void quickSort(double[] sorted,int low,int high){
//low和high相等说明，此时待排序数据为一个元素，无需排序
if(low<high){
//每调用一次getMiddle()方法就进行一次快速排序
//中间值middle为pivotKey所在的位置的下标，他的左边为
//小于它的数，右边为大于他的数
int middle = getMiddle(sorted,low,high);
//对左边的数进行相同规则的递归算法
quickSort(sorted,low,middle-1);
//对右边的数进行相同规则的递归算法
quickSort(sorted,middle+1,high);
}
}
/**
* 作一趟快速排序让左边的数都小于指定值pivotKey，右边的数都大于指定值
* low指示待排序数据的起使下标，high指示待排序数据的的结束下标
* @param sorted
* @param low
* @param high
* @return
*/
private int getMiddle(double[] sorted, int low, int high) {
//将排序数据的第一个值作为中心值
double pivotKey=sorted[low];
//首先判断low<high说明可以进行排序操作
while(low<high){
//如果low小于high且高值大于中心值，说明不需要交换，high--
//如果一路顺利的执行下去，low并将等于high跳出循环，如果发现有一个值
//小于中心值，将跳出循环，将高值赋值到中心值的位置，
//当前high指向位置将成为无用信息
while(low<high && sorted[high]>=pivotKey){
high--;
}
sorted[low]=sorted[high];
//低值发现，自己比中心值大，将赋值到高值无用信息的位置上
//然而此时当前low指向的位置上的数据将成为无用信息
while(low<high && sorted[low]<=pivotKey){
low++;
}
sorted[high]=sorted[low];
//循环以上步骤，直到low等于high
}
//low等于high时，跳出循环，此时low和high共同指向的位置为，中心值的位置
sorted[low]=pivotKey;
return low;
}
－－选择排序：
-------算法思想：-----------
第 i 次选取 i 到array.length-1中间最小的值放在 i 的位置
------代码实现：------------------------
public void straightSelectSort(double[] sorted){
int sortedLen=sorted.length;
// i 为比较的次数, 长度为sortedLen的数据需要比较sortedLen-1次
for(int i=0;i<sortedLen-1;i++){
//记录最小值的位置
int pointer = 0;
//临时变量用于和其他数据比较寻找最小值
double temp = sorted[i];
//第 i 次比较时，i 处的元素要和 i 之后的所有元素比较，所以j的初值为i+1
for(int j=i+1;j<sortedLen;j++){
if(temp>sorted[j]){
temp=sorted[j];
pointer=j;
}
}
//交换数据
sorted[pointer]=sorted[i];
sorted[i] = temp;
}
}
以上四种算法是我们必须掌握的，大多数企业特别的喜欢考，希望大家好好学习，也不要浪费了我这么长时间的辛苦总结，希望大家都能找到一份称心的工作！
