冒泡排序
public class Bubble {
/*
1. 比較相鄰的元素。如果前一個(gè)元素比后一個(gè)元素大，就交換這兩個(gè)元素的位置。
2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)元素到結(jié)尾的最后一對(duì)元素。最終最后位置的元素就是最大值。
*/
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){ // 改進(jìn)版 帶flag
for(int i = 0; i < arr.length - 1; i ++){
boolean flag = false; //是否交換的標(biāo)志
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) //若無(wú)交換 說(shuō)明已有序
return;
}
}
}
選擇排序
public class Select {
public static void sort(Comparable[] arr){
for (int i = 0; i < arr.length - 1 ; i ++){
int min = i; // 記錄最小值的下標(biāo)
for(int j = i + 1; j < arr.length ; j ++){
if(arr[j].compareTo(arr[min])<0){
min = j;
} // 記錄當(dāng)前最小值
}
if (min != i){ // 最小值不在第i位 則交換
Comparable t = arr[i];
arr[i] = arr [min];
arr[min] = t;
}
}
}
}
選擇排序的時(shí)間復(fù)雜度分析：
選擇排序使用了雙層for循環(huán)，其中外層循環(huán)完成了數(shù)據(jù)交換，內(nèi)層循環(huán)完成了數(shù)據(jù)比較，所以我們分別統(tǒng)計(jì)數(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
時(shí)間復(fù)雜度：N2/2-N/2+（N-1）=N2/2+N/2-1;
根據(jù)大O推導(dǎo)法則，保留最高階項(xiàng)，去除常數(shù)因子，時(shí)間復(fù)雜度為O(N^2);
插入排序
排序原理：
1.把所有的元素分為兩組，已經(jīng)排序的和未排序的；
2.找到未排序的組中的第一個(gè)元素，向已經(jīng)排序的組中進(jìn)行插入；
3.倒敘遍歷已經(jīng)排序的元素，依次和待插入的元素進(jìn)行比較，直到找到一個(gè)元素小于等于待插入元素，那么就把待插入元素放到這個(gè)位置，其他的元素向后移動(dòng)一位；
public class Insert {
public static void sort(Comparable[] arr){
for (int i = 1; i < arr.length ; i ++ ){
// 當(dāng)前元素為arr[i] 依次和前面的元素比較 找到一個(gè)小于等于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;
}
}
}
}
}
插入排序的時(shí)間復(fù)雜度分析
插入排序使用了雙層for循環(huán)，其中內(nèi)層循環(huán)的循環(huán)體是真正完成排序的代碼，所以，我們分析插入排序的時(shí)間復(fù)雜度，主要分析一下內(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推導(dǎo)法則，保留函數(shù)中的最高階項(xiàng)那么最終插入排序的時(shí)間復(fù)雜度為O(N^2).
希爾排序
排序原理：
1.選定一個(gè)增長(zhǎng)量h，按照增長(zhǎng)量h作為數(shù)據(jù)分組的依據(jù)，對(duì)數(shù)據(jù)進(jìn)行分組；
2.對(duì)分好組的每一組數(shù)據(jù)完成插入排序；
3.減小增長(zhǎng)量，最小減為1，重復(fù)第二步操作。
增長(zhǎng)量 h的確定：增長(zhǎng)量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;
}
// 當(dāng)增量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ù)拆分成兩個(gè)元素相等的子組，并對(duì)每一個(gè)子組繼續(xù)拆分，直到拆分后的每個(gè)子組的元素個(gè)數(shù)是1為止。
2.將相鄰的兩個(gè)子組進(jìn)行合并成一個(gè)有序的大組；(有序表的合并)
3.不斷的重復(fù)步驟2，直到最終只有一個(gè)組為止。
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 的元素進(jìn)行排序
private static void sort(Comparable[] arr, int low, int high){
if(high <= low) return;
int mid = low + (high - low) / 2;
// 對(duì) low 到 mid 之間的元素進(jìn)行排序
sort(arr, low, mid);
// 對(duì) mid+1 到 high 之間的元素進(jìn)行排序
sort(arr,mid+1,high);
// 對(duì) low - mid , mid - high 這組數(shù)據(jù)進(jìn)行歸并
merge(arr, low, mid, high);
}
// 對(duì)數(shù)組中 low - mid 為一組 mid+1 - high 為一組 對(duì)兩組數(shù)組進(jìn)行歸并
private static void merge(Comparable[] arr, int low, int mid, int high){
// low 到 mid 這組數(shù)據(jù)和 mid+1 到 high 這組數(shù)據(jù)歸并到輔助數(shù)組assist對(duì)應(yīng)的索引處
int i = low; //定義一個(gè)指針，指向assist數(shù)組中開(kāi)始填充數(shù)據(jù)的索引
int p1 = low; //定義一個(gè)指針，指向第一組數(shù)據(jù)的第一個(gè)元素
int p2 = mid + 1; //定義一個(gè)指針，指向第二組數(shù)據(jù)的第一個(gè)元素
//比較左邊小組和右邊小組中的元素大小，哪個(gè)小，就把哪個(gè)數(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中
// 下面兩個(gè)循環(huán)，只會(huì)執(zhí)行其中的一個(gè)
while(p1<=mid){
assist[i++]=arr[p1++];
}
while(p2<=high){
assist[i++]=arr[p2++];
}
//到現(xiàn)在為止，assist數(shù)組中，從low到high的元素是有序的，再把數(shù)據(jù)拷貝到a數(shù)組中對(duì)應(yīng)的索引處
for (int index=low;index<=high;index++){
arr[index]=assist[index];
}
}
}
假設(shè)元素的個(gè)數(shù)為n，那么使用歸并排序拆分的次數(shù)為log2(n),所以共log2(n)層，那么使用log2(n)替換上面32^3中的3這個(gè)層數(shù)，最終得出的歸并排序的時(shí)間復(fù)雜度為：log2(n) 2^(log2(n))=log2(n)*n,根據(jù)大O推導(dǎo)法則，忽略底數(shù)，最終歸并排序的時(shí)間復(fù)雜度為O(nlogn);
歸并排序的缺點(diǎn)：
需要申請(qǐng)額外的數(shù)組空間，導(dǎo)致空間復(fù)雜度提升，是典型的以空間換時(shí)間的操作。
快速排序
排序原理：
1.首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分；
2.將大于或等于分界值的數(shù)據(jù)放到到數(shù)組右邊，小于分界值的數(shù)據(jù)放到數(shù)組的左邊。此時(shí)左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值；
3.然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類(lèi)似處理。
4.重復(fù)上述過(guò)程，可以看出，這是一個(gè)遞歸定義。通過(guò)遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左側(cè)和右側(cè)兩個(gè)部分的數(shù)據(jù)排完序后，整個(gè)數(shù)組的排序也就完成了。
切分原理：
把一個(gè)數(shù)組切分成兩個(gè)子數(shù)組的基本思想：
1.找一個(gè)基準(zhǔn)值，用兩個(gè)指針?lè)謩e指向數(shù)組的頭部和尾部；
2.先從尾部向頭部開(kāi)始搜索一個(gè)比基準(zhǔn)值小的元素，搜索到即停止，并記錄指針的位置；
3.再?gòu)念^部向尾部開(kāi)始搜索一個(gè)比基準(zhǔn)值大的元素，搜索到即停止，并記錄指針的位置；
4.交換當(dāng)前左邊指針位置和右邊指針位置的元素；
5.重復(fù)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 進(jìn)行劃分
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;// 存放樞軸的位置
}
}
快速排序時(shí)間復(fù)雜度分析：
快速排序的一次切分從兩頭開(kāi)始交替搜索，直到left和right重合，因此，一次切分算法的時(shí)間復(fù)雜度為O(n),但整個(gè)快速排序的時(shí)間復(fù)雜度和切分的次數(shù)相關(guān)。
最優(yōu)情況：每一次切分選擇的基準(zhǔn)數(shù)字剛好將當(dāng)前序列等分。
如果我們把數(shù)組的切分看做是一個(gè)樹(shù)，那么上圖就是它的最優(yōu)情況的圖示，共切分了 logn次，所以，最優(yōu)情況下快速排序的時(shí)間復(fù)雜度為O(nlogn);
最壞情況：每一次切分選擇的基準(zhǔn)數(shù)字是當(dāng)前序列中最大數(shù)或者最小數(shù)，這使得每次切分會(huì)有一個(gè)子組，那么總共就得切分n次，所以，最壞情況下，快速排序的時(shí)間復(fù)雜度為O(n^2);
穩(wěn)定性
常見(jiàn)排序算法的穩(wěn)定性：
冒泡排序：
只有當(dāng)arr[i]>arr[i+1]的時(shí)候，才會(huì)交換元素的位置，而相等的時(shí)候并不交換位置，所以冒泡排序是一種穩(wěn)定排序算法。
選擇排序:
選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,例如有數(shù)據(jù){5(1)，8 ，5(2)， 2， 9 },第一遍選擇到的最小元素為2，所以5(1)會(huì)和2進(jìn)行交換位置，此時(shí)5(1)到了5(2)后面，破壞了穩(wěn)定性，所以選擇排序是一種不穩(wěn)定的排序算法。
插入排序：
比較是從有序序列的末尾開(kāi)始，也就是想要插入的元素和已經(jīng)有序的最大者開(kāi)始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如果碰見(jiàn)一個(gè)和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后順序沒(méi)有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。
希爾排序：
希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序 ,雖然一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以希爾排序是不穩(wěn)定的。
歸并排序：
歸并排序在歸并的過(guò)程中，只有arr[i]<arr[i+1]的時(shí)候才會(huì)交換位置，如果兩個(gè)元素相等則不會(huì)交換位置，所以它并不會(huì)破壞穩(wěn)定性，歸并排序是穩(wěn)定的。
快速排序：
快速排序需要一個(gè)基準(zhǔn)值，在基準(zhǔn)值的右側(cè)找一個(gè)比基準(zhǔn)值小的元素，在基準(zhǔn)值的左側(cè)找一個(gè)比基準(zhǔn)值大的元素，然后交換這兩個(gè)元素，此時(shí)會(huì)破壞穩(wěn)定性，所以快速排序是一種不穩(wěn)定的算法。
