2019年10月26日
桶排序
1，算法思想
- 根據(jù)場景設(shè)置桶子的個(gè)數(shù)捷凄。
- 尋訪序列瓶颠，并且把元素一個(gè)一個(gè)放到對應(yīng)的桶子去。
- 對每個(gè)不是空的桶子進(jìn)行排序痛垛。
- 從不是空的桶子里的元素再拼接到一起放回原來的序列中草慧。
2，算法圖解
1
3匙头，算法實(shí)現(xiàn)
public class Bucket {
public static void bucketSort(int[] arr, int step) {
int max = arr[0];
int min = arr[0];
for (int a : arr) {
if (max < a) {
max = a;
}
if (min > a) {
min = a;
}
}
int bucketNum = max / step - min / step + 1;
List buckList = new ArrayList<List<Integer>>();
for (int i = 0; i < bucketNum; i++) {
buckList.add(new ArrayList<Integer>());
}
for (int value : arr) {
int index = indexFor(value, min, step);
((ArrayList<Integer>) buckList.get(index)).add(value);
}
ArrayList<Integer> bucket = null;
int index = 0;
for (int i = 0; i < bucketNum; i++) {
bucket = (ArrayList<Integer>) buckList.get(i);
Collections.sort(bucket);
for (int k : bucket) {
arr[index++] = k;
}
}
}
private static int indexFor(int a, int min, int step) {
return (a - min) / step;
}
public static void main(String[] args) {
Random randomInt = new Random();
int[] a = new int[20];
for (int i = 0; i < a.length; i++) {
a[i] = randomInt.nextInt(100);
}
System.out.println(Arrays.toString(a));
bucketSort(a, 10);
System.out.println(Arrays.toString(a));
}
}
4漫谷，復(fù)雜度分析
假設(shè)待排序的數(shù)據(jù)有個(gè)，桶的個(gè)數(shù)為
個(gè)蹂析，那么每個(gè)桶平均有
個(gè)數(shù)據(jù)舔示，每個(gè)桶內(nèi)部使用對數(shù)階排序算法如快排。每個(gè)桶內(nèi)部的時(shí)間復(fù)雜度為
电抚，那么
個(gè)桶排序的時(shí)間復(fù)雜度就為：
斩郎，又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=K%3DN%2FM" alt="K=N/M" mathimg="1">，該時(shí)間復(fù)雜度又為：
喻频，當(dāng)
，這時(shí)桶排序的時(shí)間復(fù)雜度就接近
肘迎。因此：
- 最好時(shí)間復(fù)雜度：
- 最壞時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
其穩(wěn)定性取決于桶內(nèi)排序算法甥温。
計(jì)數(shù)排序
1，算法思想
- 找出待排序的數(shù)組中最大和最小的元素
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為
的元素出現(xiàn)的次數(shù)妓布，存入數(shù)組
的第
- 對所有的計(jì)數(shù)累加（從
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素
項(xiàng)，每放一個(gè)元素就將
2匣沼，算法圖解
2
由圖中可以看出狰挡，當(dāng)從下標(biāo)0開始填充時(shí)，若執(zhí)行順序從前往后的話，
中的
將會插入到
中加叁，而
中的
將會插入到
中倦沧，因此排序后，
中的相同的元素位置被顛倒了它匕，使得算法不穩(wěn)定展融。
此外，還可以將從下標(biāo)1開始填充豫柬，這時(shí)執(zhí)行順序從前往后就可以保證穩(wěn)定性了
3
3告希，算法實(shí)現(xiàn)
反向填充目標(biāo)數(shù)組的實(shí)現(xiàn)：
public class Count {
public static void countSort(int[] arr) {
int[] temp = new int[arr.length];
int max = arr[0], min = arr[0];
for (int i : arr) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int k = max - min + 1;
int[] count = new int[k];
for (int value : arr) {
count[value - min]++;
}
for (int i = 1; i < count.length; ++i) {
count[i] = count[i] + count[i - 1];
}
for (int i = arr.length - 1; i >= 0; --i) {
int index = count[arr[i] - min] - 1;
temp[index] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(temp, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
Random randomInt = new Random();
int[] a = new int[20];
for (int i = 0; i < a.length; i++) {
a[i] = randomInt.nextInt(100);
}
System.out.println(Arrays.toString(a));
countSort(a);
System.out.println(Arrays.toString(a));
}
}
正向填充目標(biāo)數(shù)組的實(shí)現(xiàn)：
public void countSort2(int[] arr) {
int[] temp = new int[arr.length];
int max = arr[0], min = arr[0];
for (int i : arr) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int k = max - min + 1;
int[] count = new int[k + 1];
for (int value : arr) {
count[value - min + 1]++;
}
for (int i = 0; i < count.length - 1; ++i) {
count[i + 1] += count[i];
}
for (int value : arr) {
temp[count[value - min]++] = value;
}
System.arraycopy(temp, 0, arr, 0, arr.length);
}
4，復(fù)雜度分析
從代碼中可以看出烧给，其最好燕偶，最壞，平均時(shí)間復(fù)雜度都為：础嫡，空間復(fù)雜度為：
指么。
而且該算法是穩(wěn)定的。
基數(shù)排序
1驰吓，算法思想
基數(shù)排序（英語：Radix sort）是一種非比較型==整數(shù)==排序算法涧尿，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較檬贰。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)姑廉，所以基數(shù)排序也不是只能使用于整數(shù)。
它是這樣實(shí)現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)字長度翁涤，數(shù)字較短的數(shù)前面補(bǔ)零桥言。然后，從最低位開始葵礼，依次進(jìn)行一次排序号阿。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列鸳粉。
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital）扔涧，LSD的排序方式由鍵值的最右邊開始，而MSD則相反届谈，由鍵值的最左邊開始枯夜。
2，算法圖解
4
3艰山，算法實(shí)現(xiàn)
public class Radix {
public static void radixSort(String[] arr, int stringLen) {
final int len = 256;
ArrayList<String>[] buckets = new ArrayList[len];
for (int i = 0; i < len; i++) {
buckets[i] = new ArrayList<>();
}
for (int pos = stringLen - 1; pos >= 0; pos--) {
for (String s : arr) {
buckets[s.charAt(pos)].add(s);
}
int idx = 0;
for (ArrayList<String> thisBucket : buckets) {
for (String s : thisBucket) {
arr[idx++] = s;
}
/**
* 每排完一次序湖雹，就將已排好的數(shù)據(jù)從buckets中清空，
* 否則外層再次循環(huán)時(shí)曙搬，第13行會將數(shù)據(jù)重復(fù)存入buckets中摔吏，
* 這樣到最后buckets中會有pos*arr.length個(gè)數(shù)據(jù)鸽嫂，即所有元素都
* 重復(fù)存入了pos個(gè)，會造成arr的ArrayIndexOutOfBoundsException
*/
thisBucket.clear();
}
}
}
public static void main(String[] args) {
String[] arr = {"4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720",
"1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"};
System.out.println(Arrays.toString(arr));
radixSort(arr, 7);
System.out.println(Arrays.toString(arr));
}
}
4征讲，復(fù)雜度分析
若排序的數(shù)據(jù)長度為据某，則需要進(jìn)行
次排序，而內(nèi)部排序的時(shí)間復(fù)雜度為
稳诚，因此總的時(shí)間復(fù)雜度為
哗脖，當(dāng)
不大時(shí)，時(shí)間復(fù)雜度近似于
扳还；空間復(fù)雜度為
才避；是穩(wěn)定的排序算法。
5氨距，應(yīng)用
對定長字符串排序
利用基數(shù)+計(jì)數(shù)排序可以對字符串進(jìn)行排序(LSD)：
反向填充：
public static void radixCountStrSort(String[] arr, int strLength) {
final int bucket = 256;
String[] temp = new String[arr.length];
for (int d = strLength - 1; d >= 0; d--) {
int[] count = new int[bucket];
//count下標(biāo)對應(yīng)的字母中填的值為該字母的最大位次
for (String s : arr) {
count[s.charAt(d)]++;
}
for (int r = 1; r < bucket; r++) {
count[r] += count[r - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
temp[count[arr[i].charAt(d)] - 1] = arr[i];
count[arr[i].charAt(d)]--;
}
System.arraycopy(temp, 0, arr, 0, arr.length);
}
}
也可以正向填充桑逝，同時(shí)為了避免數(shù)組間的頻繁復(fù)制，可以進(jìn)一步優(yōu)化為：
public static void radixCountStrSort2(String[] arr, int strLength) {
final int bucket = 256;
String[] buffer = new String[arr.length];
String[] in = arr;
String[] out = buffer;
for (int d = strLength - 1; d >= 0; d--) {
int[] count = new int[bucket + 1];
//count下標(biāo)對應(yīng)的字母中填的值為該字母的起始位次
for (String s : in) {
count[s.charAt(d) + 1]++;
}
for (int r = 0; r < count.length - 1; r++) {
count[r + 1] += count[r];
}
for (String s : in) {
out[count[s.charAt(d)]++] = s;
}
String[] temp = in;
in = out;
out = temp;
}
//將in中的數(shù)據(jù)復(fù)制到out中
if (strLength % 2 == 1) {
System.arraycopy(in, 0, out, 0, arr.length);
}
}
5
由上圖可以看出俏让，每排序趟數(shù)為奇數(shù)次時(shí)楞遏，完全排好的是指向buffer內(nèi)存塊的數(shù)組，因此要將buffer內(nèi)存塊中的數(shù)據(jù)復(fù)制到arr內(nèi)存塊首昔，以保證arr內(nèi)存塊中的數(shù)據(jù)是排好序的寡喝。
變長字符串排序①
public static void changeStringSort(String[] arr, int maxLen) {
final int bucket = 256;
ArrayList<String>[] wordsByLength = new ArrayList[maxLen + 1];
ArrayList<String>[] buckets = new ArrayList[bucket];
for (int i = 0; i < wordsByLength.length; i++) {
wordsByLength[i] = new ArrayList<>();
}
for (int i = 0; i < bucket; i++) {
buckets[i] = new ArrayList<>();
}
for (String s : arr) {
wordsByLength[s.length()].add(s);
}
int index = 0;
for (ArrayList<String> wordList : wordsByLength) {
for (String s : wordList) {
arr[index++] = s;
}
}
int startingIndex = arr.length;
for (int pos = maxLen - 1; pos >= 0; pos--) {
startingIndex -= wordsByLength[pos + 1].size();
for (int i = startingIndex; i < arr.length; i++) {
buckets[arr[i].charAt(pos)].add(arr[i]);
}
index = startingIndex;
for (ArrayList<String> thisBucket : buckets) {
for (String s : thisBucket) {
arr[index++] = s;
}
thisBucket.clear();
}
}
}
public static void main(String[] args) {
String[] arr = {"1PGCI", "3IY", "3CIO", "4O", "1I", "4JZYE", "2NL", "2ATW"};
System.out.println(Arrays.toString(arr));
changeStringSort(arr, 5);
System.out.println(Arrays.toString(arr));
}
該算法圖解如下：
6
變長字符串排序②
以下使用一種高位優(yōu)先的字符串排序，即MSD方式勒奇，從左向右遍歷所有字符预鬓。
public class StringSortMsd {
private static final int BUCKET = 256;
private static final int CUTOFF = 15;
private static String[] temp;
public static void sort(String[] arr) {
int n = arr.length;
temp = new String[n];
sort(arr, 0, n - 1, 0);
}
private static int charAt(String s, int d) {
if (d == s.length()) {
return -1;
}
return s.charAt(d);
}
private static void sort(String[] arr, int lo, int hi, int d) {
if (hi <= lo + CUTOFF) {
insertion(arr, lo, hi, d);
return;
}
int[] count = new int[BUCKET + 2];
for (int i = lo; i <= hi; i++) {
int c = charAt(arr[i], d);
count[c + 2]++;
}
for (int r = 0; r < BUCKET + 1; r++) {
count[r + 1] += count[r];
}
for (int i = lo; i <= hi; i++) {
int c = charAt(arr[i], d);
temp[count[c + 1]++] = arr[i];
}
for (int i = lo; i <= hi; i++) {
arr[i] = temp[i - lo];
}
for (int r = 0; r < BUCKET; r++) {
sort(arr, lo + count[r], lo + count[r + 1] - 1, d + 1);
}
}
private static void insertion(String[] arr, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(arr[j], arr[j - 1], d); j--) {
exchange(arr, j, j - 1);
}
}
}
private static void exchange(String[] arr, int i, int j) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static boolean less(String v, String w, int d) {
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
if (v.charAt(i) < w.charAt(i)) {
return true;
}
if (v.charAt(i) > w.charAt(i)) {
return false;
}
}
return v.length() < w.length();
}
public static void main(String[] args) {
String[] strings = {"she", "sells", "seashells", "by", "the", "seashore", "the",
"shells", "she", "sells", "are", "surely", "seashells"};
System.out.println(Arrays.toString(strings));
sort(strings);
System.out.println(Arrays.toString(strings));
}
}
上面的代碼其實(shí)使用了兩種排序算法，當(dāng)待排序數(shù)組的長度在CUTOFF以內(nèi)赊颠，則采用的是插入排序方式格二，否則，采用的是MSD方式竣蹦。這時(shí)因?yàn)?code>MSD方式要對大量的長度為256的數(shù)組進(jìn)行處理顶猜，所以當(dāng)數(shù)組長度較小時(shí)，使用插入排序來提高性能痘括。
由于MSD是逐步遞歸處理首字符相同的子數(shù)組长窄，因此當(dāng)字符串中的字符超過其長度的邊界時(shí)，需要設(shè)定一個(gè)標(biāo)志纲菌，讓其不在進(jìn)入下一輪的遞歸排序挠日；本算法中，將該標(biāo)志設(shè)為0驰后，將count[0]作為保留位，而字符又有256種情況矗愧，因此灶芝，count需要最多需要存入BUCKET+1個(gè)數(shù)郑原，所以count = new int[BUCKET + 2]。
算法圖解如下：
7
8
關(guān)于she,shells,she的排序過程涉及到字符到達(dá)字符串的末尾夜涕，其排序圖解為：
9
變長字符串排序③
當(dāng)待排序的字符串?dāng)?shù)組存在大量的相同字符串或較長的公共前綴犯犁，MSD字符串排序會檢查其所有的字符，會創(chuàng)建大量的子數(shù)組女器，因此MSD適用于隨機(jī)字符串排序酸役；而三向字符串快速排序可以很好的解決該問題：
public class StringSortQuick {
private static final int CUTOFF = 15;
public static void sort(String[] arr) {
sort(arr, 0, arr.length - 1, 0);
}
private static int charAt(String s, int d) {
if (d == s.length()) {
return -1;
}
return s.charAt(d);
}
private static void sort(String[] arr, int lo, int hi, int d) {
if (hi <= lo + CUTOFF) {
insertion(arr, lo, hi, d);
return;
}
int lt = lo, gt = hi;
int v = charAt(arr[lo], d);
int i = lo + 1;
while (i <= gt) {
int t = charAt(arr[i], d);
if (t < v) {
exchange(arr, lt++, i++);
} else if (t > v) {
exchange(arr, i, gt--);
} else {
i++;
}
}
sort(arr, lo, lt - 1, d);
if (v >= 0) {
sort(arr, lt, gt, d + 1);
}
sort(arr, gt + 1, hi, d);
}
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(a[j], a[j - 1], d); j--) {
exchange(a, j, j - 1);
}
}
}
private static void exchange(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static boolean less(String v, String w, int d) {
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
if (v.charAt(i) < w.charAt(i)) {
return true;
}
if (v.charAt(i) > w.charAt(i)) {
return false;
}
}
return v.length() < w.length();
}
public static void main(String[] args) {
String[] strings = {"she", "sells", "seashells", "by", "the", "seashore", "the",
"shells", "she", "sells", "are", "surely", "seashells"};
System.out.println(Arrays.toString(strings));
sort(strings);
System.out.println(Arrays.toString(strings));
}
}
10
11
字符串排序總結(jié)
| 算法 | 穩(wěn)定性 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 適用領(lǐng)域 |
|---|---|---|---|---|
| 字符串插入排序 | 穩(wěn)定 |
|
小數(shù)組或者已經(jīng)有序的數(shù)組 | |
低位優(yōu)先的字符串排序(LSD) |
穩(wěn)定 | 較短的定長字符串 | ||
高位優(yōu)先的字符串排序(MSD) |
穩(wěn)定 |
|
隨機(jī)字符串 | |
| 三向字符從快速排序 | 不穩(wěn)定 |
|
通用字符串排序算法，特別適用于含有較長公共前綴的字符串 |
總結(jié)
| 算法 | 穩(wěn)定性 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|---|
| 桶排序 | 取決于桶內(nèi)排序算法 |
|
|
| 計(jì)數(shù)排序 | 穩(wěn)定 | ||
| 基數(shù)排序 | 穩(wěn)定 |
|
