#快速排序:
---
* 背景介紹: 又稱劃分交換排序(partition-exchange sort),一種排序算法,最早由東尼·霍爾提出。在平均狀況下,排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他Ο(n log n)算法更快,因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來 ----- 來自 [wikipedia](https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F) **
* 算法規則: 本質來說,快速排序的過程就是不斷地將無序元素集遞歸分割,一直到所有的分區只包含一個元素為止。 <br> 由于快速排序是一種分治算法,我們可以用分治思想將快排分為三個步驟:<br> 1.分:設定一個分割值,并根據它將數據分為兩部分<br> 2.治:分別在兩部分用遞歸的方式,繼續使用快速排序法 <br> 3.合:對分割的部分排序直到完成
* 代碼實現(Java版本)
```
public int dividerAndChange(int[] args, int start, int end)
{
//標準值
int pivot = args[start];
while (start < end) {
// 從右向左尋找,一直找到比參照值還小的數值,進行替換
// 這里要注意,循環條件必須是 當后面的數 小于 參照值的時候
// 我們才跳出這一層循環
while (start < end && args[end] >= pivot)
end--;
if (start < end) {
swap(args, start, end);
start++;
}
// 從左向右尋找,一直找到比參照值還大的數組,進行替換
while (start < end && args[start] < pivot)
start++;
if (start < end) {
swap(args, end, start);
end--;
}
}
args[start] = pivot;
return start;
}
public void sort(int[] args, int start, int end)
{
//當分治的元素大于1個的時候,才有意義
if ( end - start > 1) {
int mid = 0;
mid = dividerAndChange(args, start, end);
// 對左部分排序
sort(args, start, mid);
// 對右部分排序
sort(args, mid + 1, end);
}
}
private void swap(int[] args, int fromIndex, int toIndex)
{
args[fromIndex] = args[toIndex];
}
```
- JavaSE(Java基礎)
- Java基礎知識
- Java中的內存泄漏
- String源碼分析
- Java集合結構
- ArrayList源碼剖析
- HashMap源碼剖析
- Hashtable簡介
- Vector源碼剖析
- LinkedHashMap簡介
- LinkedList簡介
- JVM(Java虛擬機)
- JVM基礎知識
- JVM類加載機制
- Java內存區域與內存溢出
- 垃圾回收算法
- Java并發(JavaConcurrent)
- Java并發基礎知識
- 生產者和消費者問題
- Thread和Runnable實現多線程的區別
- 線程中斷
- 守護線程與阻塞線程的情況
- Synchronized
- 多線程環境中安全使用集合API
- 實現內存可見的兩種方法比較:加鎖和volatile變量
- 死鎖
- 可重入內置鎖
- 使用wait/notify/notifyAll實現線程間通信
- NIO
- 數據結構(DataStructure)
- 數組
- 棧和隊列
- Algorithm(算法)
- 排序
- 選擇排序
- 冒泡排序
- 快速排序
- 歸并排序
- 查找
- 順序查找
- 折半查找
- Network(網絡)
- TCP/UDP
- HTTP
- Socket
- OperatingSystem(操作系統)
- Linux系統的IPC
- android中常用設計模式
- 面向對象六大原則
- 單例模式
- Builder模式
- 原型模式
- 簡單工廠
- 策略模式
- 責任鏈模式
- 觀察者模式
- 代理模式
- 適配器模式
- 外觀模式
- Android(安卓面試點)
- Android基礎知識
- Android內存泄漏總結
- Handler內存泄漏分析及解決
- Android性能優化
- ListView詳解
- RecyclerView和ListView的異同
- AsyncTask源碼分析
- 插件化技術
- 自定義控件
- ANR問題
- Art和Dalvik的區別
- Android關于OOM的解決方案
- Fragment
- SurfaceView
- Android幾種進程
- APP啟動過程
- 圖片三級緩存
- Bitmap的分析與使用
- 熱修復的原理
- AIDL
- Binder機制
- Zygote和System進程的啟動過程
- Android中的MVC,MVP和MVVM
- MVP
- Android開機過程
- EventBus用法詳解
- 查漏補缺
- Git操作