排序算法
基本方法忠寻，交換和比較：
public abstract class Sort<T extends Comparable<T>> {
public abstract void sort(T[] nums);
protected boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
protected void swap(T[] nums, int i, int j) {
T tmp = T[i];
T[i] = T[j];
T[j] = tmp;
}
}
選擇排序
public class Selection<T> extends Sort< T> {
@Override
public void sort(T[] nums) {
int size = nums.length;
for (int i = 0; i < size; i++) {
int less = i;
for (int j = i; j < size; j++) {
if (less(nums[j], nums[less])) {
less = j;
}
}
swap(nums, i, less);
}
}
}
不穩(wěn)定惧浴。{5,5,2}就不穩(wěn)定。
插入排序
public class Insertion<T> extends Sort<T> {
@Override
public void sort(T[] nums) {
int size = nums.length;
for (int i = 1; i < size; i++) {
for (int j = i; j > 0 & less(T[j], T[j - 1]); j--) {
swap(nums, j, j - 1);
}
}
}
}
可穩(wěn)定奕剃。等于不再交換衷旅，所以可穩(wěn)定。
冒泡排序
public class Bubble<T> extends Sort<T> {
@Override
public void sort(T[] nums) {
int size = nums.length;
boolean hasSorted = false;
for (int i = 0; i < size && !hasSorted; i++) {
hasSorted = true;
for (int j = 0; j < size - i - 1; j++){
if (less(T[j+1], T[j])) {
hasSorted = false;
swap(nums, j+1, j);
}
}
}
}
}
可穩(wěn)定纵朋。等于不再交換柿顶，所以可穩(wěn)定。
合并排序
方法解析：
https://blog.csdn.net/u010853261/article/details/54894057
public class Merge<T> extends Sort<T> {
@Override
public void sort(T[] nums) {
}
// recursive, from top to bottom.
public void sort(T[] nums, int l, int r) {
if (l >= r>) {
return;
}
int m = (l + r) / 2;
sort(nums, l, m);
sort(nums, m, r);
merge(nums, l, m, r);
}
public void merge(T[] nums, int l, int m, int h) {
T[] tmps = new T[nums.length];
//Arrays.copyOf();
int i = l;
int j = m + 1;
int k = 0;
while (i < m && j < h>) {
if (less(tmps[i], tmps[j])) {
nums[k++] = tmps[i++];
} else {
nums[k++] = tmps[j++];
}
}
while (i < m) {
nums[k++] = tmps[i++];
}
while (j < h) {
nums[k++] = tmps[j++];
}
}
// none recursive. from bottom to top
@Override
public void sort(T[] nums) {
int N = nums.length;
aux = (T[]) new Comparable[N];
for (int sz = 1; sz < N; sz += sz)
for (int lo = 0; lo < N - sz; lo += sz + sz)
merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
可穩(wěn)定操软。合并過程中我們可以保證如果兩個當前元素相等時嘁锯，我們把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩(wěn)定性。
快速排序
快速排序幾種寫法：
https://blog.csdn.net/wusecaiyun/article/details/47862897
int mypartition(vector<int>&arr, i nt low, int high)
{
int pivot = arr[low];//選第一個元素作為樞紐元
int location = low;//location指向比pivot小的元素段的尾部
for(int i = low+1; i <= high; i++)//比樞紐元小的元素依次放在前半部分
if(arr[i] < pivot)
swap(arr[i], arr[++location]);
swap(arr[low], arr[location]);//注意和前面的區(qū)別家乘，是為了保證交換到頭部的元素比pivot小
return location;
}
void quicksort(vector<int>&arr, int low, int high)
{
if(low < high)
{
int middle = mypartition(arr, low, high);
quicksort(arr, low, middle-1);
quicksort(arr, middle+1, high);
}
}
public class Quick<T> extends Sort<T> {
@Override
public void sort(T[] nums) {
sort(nums, 0, nums.length - 1);
}
public void sort(T[] nums, int l, int r) {
if (l >= r>) {
return;
}
int j = partition(nums, l, r);
sort(nums, i, j - 1);
sort(nums, j + 1, r);
}
public void partition(T[] nums, int l, int r) {
T v = nums[l];
int i = l;
int j = r + 1;
while (true) {
while (less(nums[++i], v) && i != r);
while (less(v, nums[--j]) && j != l);
if (i > j) break;
swap (nums, i, j);
}
swap (nums, l, j);
return j;
}
}
不穩(wěn)定蝗羊。因為后邊的數(shù)字可能會被交換到前邊。
如果元素較少仁锯，那么采用插入排序可以節(jié)省性能耀找。
為避免元素基準點選擇不均勻，那么可以采用三數(shù)取中作為基準业崖。有關樞紐值的選取有很多種思路野芒，隨機選取
public class ThreeMidQuick<T> extends Quick<T> {
@overide
public void sort(T[] nums, int l, int r) {
if (l >= r>) {
return;
}
selectMidToFirst(nums, l, r);
int j = partition(nums, l, r);
sort(nums, i, j - 1);
sort(nums, j + 1, r);
}
private void selectMidToFirst(T[] nums, int l, int r) {
int mid = (l + r) > 2;
if (less(nums, mid, l) && less(nums, l, r)) {
return; //mid->l， no swap.
}
if (less(nums, l, mid) && less(nums, mid, r)) {
swap(nums, l, mid); // mid -> mid, swap(l, mid)
return;
}
swap(nums, l, r); // mid -> r, swap(l, r)
}
}
如果有很多重復的元素双炕，那么可以使用三分法狞悲，如下講數(shù)組分拆為三部分，< = >的部分妇斤。然后對< 和 > 再進行quicksort即可摇锋，如下：
public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> {
@Override
protected void sort(T[] nums, int l, int h) {
if (h <= l)
return;
int lt = l, i = l + 1, gt = h;
T v = nums[l];
while (i <= gt) {
int cmp = nums[i].compareTo(v);
if (cmp < 0)
swap(nums, lt++, i++);
else if (cmp > 0)
swap(nums, i, gt--);
else
i++;
}
sort(nums, l, lt - 1);
sort(nums, gt + 1, h);
}
}
查找數(shù)組的第K大元素
快速排序的 partition() 方法，會返回一個整數(shù) j 使得 a[l..j-1] 小于等于 a[j]站超，且 a[j+1..h] 大于等于 a[j]乱投，此時 a[j] 就是數(shù)組的第 j 大元素。
可以利用這個特性找出數(shù)組的第 k 個元素顷编。
public T select(T[] nums, int k) {
int l = 0, h = nums.length - 1;
while (h > l) {
int j = partition(nums, l, h);
if (j == k)
return nums[k];
else if (j > k)
h = j - 1;
else
l = j + 1;
}
return nums[k];
}
該算法是線性級別的戚炫，因為每次正好將數(shù)組二分，那么比較的總次數(shù)為 (N+N/2+N/4+..)媳纬，直到找到第 k 個元素双肤，這個和顯然小于 2N。
堆排序
http://www.cnblogs.com/penghuwan/p/7894728.html
構建堆
從左到右钮惠，依次上该┟印；
從右一半到左素挽， 依次下沉蔑赘。(更高效, 因為“下沉”需要遍歷的節(jié)點數(shù)比“上浮”需要遍歷的節(jié)點數(shù)少了一半)
int N = nums.length;
for (int i = N/2; i >= 1; i--) {
sink(nums, i, N); //大根堆
}
單個堆節(jié)點的有序化有兩種情況：
當某個節(jié)點變得比它的父節(jié)點更大而被打破（或是在堆底加入一個新元素時候），我們需要由下至上恢復堆的順序
當某個節(jié)點的優(yōu)先級下降（例如预明，將根節(jié)點替換為一個較小的元素）時缩赛，我們需要由上至下恢復堆的順序
實現(xiàn)這兩種有序化的操作，分別叫做“上浮”（swim）和“下沉” （sink）
選擇元素撰糠，每次確定一個N酥馍， N-1，然后交換到頂端阅酪，從1開始下沉旨袒。所以最終只需要使用下沉操作即可汁针。算法如下：
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
/**
* 數(shù)組第0個位置不能有元素
*/
@Override
public void sort(T[] nums) {
int N = nums.length;
for (int i = N/2; i >= 1; i--) {
sink(nums, i, N); //大根堆
}
while (N > 1) {
swap(nums, 1, N--); // 每一次確定一個N, N-1, N-2...1
sink(nums, 1, N);
}
}
private void sink(T[] nums, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(nums, j, j + 1))
j++;
if (!less(nums, k, j))
break;
swap(nums, k, j);
k = j;
}
}
private boolean less(T[] nums, int i, int j) {
return nums[i].compareTo(nums[j]) < 0;
}
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
}
}
public void insert(Comparable v) {
heap[++N] = v;
swim(N);
}
public T delete() {
swap(nums, 1, N--); // 每一次確定一個N, N-1, N-2...1
sink(nums, 1, N);
}
}
堆排序的復雜度
一個堆的高度為 logN，因此在堆中插入元素和刪除最大元素的復雜度都為 logN砚尽。
對于堆排序施无，由于要對 N 個節(jié)點進行下沉操作，因此復雜度為 NlogN必孤。
堆排序時一種原地排序帆精，沒有利用額外的空間。
現(xiàn)代操作系統(tǒng)很少使用堆排序隧魄，因為它無法利用緩存，也就是數(shù)組元素很少和相鄰的元素進行比較隘蝎。
排序穩(wěn)定性和復雜度問題
- 排序算法的比較
算法 穩(wěn)定 時間復雜度 空間復雜度 備注
選擇排序 no N2 1
冒泡排序 yes N2 1
插入排序 yes N ~ N2 1 時間復雜度和初始順序有關
希爾排序 no N 的若干倍乘于遞增序列的長度 1
快速排序 no NlogN logN
三向切分快速排序 no N ~ NlogN logN 適用于有大量重復主鍵
歸并排序 yes NlogN N
堆排序 no NlogN 1
快速排序是最快的通用排序算法购啄，它的內循環(huán)的指令很少，而且它還能利用緩存嘱么，因為它總是順序地訪問數(shù)據(jù)狮含。它的運行時間近似為 ~cNlogN，這里的 c 比其他線性對數(shù)級別的排序算法都要小曼振。使用三向切分快速排序几迄，實際應用中可能出現(xiàn)的某些分布的輸入能夠達到線性級別，而其它排序算法仍然需要線性對數(shù)時間冰评。
- Java 的排序算法實現(xiàn)
Java 主要排序方法為 java.util.Arrays.sort()映胁，對于原始數(shù)據(jù)類型使用三向切分的快速排序，對于引用類型使用歸并排序甲雅。
穩(wěn)定行分析：
https://blog.csdn.net/DeepLies/article/details/52593597
https://blog.csdn.net/weiwenhp/article/details/8621049
其他種排序思路
https://www.cnblogs.com/ECJTUACM-873284962/p/6935506.html#autoid-1-1-0
https://www.cnblogs.com/ttltry-air/archive/2012/08/04/2623302.html
桶排序
分成若干個有序的區(qū)間桶解孙，每個區(qū)間單獨排序，然后串聯(lián)起來即可抛人。
[圖片上傳失敗...(image-eb7532-1533265888436)]
基數(shù)排序
看基數(shù)弛姜，比如10進制數(shù)那么就有10個數(shù)組鏈表，類似hashmap妖枚，然后進行個位數(shù)廷臼，十位數(shù)，百位數(shù)...等k次全數(shù)組遍歷绝页，每次都從0-10數(shù)組鏈表開始遍歷荠商，每個萬位到最大數(shù)即可。
1 pass #0: 170 45 75 90 2 24 802 66
2 pass #1: 170 90 2 802 24 45 75 66
3 pass #2: 2 802 24 45 66 170 75 90
4 pass #3: 2 24 45 66 75 90 170 802
