目錄
1淹真、前言
2、計(jì)數(shù)排序
3连茧、基數(shù)排序
4核蘸、使用場(chǎng)景
1巍糯、前言
常見(jiàn)的排序算法有很多，例如歸并排序客扎、堆排序祟峦、快速排序還有插入排序等等该面，以上排序有一個(gè)共同點(diǎn)妓蛮，隊(duì)列中的元素需要通過(guò)比較來(lái)計(jì)算元素的位置，它們被統(tǒng)稱為比較排序窗声。
比較排序是有效率極值存在的袱吆。比較排序過(guò)程可以被抽象為決策樹模型厌衙，決策樹模型是一個(gè)二叉樹。每個(gè)元素的位置根據(jù)二叉樹最終決定自己的位置绞绒。
在最壞情況下婶希，任何比較排序算法至少需要做N*lgN次比較
此定理的詳細(xì)推導(dǎo)過(guò)程請(qǐng)參照算法導(dǎo)論。
比較排序算法是有效率極值存在的处铛。本文中介紹的兩種算法非比較排序算法饲趋，它們都需要滿足一定的條件，它們的效率值均為N撤蟆。
1奕塑、計(jì)數(shù)排序
如果一個(gè)數(shù)組中的最大值已知，且數(shù)組中最大值減去最小值的差不大的話家肯，則可以使用計(jì)數(shù)排序龄砰。計(jì)數(shù)排序，顧名思義讨衣，統(tǒng)計(jì)數(shù)組中每個(gè)元素出現(xiàn)的次數(shù)换棚，然后計(jì)算出小于或等于p的元素個(gè)數(shù)q，那么p在數(shù)組中的位置應(yīng)該是q-1（數(shù)組從0開(kāi)始反镇，所以要減1）固蚤。
計(jì)數(shù)排序需要使用額外的內(nèi)存空間，一個(gè)待排序數(shù)組的等長(zhǎng)數(shù)組歹茶，一個(gè)計(jì)數(shù)數(shù)組夕玩。
/**
* @param arrayA 待排序數(shù)組
* @param arrayB 返回的正確排序的數(shù)組
* @param k 數(shù)組A中的元素最大值
*/
public static int[] countSort(int[] arrayA, int[] arrayB, int k){
int value = 0;
int pos = 0;
int size = arrayA.length;
int[] arrayC = new int[k + 1];
for (int i = 0; i <= k; i++) {
arrayC[i] = 0;
}
//數(shù)組a中每一個(gè)value出現(xiàn)的個(gè)數(shù)，存儲(chǔ)在c中惊豺，因?yàn)閏中長(zhǎng)度為k+1
//而a中元素最大值為k燎孟，所以可以存下這些值
for (int i = 0; i < size; i++) {
arrayC[arrayA[i]]++;
}
//數(shù)組C[i]中存放的是a中i元素出現(xiàn)的個(gè)數(shù)，所以C[i]+C[i-1],則是不大于i的元素的個(gè)數(shù)
for (int i = 1; i <= k; i++) {
arrayC[i] = arrayC[i] + arrayC[i-1];
}
//從數(shù)組c中取出a數(shù)組中元素不大于自己的個(gè)數(shù)尸昧，然后放入新數(shù)組b中揩页，則排序已完成
for (int i = size-1; i >= 0; i--) {
value = arrayA[i];
pos = arrayC[value];
arrayB[pos-1]=value;
arrayC[value]--;
}
return arrayB;
}
2、基數(shù)排序
計(jì)數(shù)排序的使用條件有點(diǎn)尷尬烹俗，必須找到數(shù)組中的最大值爆侣，找最大值至少也要lgN的時(shí)間萍程。基數(shù)排序累提，可理解為對(duì)計(jì)數(shù)排序的完美使用方式尘喝。
基數(shù)排序，將數(shù)組中的元素按照個(gè)十百千位分門別類斋陪，分別先后對(duì)個(gè)們朽褪、十位、百位无虚、千位等排序缔赠，那么最后結(jié)果肯定也是有序的。假如針對(duì)所有元素的個(gè)位排序友题，由于個(gè)位上的最大值為9嗤堰，非常符合計(jì)數(shù)排序的條件。由此度宦，基數(shù)排序的算法就是踢匣，針對(duì)個(gè)、十戈抄、百等位置上使用計(jì)數(shù)排序离唬。
public static int[] countSort2(int[] arrayA, int index){
int value = 0;
int pos = 0;
//個(gè)、十划鸽、百等位置上最大值為9
int k = 9;
int size = arrayA.length;
int[] arrayB = new int[size];
int[] arrayC = new int[k + 1];
for (int i = 0; i <= k; i++) {
arrayC[i] = 0;
}
//數(shù)組c中存的是數(shù)組a某個(gè)具體數(shù)位上的值的出現(xiàn)次數(shù)
for (int i = 0; i < size; i++) {
arrayC[getBitData(arrayA[i], index)]++;
}
for (int i = 1; i <= k; i++) {
arrayC[i] = arrayC[i] + arrayC[i-1];
}
//注意b中存放的是數(shù)組a中的值输莺。
for (int i = size-1; i >= 0; i--) {
value = getBitData(arrayA[i], index);
pos = arrayC[value];
arrayB[pos-1]=arrayA[i];
arrayC[value]--;
}
return arrayB;
}
public static int[] radixSort(int[] arrayA,int index){
for (int i = 0; i < index; i++) {
arrayA = countSort2(arrayA, i);
}
return arrayA;
}
基數(shù)排序，非常適合比較時(shí)間大小等裸诽，以后遇到時(shí)間的排序應(yīng)該第一時(shí)間想到基數(shù)排序嫂用。
本文中代碼已上傳到本人的github空間，歡迎訪問(wèn)
