冒泡排序
冒泡排序算法的運作如下：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個码秉。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對鸡号。這步做完后转砖，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟鲸伴，除了最后一個府蔗。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較汞窗。
時間復雜度O(n^2)姓赤，空間復雜度O(1)，穩(wěn)定排序：即相同的元素在排序后次序沒有改變
代碼實現(xiàn)：
static int[] bubbleSort(int[] arr) {
for (int i=0; i<arr.length; i++) { //0~N-1 次循環(huán)
//一輪比較后找到最大的元素仲吏，放到下標arr.length-1-i位置
for (int j=0; j<arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr, j+1, j); //交互元素
}
}
}
return arr;
}
助記碼
i∈[0,N-1)//循環(huán)N-1遍
j∈[0,N-1-i)//每遍循環(huán)要處理的無序部分
swap(j,j+1) //兩兩排序（升序/降序）
選擇排序
工作原理如下：首先在未排序序列中找到最小（大）元素不铆，存放到排序序列的起始位置，然后蜘矢，再從剩余未排序元素中繼續(xù)尋找最锌衲小（大）元素，然后放到已排序序列的末尾品腹。以此類推岖食，直到所有元素均排序完畢。
時間復雜度O(n^2)舞吭，空間復雜度O(1)泡垃，不穩(wěn)定的排序
代碼實現(xiàn)：
static int[] selectSort(int[] arr) {
for (int i=0; i<arr.length; i++) {
int min = i;
//找到i下標起始的序列中的最小元素
for (int j=i+1; j<arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
swap(arr, i, min);
}
return arr;
}
插入排序
工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)羡鸥，在已排序序列中從后向前掃描蔑穴，找到相應位置并插入。
一般來說惧浴，插入排序都采用in-place在數(shù)組上實現(xiàn)存和。具體算法描述如下：
- 從第一個元素開始，該元素可以認為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素捐腿，將該元素移到下一位置
- 重復步驟3纵朋，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
時間復雜度O(n^2)，空間復雜度O(1)茄袖，穩(wěn)定的排序
實現(xiàn)代碼：
static int[] insert(int[] arr) {
for (int i=1; i<arr.length; i++) {
int temp = arr[i], j=0;//保存當前待排序元素
for (j=i-1; j>=0 && arr[j] > temp; j--) {//從后往前遍歷
arr[j+1] = arr[j];//對數(shù)值大的操软，元素后移
}
arr[j+1] = temp;//將待排序元素插入到正確位置
}
return arr;
}
static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {//從下標1的元素開始，掃描到最后一個
int j = i;
while (j >= 1) { //將 i 處元素和它之前的元素比較宪祥，插入到合適的位置
if (arr[j] < arr[j-1]) {
swap(arr, j, j-1);
j--;
} else {
break;
}
}
}
}
希爾排序
希爾排序是插入排序的升級版聂薪，希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
1.插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高蝗羊，即可以達到線性排序的效率
2.但插入排序一般來說是低效的藏澳，因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步肘交。然后算法再取越來越小的步長進行排序笆载，算法的最后一步就是普通的插入排序扑馁，但是到了這步涯呻，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端腻要。如果用復雜度為O(n2)的排序（冒泡排序或插入排序）复罐，可能會進行n次的比較和交換才能將該數(shù)據(jù)移至正確位置。而希爾排序會用較大的步長移動數(shù)據(jù)雄家，所以小數(shù)據(jù)只需進行少數(shù)比較和交換即可到正確位置效诅。
即希爾排序通過調(diào)整插入步長來實現(xiàn)更快速高效的數(shù)據(jù)調(diào)整。
步長的選擇是希爾排序的重要部分趟济。只要最終步長為1任何步長序列都可以工作乱投。Donald Shell最初建議步長選擇為 n/2并且對步長取半直到步長達到1。已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)顷编，這項研究也表明“比較在希爾排序中是最主要的操作戚炫，而不是交換∠蔽常”用這樣步長序列的希爾排序比插入排序要快双肤，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢钮惠。
時間復雜度O(nlog^2n)茅糜，括號內(nèi)是n乘以logn的平方，空間復雜度O(1)素挽，不穩(wěn)定的排序
代碼實現(xiàn)：
static int[] shellInsert(int[] arr) {
int foot = arr.length / 2;//步長初始化
while (foot >= 1) {
for (int i=1; i<arr.length; i++) {
int temp = arr[i], j=0;
for (j=i-foot; j>=0 && arr[j] > temp; j=j-foot) {
arr[j+foot] = arr[j];
}
arr[j+foot] = temp;
}
foot /= 2;//調(diào)整步長
}
return arr;
}
快速排序
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）蔑赘。
步驟為：
- 從數(shù)列中挑出一個元素，稱為"基準"（pivot），
- 重新排序數(shù)列缩赛，所有比基準值小的元素擺放在基準前面锌历，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結(jié)束之后峦筒，該基準就處于數(shù)列的中間位置究西。這個稱為分區(qū)（partition）操作。
- 遞歸地（recursively）對小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序物喷。
遞歸到最底部時卤材，數(shù)列的大小是零或一，也就是已經(jīng)排序好了峦失。這個算法一定會結(jié)束扇丛，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去尉辑。
時間復雜度O(nlogn)帆精，，空間復雜度O(logn)隧魄，不穩(wěn)定的排序
原地（in-place）分區(qū)的版本代碼：
原地分區(qū)算法卓练，它分區(qū)了標示為"左邊（left）"和"右邊（right）"的序列部分，借由移動小于等于a[pivotIndex]的所有元素到子序列的開頭购啄，留下所有大于的元素接在他們后面襟企。在這個過程它也為基準元素找尋最后擺放的位置，也就是它回傳的值狮含。
static int partition(int[] arr, int left, int right) {
int pivot = left-1;//初始基準下標設定
//默認基準值為arr[right]
//這里可以先隨機選擇一個基準值顽悼，然后將其和arr[right]交換即可
for ( ;left <= right; left++) {
//注意等號比較重要，如果不加等號几迄，則需要在for循環(huán)結(jié)束后swap(arr, ++pivot, right);即將基準值放到正確的位置蔚龙。
if (arr[left] <= arr[right]) {
swap(arr, ++pivot, left);//將小于等于基準值的元素移動到序列開頭
}
}
return pivot;//返回調(diào)整后的基準值下標
}
快速排序算法：
static void quick(int[] arr, int left, int right) {
if (left >= right) return;//邊界檢查
int pivot = partition(arr, left, right);
quick(arr, left, pivot-1);
quick(arr, pivot+1, right);
}
歸并排序
該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行映胁。
歸并操作（merge）木羹，也叫歸并算法，指的是將兩個已經(jīng)排序的序列合并成一個序列的操作屿愚。歸并排序算法依賴歸并操作汇跨。
時間復雜度O(nlogn)，妆距，空間復雜度O(n)穷遂，穩(wěn)定的排序
迭代法
- 申請空間，使其大小為兩個已經(jīng)排序序列之和娱据，該空間用來存放合并后的序列
- 設定兩個指針蚪黑，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 比較兩個指針所指向的元素盅惜，選擇相對小的元素放入到合并空間，并移動指針到下一位置
- 重復步驟3直到某一指針到達序列尾
- 將另一序列剩下的所有元素直接復制到合并序列尾
歸并操作代碼：
static void mergeProcess(int[] arr, int left, int mid, int right) {
int[] temp = new int[right-left+1];//合并空間
int l = left;//左邊序列起始下標
int r = mid+1;//右邊序列起始下標
int id = 0;//合并空間起始下標
while (l <= mid && r <= right) {//合并
if (arr[l] < arr[r]) {//先放入小的
temp[id++] = arr[l++];
} else {
temp[id++] = arr[r++];
}
}
//合并剩余的序列
while (l <= mid) temp[id++] = arr[l++];
while (r <= right) temp[id++] = arr[r++];
//將排好的序列復制到原序列
for (int i=0; i<id; i++) {
arr[left+i] = temp[i];
}
}
遞歸歸并排序:
其實就是將序列先分割成一個個小的序列忌穿，然后再對小序列進行合并抒寂，同時在合并的過程中進行排序。
static void merge(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left+right) / 2;//找到分割點下標
merge(arr, left, mid);//分割左
merge(arr, mid+1, right);//分割右
mergeProcess(arr, left, mid, right);//合并
}
非遞歸法 ： 邊界條件不好控制掠剑，易出錯屈芜。
原理如下（假設序列共有n個元素）：
- 將序列每相鄰兩個數(shù)字進行歸并操作，形成 floor(n/2)個序列朴译，排序后每個序列包含兩個元素
- 將上述序列再次歸并井佑，形成floor(n/4)個序列，每個序列包含四個元素
- 重復步驟2眠寿，直到所有元素排序完畢
static void merge2(int[] arr) {
int step = 1;//序列合并的子序列起始長度為1
while (step <= arr.length) {
int i=0;
//將2個step長的序列合并為一個序列躬翁，長度加倍
for ( ; i+2*step-1<arr.length; i += 2*step) {
mergeP(arr, i, i+step-1, i+2*step-1);//合并2個子序列
}
//對長度不足2*step的序列尾進行合并，且最后一次整個序列的合并也由此完成
if (i+step-1 < arr.length) {
mergeP(arr, i, i+ step-1, arr.length-1);
}
step *= 2;
}
}
//寫法二
static void merge2(int[] arr) {
int before = 1;//合并前序列長
int after = 0;//合并后序列長度
while (before <= arr.length) {
after = before * 2;//將2個序列合并為一個序列盯拱，長度加倍
int i=0;
for ( ; i+after-1<arr.length; i += after) {
mergeProcess(arr, i, i+before-1, i+after-1);//合并2個子序列
}
//對長度不足after的序列尾進行合并盒发，且最后一次整個序列的合并也由此完成
if (i+before-1 < arr.length) {
mergeProcess(arr, i, i+ before-1, arr.length-1);
}
before = after;
}
}
堆排序
利用堆這種數(shù)據(jù)結(jié)構(gòu)所設計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)狡逢，并同時滿足堆的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點宁舰。
通常堆是通過一維數(shù)組來實現(xiàn)的。在數(shù)組起始位置為0的情形中：
父節(jié)點i的左子節(jié)點在位置(2i+1);
父節(jié)點i的右子節(jié)點在位置(2i+2);
子節(jié)點i的父節(jié)點在位置floor((i-1)/2);
在堆的數(shù)據(jù)結(jié)構(gòu)中甚侣，堆中的最大值總是位于根節(jié)點(在優(yōu)先隊列中使用堆的話堆中的最小值位于根節(jié)點)明吩。
堆中定義以下幾種操作：
最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點作調(diào)整间学，使得子節(jié)點永遠小于父節(jié)點
創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序
堆排序（HeapSort）：移除位在第一個數(shù)據(jù)的根節(jié)點殷费，并做最大堆調(diào)整的遞歸運算
堆排序的過程：
- 將數(shù)組調(diào)整為最大堆
- 將最大堆的根節(jié)點，即當前堆的最大值和數(shù)組未排序部分的最后一個值替換
- 重新調(diào)整最大堆低葫，最大堆的數(shù)組長度是無序數(shù)組的長度
- 重復2详羡，3步驟
//最大堆調(diào)整，id是待調(diào)整的元素下標嘿悬，len是待調(diào)整的數(shù)組長度
//一般調(diào)整時認為待調(diào)整節(jié)點以后的元素是符合最大堆的分布規(guī)律的
static void heapAdjust(int[] arr, int id, int len) {
while (id*2 + 1 < len) {
int child = id*2 + 1;//左孩子
if (child+1 < len && arr[child+1] > arr[child]) {
child++;//右孩子大于左孩子情況
}
if (arr[child] > arr[id]) {//右孩子大于父節(jié)點
swap(arr, id, child);//替換
id = child;//在新的節(jié)點上開啟下一輪比較
} else {
break;
}
}
}
static int[] heapSort(int[] arr) {
int n = arr.length;
for (int i= n/2; i>=0; i--) {//生成最大堆
heapAdjust(arr, i, n);
}
for (int i=n-1; i>0; i--) {//每次調(diào)整最大堆的數(shù)組長度
swap(arr, i, 0);//當前堆的最大值和數(shù)組未排序部分的最后一個值替換
heapAdjust(arr, 0, i);//調(diào)整最大堆
}
return arr;
}
