冒泡排序
public class Bubble {
/*
1. 比較相鄰的元素。如果前一個元素比后一個元素大倡缠，就交換這兩個元素的位置哨免。
2. 對每一對相鄰元素做同樣的工作，從開始第一對元素到結(jié)尾的最后一對元素昙沦。最終最后位置的元素就是最大值琢唾。
*/
public static void sort1(Comparable[] arr){
for (int i = arr.length - 1; i > 0 ;i -- ){ //將較大的數(shù)向后移
for (int j = 0;j < i ;j ++ ){
if (arr[j].compareTo(arr[j+1])>0){
Comparable temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void sort2(Comparable[] arr){ //將較小的數(shù)向前移
for (int i = 0; i < arr.length - 1; i ++ ){
for (int j = arr.length - 1 ; j > i ; j --){
if(arr[j].compareTo(arr[j-1])<0){
Comparable temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
public static void sort3(Comparable[] arr){ // 改進版 帶flag
for(int i = 0; i < arr.length - 1; i ++){
boolean flag = false; //是否交換的標志
for (int j = arr.length - 1; j > i ; j--){
if(arr[j].compareTo(arr[j-1])<0){
Comparable temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
if(flag == false) //若無交換 說明已有序
return;
}
}
}
選擇排序
public class Select {
public static void sort(Comparable[] arr){
for (int i = 0; i < arr.length - 1 ; i ++){
int min = i; // 記錄最小值的下標
for(int j = i + 1; j < arr.length ; j ++){
if(arr[j].compareTo(arr[min])<0){
min = j;
} // 記錄當前最小值
}
if (min != i){ // 最小值不在第i位 則交換
Comparable t = arr[i];
arr[i] = arr [min];
arr[min] = t;
}
}
}
}
選擇排序的時間復雜度分析：
選擇排序使用了雙層for循環(huán)，其中外層循環(huán)完成了數(shù)據(jù)交換盾饮，內(nèi)層循環(huán)完成了數(shù)據(jù)比較采桃，所以我們分別統(tǒng)計數(shù)據(jù)交換次數(shù)和數(shù)據(jù)比較次數(shù)：
數(shù)據(jù)比較次數(shù)：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
數(shù)據(jù)交換次數(shù)：N-1
時間復雜度：N2/2-N/2+（N-1）=N2/2+N/2-1;
根據(jù)大O推導法則，保留最高階項丘损，去除常數(shù)因子普办，時間復雜度為O(N^2);
插入排序
排序原理：
1.把所有的元素分為兩組，已經(jīng)排序的和未排序的徘钥；
2.找到未排序的組中的第一個元素衔蹲，向已經(jīng)排序的組中進行插入；
3.倒敘遍歷已經(jīng)排序的元素呈础，依次和待插入的元素進行比較舆驶，直到找到一個元素小于等于待插入元素，那么就把待插入元素放到這個位置猪落，其他的元素向后移動一位贞远；
public class Insert {
public static void sort(Comparable[] arr){
for (int i = 1; i < arr.length ; i ++ ){
// 當前元素為arr[i] 依次和前面的元素比較 找到一個小于等于arr[i]的元素
for (int j = i; j > 0 ; j -- ){ // 有序表中 從后往前查找
if(arr[j-1].compareTo(arr[j])>0){ // 在前面的有序表中找到合適的位置插入
Comparable t = arr[j];
arr[j] = arr [j-1];
arr[j-1] = t;
}
}
}
}
}
插入排序的時間復雜度分析
插入排序使用了雙層for循環(huán)，其中內(nèi)層循環(huán)的循環(huán)體是真正完成排序的代碼笨忌，所以蓝仲，我們分析插入排序的時間復雜度，主要分析一下內(nèi)層循環(huán)體的執(zhí)行次數(shù)即可官疲。
最壞情況袱结，也就是待排序的數(shù)組元素為{12,10,6,5,4,3,2,1}，那么：
比較的次數(shù)為：
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交換的次數(shù)為：
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
總執(zhí)行次數(shù)為：
(N2/2-N/2)+(N2/2-N/2)=N^2-N;
按照大O推導法則途凫，保留函數(shù)中的最高階項那么最終插入排序的時間復雜度為O(N^2).
希爾排序
排序原理：
1.選定一個增長量h垢夹，按照增長量h作為數(shù)據(jù)分組的依據(jù)，對數(shù)據(jù)進行分組维费；
2.對分好組的每一組數(shù)據(jù)完成插入排序果元；
3.減小增長量促王，最小減為1，重復第二步操作而晒。
增長量 h的確定：增長量h的值每一固定的規(guī)則蝇狼，我們這里采用以下規(guī)則：
int h=1
while(h<5){
h=2h+1；//3,7
}
//循環(huán)結(jié)束后我們就可以確定h的最大值倡怎；
//h的減小規(guī)則為：
h=h/2
public class Shell {
public static void sort(Comparable[] arr){
int N = arr.length; // 增量h的最大值 增量遞增
int h = 1;
while (h < N / 2 ){
h = h * 2 + 1;
}
// 當增量h小于1 排序結(jié)束
while (h >= 1){
// 找到待插入的元素arr[i]
// 把 arr[i]插入到arr[i-2h] arr[i - 3h] ... 序列中
for (int i = h ; i < N ; i ++){
//arr[j] 就是待插入元素 依次和arr[j-h] arr[j-2h] .. 比較 若 arr[j]小 那么交換位置 反之 arr[j]大 則插入完成
for(int j = i ; j >= h ; j-=h ){
if(arr[j-h].compareTo(arr[j])>0){
Comparable t = arr[j];
arr[j] = arr [j-h];
arr[j-h] = t;
}else{
break;
}
}
}
h /= 2;
}
}
}
歸并排序
排序原理：
1.盡可能的一組數(shù)據(jù)拆分成兩個元素相等的子組迅耘，并對每一個子組繼續(xù)拆分，直到拆分后的每個子組的元素個數(shù)是1為止监署。
2.將相鄰的兩個子組進行合并成一個有序的大組颤专；(有序表的合并)
3.不斷的重復步驟2，直到最終只有一個組為止钠乏。
public class Merge {
private static Comparable[] assist; //輔助數(shù)組
public static void sort(Comparable[] arr){
assist = new Comparable[arr.length];
int low = 0;
int high = arr.length - 1;
sort(arr,low,high);
}
// low 到 high 的元素進行排序
private static void sort(Comparable[] arr, int low, int high){
if(high <= low) return;
int mid = low + (high - low) / 2;
// 對 low 到 mid 之間的元素進行排序
sort(arr, low, mid);
// 對 mid+1 到 high 之間的元素進行排序
sort(arr,mid+1,high);
// 對 low - mid , mid - high 這組數(shù)據(jù)進行歸并
merge(arr, low, mid, high);
}
// 對數(shù)組中 low - mid 為一組 mid+1 - high 為一組 對兩組數(shù)組進行歸并
private static void merge(Comparable[] arr, int low, int mid, int high){
// low 到 mid 這組數(shù)據(jù)和 mid+1 到 high 這組數(shù)據(jù)歸并到輔助數(shù)組assist對應(yīng)的索引處
int i = low; //定義一個指針栖秕，指向assist數(shù)組中開始填充數(shù)據(jù)的索引
int p1 = low; //定義一個指針，指向第一組數(shù)據(jù)的第一個元素
int p2 = mid + 1; //定義一個指針缓熟，指向第二組數(shù)據(jù)的第一個元素
//比較左邊小組和右邊小組中的元素大小累魔，哪個小摔笤，就把哪個數(shù)據(jù)填充到assist數(shù)組中
while (p1 <= mid && p2 <= high) {
if (arr[p1].compareTo(arr[p2])<0) {
assist[i++] = arr[p1++];
} else {
assist[i++] = arr[p2++];
}
}
//上面的循環(huán)結(jié)束后够滑，如果退出循環(huán)的條件是p1<=mid，則證明左邊小組中的數(shù)據(jù)已經(jīng)歸并完畢吕世，如果退出循環(huán)的條件是p2<=high,則證明右邊小組的數(shù)據(jù)已經(jīng)填充完畢彰触；
//所以需要把未填充完畢的數(shù)據(jù)繼續(xù)填充到assist中
// 下面兩個循環(huán)，只會執(zhí)行其中的一個
while(p1<=mid){
assist[i++]=arr[p1++];
}
while(p2<=high){
assist[i++]=arr[p2++];
}
//到現(xiàn)在為止命辖，assist數(shù)組中况毅，從low到high的元素是有序的，再把數(shù)據(jù)拷貝到a數(shù)組中對應(yīng)的索引處
for (int index=low;index<=high;index++){
arr[index]=assist[index];
}
}
}
假設(shè)元素的個數(shù)為n尔艇，那么使用歸并排序拆分的次數(shù)為log2(n),所以共log2(n)層尔许，那么使用log2(n)替換上面32^3中的3這個層數(shù)，最終得出的歸并排序的時間復雜度為：log2(n) 2^(log2(n))=log2(n)*n,根據(jù)大O推導法則终娃，忽略底數(shù)味廊，最終歸并排序的時間復雜度為O(nlogn);
歸并排序的缺點：
需要申請額外的數(shù)組空間，導致空間復雜度提升棠耕，是典型的以空間換時間的操作余佛。
快速排序
排序原理：
1.首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分窍荧；
2.將大于或等于分界值的數(shù)據(jù)放到到數(shù)組右邊辉巡，小于分界值的數(shù)據(jù)放到數(shù)組的左邊。此時左邊部分中各元素都小于或等于分界值蕊退，而右邊部分中各元素都大于或等于分界值郊楣；
3.然后憔恳，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)净蚤，又可以取一個分界值喇嘱，將該部分數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值塞栅，右邊放置較大值者铜。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
4.重復上述過程放椰，可以看出作烟，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后砾医，再遞歸排好右側(cè)部分的順序拿撩。當左側(cè)和右側(cè)兩個部分的數(shù)據(jù)排完序后，整個數(shù)組的排序也就完成了如蚜。
切分原理：
把一個數(shù)組切分成兩個子數(shù)組的基本思想：
1.找一個基準值压恒，用兩個指針分別指向數(shù)組的頭部和尾部；
2.先從尾部向頭部開始搜索一個比基準值小的元素错邦，搜索到即停止探赫，并記錄指針的位置；
3.再從頭部向尾部開始搜索一個比基準值大的元素撬呢，搜索到即停止伦吠，并記錄指針的位置；
4.交換當前左邊指針位置和右邊指針位置的元素魂拦；
5.重復2,3,4步驟毛仪，直到左邊指針的值大于右邊指針的值停止。
public class Quick {
public static void sort(Comparable[] a){
int low = 0;
int high = a.length - 1;
sort(a,low,high);
}
private static void sort(Comparable[] a,int low, int high){
if(high<=low) return;
// low - high 進行劃分
int partition = partition(a, low , high);
sort(a,low,partition-1);
sort(a,partition+1,high);
}
private static int partition(Comparable[] a, int low, int high){
Comparable pivot = a[low];
while (low < high){
while(low < high && a[high].compareTo(pivot)>0 ) --high;
a[low] = a [high];
while (low < high && a[low].compareTo(pivot)<0 ) ++ low;
a[high] = a[low];
}
a[low] = pivot; // 樞軸元素放到最終位置
return low;// 存放樞軸的位置
}
}
快速排序時間復雜度分析：
快速排序的一次切分從兩頭開始交替搜索芯勘，直到left和right重合箱靴，因此，一次切分算法的時間復雜度為O(n),但整個快速排序的時間復雜度和切分的次數(shù)相關(guān)荷愕。
最優(yōu)情況：每一次切分選擇的基準數(shù)字剛好將當前序列等分衡怀。
如果我們把數(shù)組的切分看做是一個樹，那么上圖就是它的最優(yōu)情況的圖示路翻，共切分了 logn次狈癞，所以，最優(yōu)情況下快速排序的時間復雜度為O(nlogn);
最壞情況：每一次切分選擇的基準數(shù)字是當前序列中最大數(shù)或者最小數(shù)茂契，這使得每次切分會有一個子組蝶桶，那么總共就得切分n次，所以掉冶，最壞情況下真竖，快速排序的時間復雜度為O(n^2);
穩(wěn)定性
常見排序算法的穩(wěn)定性：
冒泡排序：
只有當arr[i]>arr[i+1]的時候脐雪，才會交換元素的位置，而相等的時候并不交換位置恢共，所以冒泡排序是一種穩(wěn)定排序算法战秋。
選擇排序:
選擇排序是給每個位置選擇當前元素最小的,例如有數(shù)據(jù){5(1)，8 讨韭，5(2)脂信， 2， 9 },第一遍選擇到的最小元素為2透硝，所以5(1)會和2進行交換位置狰闪，此時5(1)到了5(2)后面，破壞了穩(wěn)定性濒生，所以選擇排序是一種不穩(wěn)定的排序算法埋泵。
插入排序：
比較是從有序序列的末尾開始，也就是想要插入的元素和已經(jīng)有序的最大者開始比起罪治，如果比它大則直接插入在其后面丽声，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的觉义，那么把要插入的元素放在相等元素的后面雁社。所以，相等元素的前后順序沒有改變谁撼，從原無序序列出去的順序就是排好序后的順序歧胁，所以插入排序是穩(wěn)定的滋饲。
希爾排序：
希爾排序是按照不同步長對元素進行插入排序 ,雖然一次插入排序是穩(wěn)定的厉碟，不會改變相同元素的相對順序，但在不同的插入排序過程中屠缭，相同的元素可能在各自的插入排序中移動箍鼓，最后其穩(wěn)定性就會被打亂，所以希爾排序是不穩(wěn)定的呵曹。
歸并排序：
歸并排序在歸并的過程中款咖，只有arr[i]<arr[i+1]的時候才會交換位置，如果兩個元素相等則不會交換位置奄喂，所以它并不會破壞穩(wěn)定性铐殃，歸并排序是穩(wěn)定的。
快速排序：
快速排序需要一個基準值跨新，在基準值的右側(cè)找一個比基準值小的元素富腊，在基準值的左側(cè)找一個比基準值大的元素，然后交換這兩個元素域帐，此時會破壞穩(wěn)定性赘被，所以快速排序是一種不穩(wěn)定的算法是整。
