排序 sort
===
###### tags: `Algorithm`

## Insetion sort

遍歷一個序列, 不斷把元素插入到左邊已經排序過的序列

#include<bits/stdc++.h>
using namespace std;

#define maxN 1000
int arr[maxN];

void insertion_sort( int len){
	for( int i=1; i<len; i++){
		int key = arr[i];
		int j;
		for( j=i-1; j>=0&&(arr[j]>key); j--){
			arr[j+1] = arr[j];
		}
		arr[j+1] = key;
	}	
}

## Merge sort

* 把區段切成 2 半, 分別排序後 merge 起來

* C++ 有提供 [merge](http://www.cplusplus.com/reference/algorithm/merge/) 函數

Template

#define maxN 100000

int arr[maxN];
int tmp[maxN];

inline void m_merge( int f, int r){

    int m = (f+r)>>1;
    int fi = f, ri = m, tmpi = f;

    while( fi<m || ri<r){
        if( ri==r || arr[fi]<arr[ri] && fi<m){
            tmp[tmpi++] = arr[fi++];
        }
        else{
            tmp[tmpi++] = arr[ri++];
        }
    }
    for( int i=f; i<r; i++){
        arr[i] = tmp[i];
    }
}
void msort( int f, int r){
    if( r-f<=1) return;
    int m = (f+r)>>1;
    msort( f, m);
    msort( m, r);
    m_merge( f, r);
}

## Quick sort

### 提示
遍歷找小 swap 到前面 -> 基準移到中間 -> 遞迴兩半
___
把比基準點小的移到左邊, 比基準點大的移到右邊
若排序 f 到 r
基準點: 需要再 f 上
* 取 f 第個, 或是取第 rand()%(r-f)+f 後 swap 到第 f 個
從 f 後開始找到如果比基準點小就 swap 到右邊

swap( arr[rand()%(r-f)], arr[f]);

cout << arr[f] << "\n\n";
int j=f;
for( int i=f; i<r; i++){
    if( arr[i] < arr[f]){
        swap( arr[++j], arr[i]);
    }
}
swap( arr[f], arr[j]); // 要把基準點 swap 到大小交接處

遞迴左邊和右邊, 記得不包含基準點

void qsort( int f, int r){
	if( r-f <=1) return;
	swap( arr[rand()%(1)+f], arr[f]);
	
	int j=f;
	for( int i=f; i<r; i++){
		if( arr[i] < arr[f]){
			swap( arr[++j], arr[i]);
		}
	}
	swap( arr[f], arr[j]);
	
	qsort( f, j);
	qsort( j+1, r);
}

## Stable Sort 穩定排序, Sort by Index

如果排序後能保持相等元素的先後順序, 我們稱為穩定排序
如果需要用不穩定排序法穩定排序, 我們可以 ***sort by index***

#include<bits/stdc++.h>
using namespace std;
#define maxN (1000)

int arr[maxN], id[maxN];

bool cmp( const int &a, const int &b){
	return (arr[a]==arr[b])? (a<b) : arr[a]<arr[b];
}

int main(){
	
	for( int i=0; i<maxN; i++){
		arr[i] = rand();
		id[i] = i;
	}
	
	sort( id, id+maxN, cmp);
	
	for( int i=0; i<maxN; i++){
		cout << arr[ id[i]] << '\n';
	}
}

## Unique

### 提示
排序 -> 找到下一個不一樣的並 push_back
___

#define maxN 1000
int arr[maxN];
int u[maxN];

int uniq(){
    sort(arr,arr+maxN);
    int ai=0, ui=0;
    while(ai+1<maxN){
        for( ; arr[ai]==arr[ai+1]&&ai+1<maxN; ai++);
        u[ui++]=arr[ai++];
    }
    return ui; // size of u
}

## 字典序

### 提示

遍歷兩個直到比出大小,
如果完全一樣(其中一個是前綴)就比較長度

bool cmp( string a, string b){
    int len=min(a.size(),b.size());
    for( int i=0; i<len; i++){
        if( a[i]<b[i]) return true;
        if( a[i]>b[i]) return false;
    }
    return a.size()<b.size();
}

### ref