大一下學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法辫塌，如今已經(jīng)大三了漏策，幾乎70%左右的知識(shí)都已經(jīng)又還給了親愛的老師了【拾保可關(guān)鍵是學(xué)費(fèi)不給退啊掺喻，所以是時(shí)候要找回一些以前學(xué)過的知識(shí)了。
排序算法總結(jié)：
一、冒泡排序(Bubble Sort)
二巢寡、選擇排序(Select Sort)
三喉脖、插入排序(Insert Sort)
四、希爾排序(Shell Sort)
五抑月、快速排序(Quick Sort)
六树叽、堆排序(Heap Sort)
七、歸并排序(Merge Sort)
八谦絮、計(jì)數(shù)排序(Counting Sort)
九题诵、桶排序(Bucket Sort)
十、基數(shù)排序(Radix Sort)
一层皱、冒泡排序
冒泡排序的基本思想就是：每一次遍歷的時(shí)候性锭，只比較兩個(gè)相鄰的元素大小，最后"冒"出一個(gè)最大值/最小值叫胖。
在實(shí)現(xiàn)的時(shí)候草冈，需要注意每個(gè)循環(huán)語(yǔ)句的次數(shù)。
/**
* 原始冒泡排序
* 時(shí)間復(fù)雜度為O(n^2)
* @param args
*/
public static void bubbleSort(int[] args) {
if (args == null || args.length == 0) {
return;
}
else {
for (int i = 0; i < args.length - 1; i++) {
for (int j = args.length - 1; j > i; j--) {
if (args[j - 1] > args[j]) {
swap(args, j-1, j);
}
}
}
}
}
public static void swap(int[] args, int small, int big) {
int temp;
temp = args[big];
args[big] = args[small];
args[small] = temp;
}
** 冒泡算法的改進(jìn)： **
在每次大的循環(huán)進(jìn)行初始瓮增，將 isSwap = false怎棱。這樣每次小的循環(huán)進(jìn)行完之后，進(jìn)行依次對(duì)比绷跑，如果isSwap 為 false,則可以證明該數(shù)組已經(jīng)有序拳恋。
/**
* 改進(jìn)后的算法排序時(shí)間復(fù)雜度最佳可以達(dá)到O(n)
* @param args
*/
public static void bubbleSortImprove(int[] args) {
boolean isSwap;
if (args == null || args.length == 0) {
return;
}
for (int i =0; i < args.length; i++) {
isSwap = false;
for (int j = args.length - 1; j > i; j--) {
if (args[j - 1] > args[j]) {
swap(args, j-1, j);
isSwap = true;
}
}
if (!isSwap) {
return;
}
}
}
二、選擇排序
選擇排序的主要過程是：從第一個(gè)數(shù)字開始砸捏，將其下標(biāo)記為minIndex,然后逐個(gè)與后邊的所有數(shù)字進(jìn)行比較谬运，在這一輪比較結(jié)束后，判斷minIndex是否和第一個(gè)數(shù)字的下標(biāo)一致垦藏，如果一致梆暖，則第一個(gè)數(shù)字為數(shù)組中最小數(shù)，否則掂骏，將minIndex所指向的數(shù)字與第一個(gè)數(shù)字交換式廷。接著從第二個(gè)數(shù)字開始，依次按照上邊的流程來(lái)進(jìn)行芭挽，大的循環(huán)需要進(jìn)行的次數(shù)為:arr.lenth - 1
/**
* 選擇排序
* 時(shí)間復(fù)雜度為O(n^2)
* @param args
*/
public static void selectSort(int[] args) {
int minIndex;
if (args == null || args.length == 0) {
return;
}
else {
for (int i = 0; i < args.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < args.length - 1; j++) {
if (args[j] < args[minIndex]) {
minIndex = j;
}
}
//如果minIndex不等于i，說(shuō)明此時(shí)已經(jīng)找到了最小的值蝗肪，所以要坐一個(gè)交換袜爪。
if (minIndex != i) {
swap(args,minIndex, i);
}
}
}
}
public static void swap(int[] args, int small, int big) {
int temp;
temp = args[big];
args[big] = args[small];
args[small] = temp;
}
三、插入排序
插入排序的主要過程是：先選出數(shù)組中的一個(gè)數(shù)字（一般選擇第一個(gè)數(shù)字）薛闪，然后接著選擇第二個(gè)數(shù)字辛馆，判斷第二個(gè)數(shù)字和第一個(gè)數(shù)字的大小，如果比第一個(gè)數(shù)字大，則插入到后邊昙篙，反之則第一個(gè)數(shù)字后移一個(gè)位置腊状，第二個(gè)數(shù)字插入到第一個(gè)位置。接著選擇第三個(gè)數(shù)字苔可，判斷第三個(gè)數(shù)字與此時(shí)位置上的第二個(gè)數(shù)字的大小缴挖，如果比第二個(gè)數(shù)字大，則插入到最后焚辅，反之映屋，則繼續(xù)判斷與第一個(gè)數(shù)字的大小，如果比第一個(gè)數(shù)字大同蜻，則插入到中間棚点，反之，第一個(gè)數(shù)字后移湾蔓，第三個(gè)數(shù)字插入到第一的位置瘫析。后邊的數(shù)字也是依次按照這樣的方式來(lái)進(jìn)行判斷，移動(dòng)默责，插入贬循。
/**
* 插入排序，時(shí)間復(fù)雜度O(n*2)
* @param args
*/
public static void insertSort(int[] args) {
if (args == null | args.length == 0) {
return;
}
else {
for (int i = 1; i < args.length; i++) {
int j = i;
int target = args[i];
while (j >= 1 && target < args[j - 1]) {
args[j] = args[j - 1];
j--;
}
args[j] = target;
}
}
}
四傻丝、希爾排序
我所理解的希爾排序甘有，其實(shí)就是基于插入排序(Insert Sort)來(lái)實(shí)現(xiàn)的。所謂希爾排序的一大關(guān)鍵實(shí)現(xiàn)就是不再需要再?gòu)氖嫉侥┮粋€(gè)個(gè)元素挨個(gè)去比較葡缰、插入亏掀，而是根據(jù)一個(gè)gap變量，來(lái)將數(shù)組內(nèi)的元素來(lái)進(jìn)行分組泛释，先是每個(gè)小組內(nèi)進(jìn)行比較滤愕，然后再進(jìn)一步縮小gap的值，分組來(lái)比較怜校。最后當(dāng)gap的值縮小為1的時(shí)候间影，就儼然成為了我之前所學(xué)習(xí)的簡(jiǎn)單插入排序了。不過這個(gè)時(shí)候再進(jìn)行簡(jiǎn)單的插入排序茄茁，經(jīng)過前幾輪的分組比較之后魂贬，此時(shí)大部分的數(shù)據(jù)都已經(jīng)有序了，需要比較的元素相對(duì)來(lái)說(shuō)就減少很多裙顽。
廢話不多說(shuō)了付燥，直接上代碼(注意與插入排序的代碼進(jìn)行比較，觀察有哪些異同點(diǎn)愈犹。)
package sortAlgorithm;
/**
* Created by Max on 2016/10/30.
*/
public class ShellSort {
/**
* 希爾排序
* 時(shí)間復(fù)雜度為0(n^2)
* @param nums
*/
public static void hellSort(int[] nums) {
//第一次的gap為數(shù)組長(zhǎng)度除以2取整
int gap = nums.length / 2;
while (gap >= 1) {
for (int i = gap; i < nums.length; i++) {
int j = i;
//獲取到每一次要與小組內(nèi)其他元素進(jìn)行比較的基礎(chǔ)值nums[i]
int temp = nums[i];
//利用一個(gè)while循環(huán)键科，來(lái)遍歷小組內(nèi)其他元素，并與基礎(chǔ)值比較num[i]
while (j >= gap && temp > nums[j - gap]) {
nums[j] = nums[j - gap];
j -= gap;
}
//如果j != i，則說(shuō)明在遍歷的過程中勋颖，發(fā)生了交換嗦嗡，故這里也要將num[i]插入到相應(yīng)的位置
if (j != i) {
nums[j] = temp;
}
}
//當(dāng)gap = 1時(shí)，則最終完全變成了簡(jiǎn)單的插入排序饭玲。
if (gap == 2) {
gap = 1;
}
else {
gap /= 2;
}
}
for (int i : nums) {
System.out.print(i + " ");
}
}
public static void main(String[] args) {
int[] args1 = {5,3,8,6,4,23,34,12,54};
hellSort(args1);
}
}
五侥祭、快速排序（快排）
快速排序的過程是：第一次排序，一般以第一個(gè)數(shù)字為基礎(chǔ)值咱枉，在數(shù)組兩端分別有兩個(gè)指針：left 和 right 卑硫，然后right 指針首先向左移動(dòng)，尋找小于基礎(chǔ)值的數(shù)字蚕断，找到便停下欢伏，這時(shí)left指針開始向右尋找，尋找大于基礎(chǔ)值的數(shù)字亿乳，找到便停下硝拧。接著left 和 right所指向的值便進(jìn)行swap操作，接著左右指針再接著遍歷比較下去葛假，流程如上障陶。不過在每次比較之前需要比較left 和 right指針是否重合了。重合便結(jié)束遍歷聊训。結(jié)束遍歷之后抱究，將指針重合位置所指向的數(shù)字與基礎(chǔ)值進(jìn)行swap操作，這時(shí)已經(jīng)初步將小于和大于基礎(chǔ)值的數(shù)字分布于左右兩側(cè)了带斑。接著再進(jìn)行兩個(gè)一左一右的遞歸調(diào)用鼓寺，便可以最終排序成功。
/**
* 快速排序
* 時(shí)間復(fù)雜度:O(nlgn)
* @param args
* @param left
* @param right
*/
public static void quickSort(int[] args, int left, int right) {
if (left >= right) {
return;
}
else {
int pivotPos = partition(args, left, right);
quickSort(args, left, pivotPos - 1);
quickSort(args, pivotPos + 1, right);
}
}
public static int partition(int[] args, int left, int right) {
int pivotKey = args[left];
int pivotPointer = left;
while (left < right) {
while (left < right && args[right] >= pivotKey) {
right--;
}
while (left < right && args[left] <= pivotKey) {
left++;
}
swap(args, left, right);
}
swap(args, pivotPointer, left);
return left;
}
public static void swap(int[] args, int small, int big) {
int temp;
temp = args[big];
args[big] = args[small];
args[small] = temp;
}
** 快速排序的優(yōu)化代碼： **
由于int pivotKey = args[left]; 已經(jīng)保存過基礎(chǔ)值了勋磕，所以可以直接將其值給覆蓋掉妈候。這樣就減少了一個(gè)int temp 臨時(shí)變量的產(chǎn)生了。
/**
* 快速排序
* 時(shí)間復(fù)雜度:O(nlgn)
* @param args
* @param left
* @param right
*/
public static void quickSort(int[] args, int left, int right) {
if (left >= right) {
return;
}
else {
int pivotPos = partition(args, left, right);
quickSort(args, left, pivotPos - 1);
quickSort(args, pivotPos + 1, right);
}
}
public static int partition(int[] args, int left, int right) {
int pivotKey = args[left];
while (left < right) {
while (left < right && args[right] >= pivotKey) {
right--;
}
args[left] = args[right];
while (left < right && args[left] <= pivotKey) {
left++;
}
args[right] = args[left];
}
args[left] = pivotKey;
return left;
}
public static void swap(int[] args, int small, int big) {
int temp;
temp = args[big];
args[big] = args[small];
args[small] = temp;
}
六挂滓、堆排序
什么是二叉樹?
每個(gè)節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)的樹狀結(jié)構(gòu)
二叉樹有哪些性質(zhì)?
- 二叉樹的第i層至多有2^(i-1)個(gè)節(jié)點(diǎn),
- 深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)苦银，
- 對(duì)任何一顆二叉樹T，如果其終端節(jié)點(diǎn)數(shù)為n0,度為2的節(jié)點(diǎn)數(shù)為n2赶站，則n0=n2+1
二叉樹分類
- 完全二叉樹(complete binary tree)：深度為 k幔虏，有 n 個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為 k 的滿二叉樹中序號(hào)為 1 至 n 的節(jié)點(diǎn)對(duì)應(yīng)時(shí)贝椿，稱之為完全二叉樹
- 滿二叉樹(full binary tree)：一顆深度為k所计，且有2^k-1個(gè)節(jié)點(diǎn)的二叉樹
那么，堆又是什么呢?
以二叉堆為例团秽，其可以視為一棵完全的二叉樹，完全二叉樹的一個(gè)“優(yōu)秀”的性質(zhì)是，除了最底層之外习勤，每一層都是滿的踪栋，這使得堆可以利用數(shù)組來(lái)表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素图毕。
二叉堆的特性：
對(duì)于給定的某個(gè)結(jié)點(diǎn)的下標(biāo) i夷都，可以很容易的計(jì)算出這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、孩子結(jié)點(diǎn)的下標(biāo)：
Parent(i) = floor(i/2)予颤，i 的父節(jié)點(diǎn)下標(biāo)
Left(i) = 2i囤官，i 的左子節(jié)點(diǎn)下標(biāo)
Right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)
二叉堆的分類：
- 大頂堆：最大堆中的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）堆中每個(gè)父節(jié)點(diǎn)的元素值都大于等于其孩子結(jié)點(diǎn)（如果存在）
- 小頂堆：最小堆中的最小元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）堆中每個(gè)父節(jié)點(diǎn)的元素值都小于等于其孩子結(jié)點(diǎn)（如果存在）
堆排序原理
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出蛤虐，將剩余的堆繼續(xù)調(diào)整為最大堆党饮，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束驳庭。時(shí)間復(fù)雜度為(nlogn)刑顺。
過程
步驟一：
將數(shù)組初始化為大頂堆：
//將該數(shù)組初始化為大頂堆
public static void heapInit(int[] nums) {
//獲取此二叉樹最后一個(gè)非葉節(jié)點(diǎn)node
int node = nums.length / 2 - 1;
int length = nums.length;
int tempNode;
for (; node >= 0; node--) {
tempNode = node;
//獲得該非葉節(jié)點(diǎn)的左右孩子節(jié)點(diǎn):lNode,rNode
int lNode = node * 2 + 1;
int rNode = node * 2 + 2;
if (lNode < length && nums[lNode] > nums[tempNode]) {
tempNode = lNode;
}
if (rNode < length && nums[rNode] > nums[tempNode]) {
tempNode = rNode;
}
if (tempNode != node) {
//如果有子節(jié)點(diǎn)比父節(jié)點(diǎn)大，就進(jìn)行交換
swap(nums, tempNode, node);
}
}
}
接著:
for (int j = 0; j < nums.length; j++) {
swap(nums, 0, nums.length - 1 - j);
headAdjust(nums, nums.length - j - 1, 0);
}
循環(huán)將第一個(gè)元素（即為每一輪的最大值）與最后一個(gè)元素進(jìn)行交換饲常，要注意每一次交換過之后要再對(duì)該堆進(jìn)行一個(gè)調(diào)整，使其再次成為一個(gè)大頂堆。
調(diào)整的函數(shù)為：
public static void headAdjust(int[] nums, int numsLength, int parentNode) {
int lNode = parentNode * 2 + 1;
int rNode = parentNode * 2 + 2;
int maxNode = parentNode;
if (lNode < numsLength && nums[lNode] > nums[maxNode]) {
maxNode = lNode;
}
if (rNode < numsLength && nums[rNode] > nums[maxNode]) {
maxNode = rNode;
}
if (maxNode != parentNode) {
swap(nums, maxNode, parentNode);
//遞歸調(diào)用腻要，直到調(diào)整到葉子節(jié)點(diǎn)處
headAdjust(nums, numsLength, maxNode);
}
}
附上完整的源碼：
package sortAlgorithm;
import java.util.Arrays;
/**
* Created by Max on 2016/10/29.
*/
public class HeapSort {
//將該數(shù)組初始化為大頂堆
public static void heapInit(int[] nums) {
//獲取此二叉樹最后一個(gè)非葉節(jié)點(diǎn)node
int node = nums.length / 2 - 1;
int length = nums.length;
int tempNode;
for (; node >= 0; node--) {
tempNode = node;
int lNode = node * 2 + 1;
int rNode = node * 2 + 2;
if (lNode < length && nums[lNode] > nums[tempNode]) {
tempNode = lNode;
}
if (rNode < length && nums[rNode] > nums[tempNode]) {
tempNode = rNode;
}
if (tempNode != node) {
//如果有子節(jié)點(diǎn)比父節(jié)點(diǎn)大郭计，就進(jìn)行交換
swap(nums, tempNode, node);
}
}
}
public static void headAdjust(int[] nums, int numsLength, int parentNode) {
int lNode = parentNode * 2 + 1;
int rNode = parentNode * 2 + 2;
int maxNode = parentNode;
if (lNode < numsLength && nums[lNode] > nums[maxNode]) {
maxNode = lNode;
}
if (rNode < numsLength && nums[rNode] > nums[maxNode]) {
maxNode = rNode;
}
if (maxNode != parentNode) {
swap(nums, maxNode, parentNode);
//遞歸調(diào)用，直到調(diào)整到葉子節(jié)點(diǎn)處
headAdjust(nums, numsLength, maxNode);
}
}
public static void swap(int[] nums, int start, int end) {
int temp;
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
public static void heapSort(int[] nums) {
//首先將數(shù)組初始化為一個(gè)大頂堆
heapInit(nums);
for (int j = 0; j < nums.length; j++) {
swap(nums, 0, nums.length - 1 - j);
headAdjust(nums, nums.length - j - 1, 0);
}
for (int i : nums) {
System.out.print(i + " ");
}
}
public static void main(String[] args) {
int[] nums = {54, 23, 44, 78, 11, 5};
System.out.println("排序之后：");
heapSort(nums);
}
}
七播聪、歸并排序
什么是歸并排序朽基？
歸并排序的過程可以簡(jiǎn)單概括為：先將該數(shù)組進(jìn)行一個(gè)遞歸分治的分組，然后再將每個(gè)分組的結(jié)果進(jìn)行合并排序犬耻，最終形成一個(gè)有序的數(shù)組踩晶。那么，"遞歸分治"究竟是什么枕磁？以后就要多多了解些這方面的東西啦,然后適時(shí)地再總結(jié)一下渡蜻。
下面是利用遞歸分治思想進(jìn)行分組的代碼：
/**
* 歸并排序，時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n)计济。
* 這里的算法蘊(yùn)含了一種算法思想：遞歸分治
* 何謂遞歸分治茸苇？即將一個(gè)大問題分解成n個(gè)小問題，然后再采用遞歸的方式來(lái)進(jìn)行解決沦寂。
* @param nums
* @param start
* @param end
*/
public static void Sort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
Sort(nums, start, mid);
Sort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
下邊是對(duì)數(shù)組進(jìn)行合并的代碼：
public static void merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
}
else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= end) {
temp[k++] = nums[j++];
}
for(int p = 0; p < temp.length; p++) {
nums[start + p] = temp[p];
}
}
完整代碼如下:
package sortAlgorithm;
/**
* Created by Max on 2016/10/31.
*/
public class MergeSort {
/**
* 歸并排序学密，時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n)。
* 這里的算法蘊(yùn)含了一種算法思想：遞歸分治
* 何謂遞歸分治传藏？即將一個(gè)大問題分解成n個(gè)小問題腻暮，然后再采用遞歸的方式來(lái)進(jìn)行解決彤守。
* @param nums
* @param start
* @param end
*/
public static void Sort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
Sort(nums, start, mid);
Sort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
public static void merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
}
else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= end) {
temp[k++] = nums[j++];
}
for(int p = 0; p < temp.length; p++) {
nums[start + p] = temp[p];
}
}
public static void main(String[] args) {
int[] args1 = {5,3,8,6,4,23,34,12,54};
Sort(args1, 0, args1.length - 1);
for (int i : args1) {
System.out.print(i + " ");
}
}
}
八、計(jì)數(shù)排序
說(shuō)實(shí)話哭靖，看完計(jì)數(shù)排序的介紹和算法具垫，只能說(shuō)代碼看懂了，但是還不太理解其內(nèi)部的原理试幽。先把源碼貼上去吧筝蚕，有關(guān)該算法的分析以后補(bǔ)上。
package sortAlgorithm;
/**
* Created by Max on 2016/11/1.
*/
public class CountingSort {
/**
* 計(jì)數(shù)排序
* 時(shí)間復(fù)雜度O(n + k) 铺坞，n為數(shù)組長(zhǎng)度起宽，k為輸入數(shù)字的最大范圍
* @param arr
*/
public static void countingSort(int[] arr) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[256];
for (int i = 0; i < 256; ++i) {
count[i] = 0;
}
for (int i = 0; i < n; ++i) {
++count[arr[i]];
}
for (int i = 1; i <= 255; ++i) {
count[i] += count[i - 1];
}
for (int i = 0; i < n; ++i) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
for (int i = 0; i < n; ++i) {
arr[i] = output[i];
}
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void main(String[] args) {
int[] args1 = {1, 4, 1, 2, 7, 5, 2};
countingSort(args1);
}
}
九、桶排序
什么是桶排序济榨？
個(gè)人感覺桶排序還是比較好理解的坯沪。之所以叫"桶排序"，就是要根據(jù)一定的規(guī)則來(lái)將所有的數(shù)字分成幾組裝進(jìn)一個(gè)個(gè)的桶(數(shù)組)中,然后在再每個(gè)桶中對(duì)所有的數(shù)字進(jìn)行一個(gè)排序腿短，這個(gè)排序一般為插入排序屏箍。
那么這個(gè)規(guī)則是什么呢？
通過一個(gè)函數(shù) bindex = f (key )橘忱，key為數(shù)字大小赴魁，然后通過計(jì)算，得出每個(gè)數(shù)組屬于索引為bindex的桶钝诚。廢話不多說(shuō)颖御，直接上部分代碼：
int range = 10;
List<List<Integer>> temp = new ArrayList<List<Integer>>(range);
for (int i = 0; i < 10; i++) {
temp.add(new ArrayList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
temp.get(arr[i] / range).add(arr[i]);
}
System.out.println("排序前==============");
for (List<Integer> array : temp) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
這段函數(shù)的作用是通過bindex = key / 10來(lái)獲得每個(gè)相應(yīng)桶的索引bindex。
然后劃分好桶凝颇，并把數(shù)字裝進(jìn)去之后潘拱，再對(duì)每個(gè)桶進(jìn)行排序：
public static void insertSort(List<Integer> arr) {
arr.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 > o2) {
return 1;
}
else {
return -1;
}
}
});
}
這樣每個(gè)桶內(nèi)部排序完之后，再整體輸出拧略，就是一個(gè)遞增的數(shù)組啦芦岂！
完整的代碼：
package sortAlgorithm;
import java.util.*;
/**
* Created by Max on 2016/11/2.
*/
public class BucketSort {
/**
*桶排序
*時(shí)間復(fù)雜度O(n + k) ，n為數(shù)組長(zhǎng)度垫蛆，k為輸入數(shù)字的最大范圍
*/
public static void bucketSort(int[] arr) {
int range = 10;
List<List<Integer>> temp = new ArrayList<List<Integer>>(range);
for (int i = 0; i < 10; i++) {
temp.add(new ArrayList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
temp.get(arr[i] / range).add(arr[i]);
}
System.out.println("排序前==============");
for (List<Integer> array : temp) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
for (int i = 0; i < temp.size(); i++)
{
insertSort(temp.get(i));
}
System.out.println("排序后=========");
for (List<Integer> array : temp) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static void insertSort(List<Integer> arr) {
arr.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 > o2) {
return 1;
}
else {
return -1;
}
}
});
}
public static void swap(int[] args, int small, int big) {
int temp;
temp = args[big];
args[big] = args[small];
args[small] = temp;
}
public static void main(String[] args) {
int[] nums = {49, 38, 35, 97, 73, 76, 27, 49};
bucketSort(nums);
for (int i : nums) {
System.out.print(i + " ");
}
}
}
十禽最、基數(shù)排序
什么是基數(shù)排序？
基數(shù)排序的大致過程可以描述為：對(duì)于一組數(shù)字袱饭，首先根據(jù)每個(gè)數(shù)字的個(gè)位數(shù)字來(lái)將其劃分到0-9不等的臨時(shí)數(shù)組位置中川无，然后將劃分好的數(shù)字依次再寫入到一個(gè)新的數(shù)組中，接著進(jìn)行與第一步類似的操作虑乖，只不過這次是根據(jù)數(shù)字的十位來(lái)繼續(xù)劃分懦趋。接下來(lái)的過程依次類推，直到進(jìn)行到原數(shù)組中數(shù)字最大的那個(gè)最大數(shù)位疹味。接下來(lái)看一下部分源碼：
首先是選擇出最大數(shù)字的最大位是多少位：
private static int getMaxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int ele : arr) {
int len = (ele + "").length();
if (len > max) {
max = len;
}
}
return max;
}
然后根據(jù)這個(gè)最大位 maxBit 來(lái)進(jìn)行循環(huán)劃分:
int maxBit = getMaxBit(arr);
for (int i = 1; i <= maxBit; i++) {
List<List<Integer>> buf = distribute(arr, i);
collect(arr, buf);
}
具體的劃分方法:
private static List<List<Integer>> distribute(int[] arr, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for (int j = 0; j < 10; j++) {
buf.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
System.out.println(getNBit(arr[i], iBit));
buf.get(getNBit(arr[i], iBit)).add(arr[i]);
}
return buf;
}
每一次劃分完之后仅叫，都要將劃分好的數(shù)字再重新寫到原來(lái)的數(shù)組中(或者一個(gè)新的數(shù)組帜篇。新舊無(wú)所謂，存儲(chǔ)的只是一系列中間值)
private static void collect(int[] arr, List<List<Integer>> buf) {
int k = 0;
for (List<Integer> bucket : buf) {
for (int ele : bucket) {
arr[k++] = ele;
}
}
}
這樣整個(gè)循環(huán)結(jié)束之后惑芭，最后一次寫入到原數(shù)組中的數(shù)字序列就已經(jīng)是有序的啦
最后附上完整的源碼:
package sortAlgorithm;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* Created by Max on 2016/11/3.
*/
public class RadixSort {
/**
* 基數(shù)排序
* 時(shí)間復(fù)雜度為O(nlogn)
* @param arr
*/
public static void radixSort(int[] arr) {
if (arr == null && arr.length == 0) {
return;
} else {
int maxBit = getMaxBit(arr);
for (int i = 1; i <= maxBit; i++) {
List<List<Integer>> buf = distribute(arr, i);
collect(arr, buf);
}
}
}
private static List<List<Integer>> distribute(int[] arr, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for (int j = 0; j < 10; j++) {
buf.add(new LinkedList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
System.out.println(getNBit(arr[i], iBit));
buf.get(getNBit(arr[i], iBit)).add(arr[i]);
}
return buf;
}
private static void collect(int[] arr, List<List<Integer>> buf) {
int k = 0;
for (List<Integer> bucket : buf) {
for (int ele : bucket) {
arr[k++] = ele;
}
}
}
private static int getNBit(int x, int n) {
String sx = x + "";
if (sx.length() < n) {
return 0;
}
else {
// 由于charAt()方法返回值為char,要返回的類型為int坠狡，所以需要減去字符'0'，最后的結(jié)果即可int
return sx.charAt(sx.length() - n) - '0';
}
}
private static int getMaxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int ele : arr) {
int len = (ele + "").length();
if (len > max) {
max = len;
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {278, 109, 63, 930, 589, 184, 505, 269, 8, 83};
radixSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
后記：
算法是我在大一下學(xué)習(xí)的課程遂跟，不過自從學(xué)習(xí)之后，轉(zhuǎn)而做起了開發(fā)婴渡，所以算法這一部分都沒有被怎么使用上幻锁，荒廢了許久。臨近大三下边臼，為了響應(yīng)學(xué)校號(hào)召哄尔，也要開始找工作去實(shí)習(xí)了，所以為了能被公司看上柠并，特意又重新來(lái)回顧一下之前所學(xué)習(xí)過的各種排序算法岭接。不過到目前為止，這一次對(duì)算法的復(fù)習(xí)自我評(píng)價(jià)為良臼予，還算不上優(yōu)鸣戴，因?yàn)橹皇前迅鱾€(gè)算法的關(guān)鍵過程給重新梳理了一遍，但是針對(duì)算法的深入分析粘拾，比如時(shí)間復(fù)雜度窄锅，空間復(fù)雜度這兩塊，還沒有進(jìn)行任何的思考和學(xué)習(xí)缰雇。就目前復(fù)習(xí)過這十個(gè)排序算法而言入偷，感覺對(duì)算法的興趣不是特別大，可能對(duì)我來(lái)說(shuō)是因?yàn)楸容^難吧械哟。但是我始終應(yīng)該認(rèn)為疏之，算法是一種為我提供技術(shù)支持的工具，別把它當(dāng)做奧賽題那樣去解答暇咆，否則會(huì)很乏味锋爪。
