冒泡排序
原理：一遍循环与旁边的比较找到最大（最小）放到后面，多趟排序之后就成为一个有序的队列。
冒泡排序示意图.png
//冒泡排序
public int[] bubbleSort(int[] array){
int size = array.length;
int temp ;
//排序趟数
for(int i = 0 ; i < size-1 ; i++){
//找到最大值，不断比较，交换位置
for(int j = 0 ; j < size-1-i ; j++)
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
return array;
}
冒泡循环中有嵌套两个for，所以时间复杂度是O(n^2)
快速排序
原理：在一堆数中取一个base值，一般第一个数为base值，第一个位置为LeftIndex，最后一个位置为RightIndex。然后从RightIndex向前比较，如果比base值小，就交换位置并从LeftIndex向后比较；如果比base值大就RightIndex--。当从LeftIndex开始向后比较base值，如果比base值大，就交换并又从RightIndex向前比较；否则LeftIndex++。当LeftIndex == RightIndex时，两边递归重复上面的操作。
快速排序示意图.png
代码实现
/**
* 1.取一个基准
* 2.从end-》start方向，比基准小的，交换end位置的数字和基准
* 3.从start-》end方向，比基准大的，交换start位置的数字和基准
* 4.当start==end后，分治递归两边
* */
public void quickSort(int[] array , int i , int j){
if(i >= j)
return;
int start = i;
int end = j;
int base = array[start];
boolean backOrForward = true;
while (start < end){
if(backOrForward){
if(array[end] < base){
array[start] = array[end];
array[end] = base;
backOrForward = false;
start++;
}else{
end--;
}
}else{
if(array[start] > base){
array[end] = array[start];
array[start] = base;
backOrForward = true;
end--;
}else{
start++;
}
}
}
Log.i(TAG, "quickSort: end = " + end + ",start = " + start);
int part = start;
quickSort(array,i,part-1);
quickSort(array,part+1,j);
}
快速排序平均时间复杂度O(n*log2n)
堆排序
原理：把数组想象成一个二叉树，从最后一个有叶儿节点的位置（length /2 - 1）开始，比较左孩子（2index+1）右孩子（2index+2），将大的放到节点，这样一遍循环下来就构成了一个最大堆，最后将第一个位置和最后一个位置交换，最大数就到最后一位。每次都形成最大堆，就成为有序的一个数组
构建二叉树.png
比较左右孩子.png
比较左右孩子.png
代码实现
/**
* start = 0 起始位置
* end为需要排序最后一个位置，及数组长度
**/
public void heapSort(int[] array,int start,int end){
int length = array.length;
int index , temp;
for(int i = 0 ; i < length ; i++ ){
index = (end+1) / 2 - 1;
for(int j = index ; j >=0 ; j-- ){
int left = 2 * j + 1;//左孩子
int right = 2 * j + 2;//右孩子
if(left <= end && array[left] > array[j]){
temp = array[j];
array[j] = array[left];
array[left] = temp;
}
if(right <= end && array[right] > array[j]){
temp = array[j];
array[j] = array[right];
array[right] = temp;
}
}
//完成最大堆，最大放到最后
temp = array[end];
array[end] = array[start];
array[start] = temp;
//需要排序的最堆数量减少一个
end--;
}
}
