選擇排序
- 含義：從第一個值往后開始查找，每次找到最小的值然后與第一個值進行交換，遍歷整個數(shù)據(jù)達到有序。代碼實現(xiàn)如下：
public static void sort(Comparable[] a)
{
//首先獲取長度
N = a.length();
for(int i=0;i<N;i++) {
min = i;//假設這是最小的下標
for(int j=i+1;j<N;j++) {
if(less(a[j],a[min])) {
min = j;//a[j]對應的值比a[min]小進行交換
}
}
exch(a,min,j);//一次內(nèi)循環(huán)結束交換
}
}
插入排序
- 含義：像整理撲克牌一樣，每次一張一張的把牌移入到有序的牌組中，只是代碼中因為有空間需求，所以需要進行位置交換騰換空間，代碼如下：
public static void sort(Comparable[] a) {
int N = a.length();//獲取數(shù)組長度
for(int i=1;i<N;i++) {
//有序數(shù)組不能為空，所以i從1開始
for (int j=i;j>0 && less(a[j],a[j-1];j--) {
//二重循環(huán)是從大檢索到最小依次比較排序使得有序排列
exch(a,j,j-1);//交換
}
}
}
希爾排序
- 含義：插入排序的升級版，步長不在為1，而是設定為一個h可以加快往后排列的小數(shù)回歸到前面的正常位置中，比起插入排序效率更高
public static void sort(Comparable[] a) {
N = a.length();
//或者這樣設定步長（算法書上的）
# int h=1;
# while(h < N/3) {
# h = 3*h + 1;
#}
#下面的更改為h = h/3也可，性能不一樣
int h = N/2;//設定步長
while(h>=1) {
for(int i=h;i<N;i++) {
for(int j=i;j>h && less(a[j],a[j-h);j-=h) {
exch(a,j,j-h);
}
}
h = h/2;
}
}
歸并排序：
- 時間復雜度是NlgN,命題對于長度為N的任意數(shù)組，自頂向下的歸并排序需要1/2
- 原地歸并方法：需要一個輔助數(shù)組，將原數(shù)組copy到輔助數(shù)組中，然后將輔助數(shù)組的數(shù)據(jù)根據(jù)lo，mid,hi分為兩組依次歸并到原數(shù)組中，具體實現(xiàn)代碼如下,關于值的設定for循環(huán)中的語句含義還是畫一個圖看：
private static void Comparable[] aux;//設定歸并所需的輔助數(shù)組
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo,j=mid+1;
for (int k=lo;k<=hi;k++) {
aux[k] = a[k];
}
//進行歸并排序
for (int k=lo;k<=hi;k++) {
if(i>mid) {
a[k] = aux[j++];
}
else if (j>hi) {
a[k] = aux[i++];
}
else if (less(aux[j],aux[i])) {
a[k] = aux[j++];
}
else {
a[k] = aux[i++];
}
}
}
public static void sort(Comparable[] sort) {
aux = new Comparable[a.length];
sort(a,0,a.length - 1);
}
public static void sort(Comparable[] a,int lo,int hi) {
if (hi<=lo) return;
int mid = (lo + hi)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
/**
* 自頂向上的歸并排序
*多次遍歷整個數(shù)組，根據(jù)子數(shù)組大小進行兩兩歸并
* 類似于1+1=2,2+2=4一直到大于N結束為止
* lo , mid = lo+sz -1, hi = lo +2*sz -1
*/
public static void sortUp(Comparable[] a) {
int N = a.length;
aux = new Comparable[a.length];
for (int sz=1; sz<N; sz = sz + sz) {
//lo < N-sz 保證mid = lo + sz <N,即是說[mid, hi]還存在著數(shù)據(jù)，這個數(shù)據(jù)只是可能沒有sz這么大
for (int lo=0; lo < N-sz; lo += sz+sz) {
//進行逐序歸并,利用Math.max防止最大值索引直接越界
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
}
}
快速排序
- 含義：采用的是分治的排序算法。快排和歸并排序是互補的算法，歸并需要額外的輔助數(shù)組，快速排序不需要。實現(xiàn)的是兩個子數(shù)組有序時整個數(shù)組也就有序了。舉例來說如下：首先從數(shù)組中選定一個值，假如是第一個值，然后遍歷整個數(shù)組，將比這個值小的數(shù)據(jù)放在這個數(shù)的左邊，比這個大的放在數(shù)據(jù)右邊，從兩頭往中間縮進，所以需要的時間會小很多，然后再進行遞歸遍歷實現(xiàn)最后以1位間隔的數(shù)據(jù)段，自然整個數(shù)組也就有序了。
- 代碼如下：
public static void sort(Comparable[] a) {
int N = a.length;
sort(a, 0, N-1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi < lo) return;//遞歸結束條件返回
int j = partition(a, lo, hi);
sort(a, lo, j-1);//左邊數(shù)組快排
sort(a, j+1, hi);//右邊數(shù)組快排
}
//以下這個函數(shù)是實現(xiàn)快排的重要代碼
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
while (true) {
while (less(a[i++],a[lo])) {
//控制越界
if (i == hi) {
break;
}
}
while (less(a[lo],a[j--])) {
if (j == lo) {
break;
}
}
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
//快排實現(xiàn)代碼2感覺比上面那一種簡單
private static int partitionBack(Comparable[] a, int lo, int hi) {
Comparable key = a[lo];
while(lo < hi) {
while (lo < hi && less(key, a[hi])) hi--;
a[lo] = a[hi];
while (lo < hi && less(a[lo], key)) lo++;
a[hi] = a[lo];
}
a[hi] = key;
return hi;
}
堆排序
- 含義：采用堆的形式（大根堆：父節(jié)點都比子節(jié)點大，小根堆：父節(jié)點都比子節(jié)點?。?，首先將一堆數(shù)據(jù)排列成為大根堆，然后從根節(jié)點取出最大值，一次放入到隊列的最后，就可以變成一個有序的從小到大排序的數(shù)據(jù)，其時間復雜度為NlgN。
- 父節(jié)點和子節(jié)點滿足以下關系：父節(jié)點序號*2+1 或者 父節(jié)點序號*2 + 2 = 子節(jié)點序號，父節(jié)點序號 = 子節(jié)點序號-1/2
- 算法如下：
private static void sink(Comparable[] a, int k, int N) {
//下沉算法
while (2*k+1 < N) {
int j = 2*k+1;//找尋子節(jié)點
//比較兩個子節(jié)點找出最大的
if (j<N && less(a[j], a[j+1])) {
j++;
}
//比較父節(jié)點和最大的子節(jié)點
if(!less(a[k], a[j])) {
//滿足堆特性，結束循環(huán)
break;
}
//進行交換
exch(a,k,j);
//繼續(xù)下層遍歷
k = j;
}
}
//實現(xiàn)堆有序的過程
public static void sort(Comparable[] a) {
int N = a.length - 1;//數(shù)組和實際下標有一個1的差距
//實現(xiàn)對有序
for (int k = N/2; k>=1; k--) {
sink(a, k, N);
}
//進行堆排序，每次將根節(jié)點挪到后面在進行堆排序循環(huán)
while (N >1 ) {
exch(a,1,N--);
sink(a,1,N);
}
}
冒泡排序
- 含義：每一輪從前往后的遍歷，較大數(shù)據(jù)后排，就像魚吐泡泡一樣越來越大，輪次結束后數(shù)組整體有序
- 源代碼如下：
package com.zhou.sort;
import com.zhou.prepare.StdOut;
/**
* Created by 強 on 2018/11/21.
* 冒泡排序：每次進行兩個數(shù)字的比較，較大者放到后面，從前往后依次進行直到最后一個是本輪次的最大的數(shù)，然后繼續(xù)下一輪直到整個數(shù)組有序
*/
public class Bubble {
public static void main(String[] args) {
Integer[] a = {5, 3, 2, 10, 1, 15, 4,90};
bubble_sort(a);
show(a);
System.out.println(isSorted(a));
}
private static void sort(Comparable[] a) {
//外層循環(huán)控制輪次
for (int i = 0; i < a.length; i++) {
//內(nèi)存循環(huán)控制比較
for (int j = 0; j < a.length - i - 1; j++) {
if (less(a[j+1], a[j])) exch(a, j, j+1);
}
}
}
/**
* 將雙層for循環(huán)進化為一個while循環(huán)加一個for循環(huán)，此時若數(shù)組處于有序狀態(tài)可以大大減小排序時間
* 比如數(shù)組本身有序，那么時間復雜度進化為O(n),逆序狀態(tài)下與原始冒泡排序等同，平均復雜度和逆序等同
* @param a
*/
private static void bubble_sort(Comparable[] a) {
int pos = a.length - 1;
while (pos != 0) {
int bound = pos;
pos = 0;//用于標記是否有交換記錄，若有，則記錄"下一趟要處理的最后一個位置"
for (int j = 0; j < bound; j++) {
if (less(a[j+1], a[j])) {
exch(a, j, j+1);
pos = j;
}
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i=0; i<a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i=1; i<a.length; i++) {
if (less(a[i], a[i-1])) {
return false;
}
}
return true;
}
}
基數(shù)排序(桶排序)
含義：從最基本的認知出發(fā)的排序，兩個數(shù)比較大小首先是看位數(shù)是否相同，如果不同那么位數(shù)多的肯定比位數(shù)少的大，位數(shù)相同則逐個位置進行比較大小進行排序。這個每一位比較就被稱為基數(shù)（個位/十位/百位等），這個排序過程又可以分為MSD（高位優(yōu)先排序，從左到右）和LSD（低位優(yōu)先排序，從右到左）和字符串的排序倒是有異曲同工之處。
此處著眼于LSD，具體實現(xiàn)的過程如下：
首先聲明10個桶，每個桶代表的數(shù)字0-9，也就是對應的基數(shù)，然后對于每一個數(shù)字按照從低位優(yōu)先（個位開始）進行取余，加如對應的位數(shù)字為5，那么就放入數(shù)字為5的桶中，依次將數(shù)組中所有數(shù)據(jù)都放入桶中。
之后再從桶0開始遍歷，將桶中所有數(shù)據(jù)依次取出（同一個桶中的數(shù)據(jù)按照先進先出的特性）放入到原數(shù)組中
然后將基數(shù)擴大十倍（個位變百位，百位變千位，依次類推），重復上述過程直到最后循環(huán)結束
舉例來說，一組數(shù)據(jù)5、2、9、7、18、17、52
如下圖中所示，按照個位數(shù)字大小依次放入桶中，然后再 將桶中的數(shù)據(jù)串起來輸出得到排序后的結果2、52、5、7、17、18、9，然后以此順序進行十位的桶排序
如下圖第二張圖中所示，重復操作即可得到最后有序的數(shù)組完成此次排序的結果
-
在代碼實現(xiàn)過程中用一個二維數(shù)組實現(xiàn)，行為10表示10個桶，列表示的是桶中藥存儲的數(shù)據(jù)，長度為數(shù)組長度，然后聲明一個長度為10的一維數(shù)組用來表示每個桶中有多少數(shù)據(jù)
第一次桶排序
第二次桶排序 源代碼實現(xiàn)如下所示：
package com.zhou.sort;
/**
* Created by 強 on 2019/4/6.
*/
public class RadixSort {
public static void main(String[] args) {
int[] num = new int[50];
for (int i=0; i<num.length; i++) {
num[i] = (int)(Math.random()*1000);
}
radixSort(num, 1000);
System.out.println("the result is order: " + isSorted(num));
for (int i=0; i<num.length; i++) {
System.out.print(num[i]+ " ");
}
}
//d表示的是數(shù)組中最大位的位數(shù)+1位，舉例來說加如排序的都是1-99兩位數(shù)，那么d就是100，如果是1-999那么d就是1000
private static void radixSort(int[] array, int d) {
int n = 1;//代表位數(shù)對應的數(shù):1、10、100
int length = array.length;
int[][] bucket = new int[10][length];//排序桶用于保存每次排序后的結果，這一位上排序結果相同的數(shù)字放在同一個桶里
int[] order = new int[10];//用于保存每個桶里有多少個數(shù)字,一共有10個桶
while (n<d) {
for (int num:array) {
//將數(shù)組array每個數(shù)字放在相應的桶里
int digit = (num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
int k=0;//回寫到原數(shù)組時，原數(shù)組下標索引
for (int i=0; i<10; i++) {
//將前一個循環(huán)生成的桶里的數(shù)據(jù)覆蓋到原數(shù)組中用于保存這一位的排序結果
if(order[i]!=0) {
//這個桶里有數(shù)據(jù)，從上到下排序并將數(shù)據(jù)保存到原數(shù)組中
for (int j=0; j<order[i]; j++) {
array[k] = bucket[i][j];
k++;
}
}
order[i]=0;//將桶里計數(shù)器清零，用于下一次位排序
}
n*=10;
}
}
private static boolean isSorted(int[] a) {
for (int i=1; i<a.length; i++) {
if (a[i]<a[i-1]) {
return false;
}
}
return true;
}
}
排序算法總結
- 所需輔助空間最多：歸并排序
- 所需輔助空間最少：堆排序
- 平均速度最快：快速排序
- 不穩(wěn)定性：快速排序、希爾排序、堆排序（不穩(wěn)定性指的是相同的兩個數(shù)在排序前后的相對位置是否改變）
- 平均時間復雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，快排最好
- 平均時間復雜度為O(n2)的方法有：直接插入排序、冒泡排序、簡單選擇排序，其中直接插入排序最好，尤其是對那些關鍵字近似有序的記錄序列
-
平均時間復雜度為O(n)的只有基數(shù)排序
排序算法比較表
排序完整代碼鏈接
https://github.com/zhouwaiqiang/JavaLearning/tree/master/algorithm/src/com/zhou/sort
