-
寫(xiě)在之前
-
代碼實(shí)現(xiàn) Java
-
設(shè)計(jì)模式 策略模式
// 接口定義
public interface Sorter {
public void sort(int []data);
}
// 測(cè)試入口函數(shù)
public static void main(String[] args) {
int []data = new int[] {2,5,6,3,4,6,1,8,9,12,56,4,3,7,9,6,8};
Sorter sorter = new //具體實(shí)現(xiàn)類
sorter.sort(data);
for(int i:data) {
System.out.println(i);
}
}
-
冒泡排序
似乎是這個(gè)世界上最簡(jiǎn)單的排序算法，很多Coder最初學(xué)會(huì)的排序算法， 簡(jiǎn)單思路清晰，通過(guò)一次次的循環(huán)找出最值元素將其浮到“邊界”，因其過(guò)程十分相似冒泡，就得到了這個(gè)十分形象的名字。
public class BubbleSort implements Sorter{
@Override
public void sort(int[] data) {
for(int i=0; i<data.length;i++) {
for(int j=0; j<i;j++) {
if(data[i] > data[j]) {
//交換 data[i]和data[j]的值 當(dāng)時(shí)突然想起了怎么在不引入中間變量交換值 0.0
data[i] = data[i]^data[j];
data[j] = data[i]^data[j];
data[i] = data[i]^data[j];
}
}
}
}
}
- 時(shí)間復(fù)雜度 O(n^2)
- 空間復(fù)雜度 O(1) （霧 如果這樣寫(xiě)明明是0
- 穩(wěn)定的排序
-
直接插入排序
一種簡(jiǎn)單暴力排序算法，將待排序的數(shù)字依次插入一個(gè)有序數(shù)組中，平時(shí)很少用到，反而在一些往已經(jīng)有序的數(shù)組插入數(shù)據(jù)的場(chǎng)合使用。
public class InsertionSort implements Sorter{
@Override
public void sort(int[] data) {
for(int i=0; i<data.length; i++) {
for(int j = i-1;j>=0;j--) {
if(data[j] > data[j+1]) {
int temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
}else {
break;
}
}
}
}
}
- 時(shí)間復(fù)雜度 O(n^2)
- 空間復(fù)雜的有 O(1)
-
穩(wěn)定 的排序
相比于冒泡排序沒(méi)什么優(yōu)點(diǎn) 還多了一句 怪不得很少人使用。
-
歸并排序
一種思想簡(jiǎn)單，且具有魔力的排序，使用分治的思想 先拆分?jǐn)?shù)據(jù)為2部分 分別保證左邊和右邊同樣有序 再將其有序地歸并起來(lái)，其實(shí)簡(jiǎn)而言之，我覺(jué)得歸并排序本身就是在不停地拆和并。使用的情景非常豐富，是一種高效的排序手段。
- 簡(jiǎn)單舉例
8,13,9,12,56,4,3,7,12;
拆成子元素
8 9 56 3 12
13 12 4 7
第一趟歸并
8 13 4 56 12
9 12 3 7
第二趟
8 9 12 13 12
3 4 7 56
//中間略歸并一步
3 4 7 8 9 12 12 13 56
public class MergcSort implements Sorter{
@Override
public void sort(int[] data) {
int[] temp = new int[data.length]
mergcSort(0, data.length-1, data,temp);
}
private void mergcSort(int left,int right,int[]data,int []temp) {
if(left == right) {
//當(dāng)拆分到只有一個(gè)元素的時(shí)候當(dāng)然有序咯
return;
}
// 拆拆拆
int mid = (left+right)/2;
// 遞歸拆左邊
mergcSort(left, mid, data);
// 遞歸拆右邊
mergcSort(mid+1, right, data);
int x = left,y = mid +1,loc =left;
while(x<=mid || y<=right) {
if(x <= mid &&(y>right||data[x] < data[y])) {
//分2種情形
//1. x <= mid && y <= right 這時(shí)候data[x] 的值小于data[y] 按照原則 誰(shuí)小誰(shuí)上
//2. x <= mid && y > right 即右邊的已經(jīng)全部填充到數(shù)組里了 這時(shí)候只好填左邊的了
temp[loc] = data[x];
x++;
}else {
temp[loc] = data[y];
y++;
}
loc++;
}
// 毫無(wú)技巧地將中間數(shù)組的值填充回來(lái)
for(int i=left;i<=right;i++) {
data[i] = temp[i];
}
}
- 時(shí)間復(fù)雜度O(n*log(n))
- 空間復(fù)雜度 O(n)
- 穩(wěn)定的排序
-
快速排序
強(qiáng)大的排序，是最常用的排序算法之一（目測(cè)要是是穩(wěn)定排序的話使用會(huì)更豐富），快速排序其實(shí)非常簡(jiǎn)單 簡(jiǎn)單來(lái)說(shuō)就是不斷挖坑和填坑的過(guò)程，特點(diǎn)排序效率高，空間復(fù)雜度低，非常難得。
- 簡(jiǎn)單舉例
8,13,9,12,56,4,3,7,12;
選取哨兵 簡(jiǎn)單取第一位挖掉 【】表示新填充 （）代表挖掉了 哨兵 = 8；
（8） 13 9 12 56 4 3 7 12 ； 挖掉哨兵
#1【7】 13 9 12 56 4 3 （7） 12 從右搜索第一個(gè)小于8的 挖掉并填充到上次挖的地方 7
#2 7 （13） 9 12 56 4 3 【13】 12 從左搜索第一個(gè)大于8的 挖掉填充到上次挖的地方 13
7 【3】9 12 56 4 （3）13 12 重復(fù)#1
7 3 （9）12 56 4 【9】 13 12 #2
7 3 【4】 12 56 （4） 9 13 12 。。。
7 3 4 （12） 56 【12】 9 13 12
最后左右重逢了 填充哨兵到相逢的地方
7 3 4 8 56 12 9 13 12
遞歸處理左右
[ 7 3 4 ] 8 [56 12 9 13 12]
......
- 代碼實(shí)現(xiàn)
public class QuickSort implements Sorter{
@Override
public void sort(int[] data) {
quickSort(0, data.length-1, data);
}
private void quickSort(int left,int right,int []data) {
if(right <= left) {
return;
}
int x = left,y = right;
int temp = data[x];
while(x < y) {
while(y > x && data[y] > temp) {
y--;
}
if(y > x) {
data[x++]=data[y];
}
while(x < y && data[x] < data[y]) {
x++;
}
if(x < y) {
data[y--] = data[x];
}
}
data[x] = temp;
quickSort(left, x-1, data);
quickSort(x+1, right, data);
}
}
聽(tīng)起來(lái)好像很復(fù)雜 實(shí)際實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單 其中2個(gè)if是為了保證左右指針不重逢 畢竟重逢意味著填充哨兵，本次排序的結(jié)束和分治的開(kāi)始
- 時(shí)間復(fù)雜度O(n*log(n))
- 空間復(fù)雜度 O(1)
- 不穩(wěn)定的排序
-
堆排序
STL中優(yōu)先隊(duì)列的底層實(shí)現(xiàn)，雖然在一次排序上表現(xiàn)不夠優(yōu)秀，但是非常適合那種不停地插入和取出最值的情景，堆排序事實(shí)上是最大堆或者最小堆，屬于樹(shù)形結(jié)構(gòu)這里我就簡(jiǎn)單寫(xiě)一個(gè)堆，接下來(lái)不適合0基礎(chǔ)的人查看。
public class Heap {
private int[] data;
private int size;
public Heap(int size) {
data = new int[size];
size = 0;
}
//得到堆頂元素
public int getTop() {
return data[0];
}
// 入堆
// 將入堆元素放到堆末尾 再?gòu)牡投献鲆淮尉S護(hù)
public void push(int input) {
int current = size;
data[current] = input;
// 計(jì)算 父節(jié)點(diǎn)的位置
int father = (current - 1) / 2;
// 維護(hù) 這里保證堆中所有的兒子都比父親大 否則就交換位置 繼續(xù)向上維護(hù)
while (data[current] < data[father]) {
data[current] = data[current] ^ data[father];
data[father] = data[current] ^ data[father];
data[current] = data[current] ^ data[father];
current = father;
father = (father - 1) / 2;
}
size++;
}
// 最值元素出堆 首先將要出堆的元素交換到末尾 再頂定而下做一次維護(hù)
public int pop() {
int temp = data[0];
data[0] = data[size-1];
data[size-1] = temp;
size--;
update(0,size);
return data[size];
}
//自定而下維護(hù)函數(shù) 如果發(fā)現(xiàn)子節(jié)點(diǎn)大于父節(jié)點(diǎn)的值交換位置 再?gòu)男鹿?jié)點(diǎn)位置繼續(xù)維護(hù) 專業(yè)的叫法叫 沉底
private void update(int pos,int size) {
int lchild = pos*2+1;
int rchild = pos*2+2;
int min_pos = pos;
if(lchild < size && data[lchild] < data[min_pos]) {
min_pos = lchild;
}
if(rchild < size && data[rchild] <data[min_pos]) {
min_pos = rchild;
}
if(pos != min_pos) {
int temp = data[pos];
data[pos] = data[min_pos];
data[min_pos] = temp;
update(min_pos, size);
}
}
}
- 時(shí)間復(fù)雜度O(n*log(n))
- 空間復(fù)雜度 O(1)
- 不穩(wěn)定的排序
