冒泡排序
以升序來講鄙币，我們需要把最小的一個數(shù)通過換位置的方式調(diào)到最第一個，那么第二小的數(shù)調(diào)到第二個位置剩拢。每次我們都從最后的一個數(shù)arr.lenth - 1進行相鄰比較大小糯俗，小的往前調(diào)，調(diào)動至位置i, i從0開始
//排序的時間復(fù)雜度n*n 個人覺得(n-1)!更為精確
public static void orderByBubble(int a[]) {
//先把前面的數(shù)排好.
for(int i = 0 ; i < a.length - 1 ; i++) {
//從最后一個數(shù)開始往前冒泡.
for(int j = a.length - 1 ; j > i; j--) {
//每一輪調(diào)換最小的數(shù)到最前面》
if(a[j] < a[j-1]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
}
選擇排序
選擇排序比較簡單肄程，每次從第arr.lenth - i 個數(shù)中找到一個最大或者最小的數(shù)锣吼，并把該數(shù)放到第i個位置
/**
* 每次選擇一個最小的數(shù)放在對應(yīng)的i位置.
* 選擇排序.n*n
* @param a
*/
public static void orderBySelect(int a[]) {
//這個代表第幾個數(shù)需要排序.最后n - 1(最后一個)個數(shù)是不需要排序的，
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個數(shù)的序已經(jīng)排好.
}
}
直接插入排序
每次將一個無序的數(shù)a[i + 1]插入到一個有序的數(shù)組a[0] ~ a[i]之間蓝厌，并且對該數(shù)組排序.
/**
* 直接插入排序. n
* @param a
*/
public static void orderByDirectInsert(int a[]) {
for(int i = 1 ; i < a.length ; i++) {
// 在有序的數(shù)組里互換位置把己調(diào)整到合適的位置.
for(int j = i; j > 0 ; j--) {
//if(a[n] > a[n - 1] && a[n] < a[n + 1])達到這個條件我們才說OK.終止循環(huán).
//如果前面一個數(shù)要大玄叠，那么我們跟前面一個數(shù)換位置
if(a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
快速排序
快速排序，又名挖坑填數(shù)
/**
* 時間復(fù)雜度n*logn, 空間復(fù)雜度logn
* 快速排序》,這里就以a[0]為參照.任意數(shù)組中的元素為參照. 挖坑填數(shù).
* @param a
* @param l 初始值通常為0
* @param r 初始值通常為a.length 可以針對某個區(qū)間排序.
*/
public static void orderByQuick(int a[],int l,int r) {
if(a == null) {
throw new IllegalArgumentException("a[] == null exception");
}
if( l < r) {
//x只是個參考基數(shù).后面的動作中a[l]最終被放在a[i]上.
int i = l,j = r,x = a[l];
while(i < j) {
//這表示有一個數(shù)比x大了,退出循環(huán)的條件拓提，是找到一個比X小的數(shù).
while(i < j && a[j] >= x) {
j--;
}
將這個比x小的數(shù)放在左邊的位置
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);//排右邊.
}
}
堆排序
二叉樹
構(gòu)建最大堆读恃，調(diào)整最大堆，堆邏輯結(jié)構(gòu)表示為一個完全二叉樹代态，從最后一個非葉子節(jié)點開始構(gòu)建最大堆寺惫，將堆中的最大元素a[0] 和 最后一個元素互換位置，之后抹去已經(jīng)調(diào)整完成的最后一個元素蹦疑，剩余的元素繼續(xù)調(diào)整出最大堆西雀，以此循環(huán)，直至所有元素調(diào)整完畢. 完全二叉樹每個節(jié)點下標滿足公式n = i/2 - 1, n代表節(jié)點歉摧，i代表節(jié)點下面的左孩子. 所以二叉樹最后一個節(jié)點下標是lastNode = (a.lenth - 1)/2 - 1艇肴。
最大堆：即任何節(jié)點都比自己左右孩子節(jié)點大.由此根節(jié)點顯然最大.
/**
* 這個需要構(gòu)建最大堆.
*/
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++，那么下一輪循環(huán),將對該節(jié)點下的孩子進行調(diào)整
如果沒有發(fā)生i++,則要調(diào)整的是左孩子下的所有節(jié)點.
i++;
}
// 取出左右孩子中最大的孩子
if(a[i] > curPointValue) {
int temp = a[i];
a[i] = curPointValue;
a[begain] = temp;
}else //表示當(dāng)前節(jié)點自己就是最大的,不必重排了.
break;
begain = i;
}
}
/**
* 堆排序. 堆是具有某些特性的完全二叉樹.每個節(jié)點的值要么都大于等于或者小于等于其子節(jié)點.
* @param a
*/
public static void orderByHead(int a[]) {
//構(gòu)建最大堆
for(int i = (a.length - 1)/2 ; i >= 0 ; i--)
{
builMaxHeap(a, i, a.length);
}
//調(diào)整最大堆.
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);
}
}
