冒泡排序
以升序来讲，我们需要把最小的一个数通过换位置的方式调到最第一个，那么第二小的数调到第二个位置。每次我们都从最后的一个数arr.lenth - 1进行相邻比较大小，小的往前调，调动至位置i, i从0开始
//排序的时间复杂度n*n 个人觉得(n-1)!更为精确
public static void orderByBubble(int a[]) {
//先把前面的数排好.
for(int i = 0 ; i < a.length - 1 ; i++) {
//从最后一个数开始往前冒泡.
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;
}
}
}
}
选择排序
选择排序比较简单，每次从第arr.lenth - i 个数中找到一个最大或者最小的数，并把该数放到第i个位置
/**
* 每次选择一个最小的数放在对应的i位置.
* 选择排序.n*n
* @param a
*/
public static void orderBySelect(int a[]) {
//这个代表第几个数需要排序.最后n - 1(最后一个)个数是不需要排序的，
for(int i = 0 ; i < a.length - 1; i++) {
int min = a[i];
for(int j = i + 1 ; j < a.length ; j++ ) {
if(min > a[j]) {
min = a[j];
}
}
a[i] = min; //第i个数的序已经排好.
}
}
直接插入排序
每次将一个无序的数a[i + 1]插入到一个有序的数组a[0] ~ a[i]之间，并且对该数组排序.
/**
* 直接插入排序. n
* @param a
*/
public static void orderByDirectInsert(int a[]) {
for(int i = 1 ; i < a.length ; i++) {
// 在有序的数组里互换位置把己调整到合适的位置.
for(int j = i; j > 0 ; j--) {
//if(a[n] > a[n - 1] && a[n] < a[n + 1])达到这个条件我们才说OK.终止循环.
//如果前面一个数要大，那么我们跟前面一个数换位置
if(a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
快速排序
快速排序，又名挖坑填数
/**
* 时间复杂度n*logn, 空间复杂度logn
* 快速排序》,这里就以a[0]为参照.任意数组中的元素为参照. 挖坑填数.
* @param a
* @param l 初始值通常为0
* @param r 初始值通常为a.length 可以针对某个区间排序.
*/
public static void orderByQuick(int a[],int l,int r) {
if(a == null) {
throw new IllegalArgumentException("a[] == null exception");
}
if( l < r) {
//x只是个参考基数.后面的动作中a[l]最终被放在a[i]上.
int i = l,j = r,x = a[l];
while(i < j) {
//这表示有一个数比x大了,退出循环的条件，是找到一个比X小的数.
while(i < j && a[j] >= x) {
j--;
}
将这个比x小的数放在左边的位置
a[i++] = a[j];
while (i < j && a[i] < x ) {
i++;
};
a[j--] = a[i];
}
a[i] = x;
orderByQuick(a, l, i - 1);//排左边
orderByQuick(a, i+1, r);//排右边.
}
}
堆排序
二叉树
构建最大堆，调整最大堆，堆逻辑结构表示为一个完全二叉树，从最后一个非叶子节点开始构建最大堆，将堆中的最大元素a[0] 和 最后一个元素互换位置，之后抹去已经调整完成的最后一个元素，剩余的元素继续调整出最大堆，以此循环，直至所有元素调整完毕. 完全二叉树每个节点下标满足公式n = i/2 - 1, n代表节点，i代表节点下面的左孩子. 所以二叉树最后一个节点下标是lastNode = (a.lenth - 1)/2 - 1。
最大堆：即任何节点都比自己左右孩子节点大.由此根节点显然最大.
/**
* 这个需要构建最大堆.
*/
public static void builMaxHeap(int a[],int begain,int end) {
int curPointValue = a[begain];
int leftIndex = 2*begain + 1;
for(int i = leftIndex; i*2 + 1 < end ;)
{
//意思是右孩子大于左孩子.
if(i + 1 < end && a[i + 1] > a[i]) {
如果右孩子i++，那么下一轮循环,将对该节点下的孩子进行调整
如果没有发生i++,则要调整的是左孩子下的所有节点.
i++;
}
// 取出左右孩子中最大的孩子
if(a[i] > curPointValue) {
int temp = a[i];
a[i] = curPointValue;
a[begain] = temp;
}else //表示当前节点自己就是最大的,不必重排了.
break;
begain = i;
}
}
/**
* 堆排序. 堆是具有某些特性的完全二叉树.每个节点的值要么都大于等于或者小于等于其子节点.
* @param a
*/
public static void orderByHead(int a[]) {
//构建最大堆
for(int i = (a.length - 1)/2 ; i >= 0 ; i--)
{
builMaxHeap(a, i, a.length);
}
//调整最大堆.
for(int j = a.length; j > 0 ; j--) {
int temp = a[0];
a[0] = a[j - 1];
a[j-1] = temp;
builMaxHeap(a,0, j);
}
}
