#import <Foundation/Foundation.h>
    /*
      選擇 插入 On2 時間復(fù)雜度
      插入排序 > 選擇排序
     */
    /*
     1.選擇排序
     
     選擇排序算法分為已排區(qū)間和未排區(qū)間,但是選擇排序每次會從未排序區(qū)間中找到最小的元素膜廊，將其放到已排區(qū)間的末尾师枣。
     選擇排序算法空間復(fù)雜度為O(1)，是一種原地排序算法卢肃，選擇排序最好的時間復(fù)雜度纤控、最壞和平均都是O(n2)
     選擇排序是一種不穩(wěn)定的排序算法畜隶。(稍差)
     
     */
    
    
    /*
     2.插入排序
      1.首先將數(shù)組中的數(shù)據(jù)分為兩個區(qū)間 已排區(qū)間和未排區(qū)間
      初始已排區(qū)間只有一個元素就是數(shù)組的第一個元素蒋譬。插入算法的核心思想就是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的
      插入位置將其插入揍诽，并保證已排序區(qū)間數(shù)據(jù)一直有序诀蓉。重復(fù)這個過程，直到未排序區(qū)間中元素為空暑脆。算法結(jié)束渠啤。
      2.兩種操作
             一種是元素的比較 一種是元素的移動
      3.移動操作次數(shù)總是固定的 等于逆序度
      4. 有序度和逆序度:
         有序度:是數(shù)組中具有有序關(guān)系的元素對的個數(shù)。
         滿有序度: n*(n-1)/2
         逆序度: 滿有序度 - 有序度
     */
    
    /*
     3.冒泡排序
      1.冒泡排序只會操作相鄰的兩個數(shù)據(jù)添吗，每次冒泡操作都會對相鄰的兩個元素進(jìn)行比較沥曹，看是否滿足大小關(guān)系，如果不滿足
     就讓他倆交換碟联。一次冒泡會讓至少一個元素移動到它應(yīng)該在的位置妓美。重復(fù)n次就完成了n個數(shù)據(jù)的排序工作。
     */
    
    /*
     分治算法
     分而治之玄帕，就是將原問題分割成同等結(jié)構(gòu)的子問題部脚，之后將子問題逐一解決后，原問題也得到解決裤纹。
     
     */
    
    
    /*
     4.歸并排序
     自頂向下歸并排序
     */
    void _merge(int arr[],int l,int mid,int r)
    {
        //將l和mid mid到r之間進(jìn)行merge
        int aux[r-l+1];
        for (int i=l; i<=r; i++) {
            aux[i-l] = arr[i];
        }
        int i = l,j = mid+1;
        for (int k=l; k<=r; k++) {
            //判斷索引
            if (i>mid) {
                arr[k] = aux[j-l];
                j++;
            }else if (j>r)
            {
                arr[k] = aux[i-l];
                i++;
            }else if (aux[i-l]<aux[j-l]) {
                arr[k] = aux[i-l];
                i++;
            }else
            {
                arr[k] = aux[j-l];
                j++;
            }
        }
    }
    
    void _mergerSort(int arr[],int l,int r)
    {
        if (l>=r) {
            return;
        }
        int mid = (l+r)/2;
        _mergerSort(arr, l, mid);
        _mergerSort(arr, mid+1, r);
        //優(yōu)化部分 無序才需要merge
        if (arr[mid]>arr[mid+1]) {
           _merge(arr, l, mid, r);
        }
    }
    
    void mergeSort(int arr[],int n)
    {
        _mergerSort(arr, 0, n-1);
    }
    
    /*
     自底向上歸并排序
     
     */
    void mergerSortBU(int arr[],int n)
    {
        for(int sz=1;sz<=n;sz+=sz)//sz 1 2 4 6 8
        {
            for(int i=0;i+sz<n;i+= sz+sz)
            {
                _merge(arr, i, i+sz-1, i+sz+sz-1);
            }
        }
    }
    
    
    /*
     快速排序
     1.選擇一個標(biāo)定點(diǎn)  分成兩塊
     最差的情況退化為O(n^2)
     nLogn
     */
    //返回p 使得arr[l...p-1]; arr[p+1,...r]>arr[p]
    int _partition(int arr[],int l,int r)
    {
        int x = random()%(r-l+1)+l;
        int v = arr[l];
         //arr[l+1,j]<v
        int j=l;
        for (int i=l+1; i<=r; i++) {
            if (arr[i]<=v) {
                //交換
                int tmp = arr[i];
                arr[i] = arr[j+1];
                arr[j+1] = tmp;
                j++;
                //增加小于V的數(shù)組大小
            }
        }
        //交換V的位置
        int tmp = arr[l];
        arr[l] = arr[j];
        arr[j] = tmp;
        return j;
    }
    
    
    void _quickSort(int arr[],int l,int r)
    {
        if (l-r <= 15) {
        
            return;
        }
        int p = _partition(arr, l, r);
        _quickSort(arr, l, p);
        _quickSort(arr, p+1, r);
        
    }
    
    
    
    
    void quickSort(int arr[],int n)
    {
        _quickSort(arr, 0, n);
    }
    
    void bubbleSort(int arr[],int n)
    {
        if (n<=1) {
            return;
        }
        for (int i=0; i<n; i++) {
            bool flag = false;//提前退出冒泡排序的標(biāo)志位
            for (int j=0; j<n-i-1; j++) {
                if (arr[j]>arr[j+1]) {
                    //交換
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
    
    
    void insertSort(int arr[],int n)
    {
       if(n<=1) return;
        for(int i=1;i<n;i++)
        {
            int value = arr[i];//制作一個副本
            int j = i-1;//插入的位置
            for (;j>=0; j--) {
                if (arr[j]>value) {
                    arr[j+1] = arr[j];
                }else
                {
                    break;
                }
            }
            arr[j+1] = value;
        }
        
    }
    
    
    void selectSort(int arr[], int n)
    {
        if (n<=1) {
            return;
        }
        
        for (int i=0; i<n; i++) {
            //1.確定一個最小的下標(biāo)
            int minIndex = i;
            for (int j=i+1; j<n; j++) {
                if (arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            //交換
            int tmp;
            tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    
    
    int _selectionPartition(int arr[],int l,int r)
    {
        int p = rand()%(r-l+1)+1;
        
        int tmp = arr[l];
        arr[l] = arr[p];
        arr[p] = tmp;
        
        int j = l;//[l+1...j]<p;[lt+1..i]>p
        for (int i=l+1; i<=r; i++) {
            if (arr[i]<arr[l]) {
                int tmp = arr[i];
                arr[i] = arr[j+1];
                arr[j+1] = tmp;
                j++;
            }
        }
        //交換V的位置
        int tmp1 = arr[l];
        arr[l] = arr[j];
        arr[j] = tmp1;
        return j;
    }
    
    int _selection(int arr[],int l,int r,int k)
    {
        if (l == r) {
            return arr[l];
        };
        int p = _selectionPartition(arr,l,r);
        if (k == p) {//如果k == p 直接返回arr[p]
            return arr[p];
        }else if (k<p)//如果k<p 只需要在arr[l..p-1]中查找第k小元素即可。
        {
            return _selection(arr, l, p-1,k);
        }else //如果 k > p, 則需要在arr[p+1...r]中找第k-p-1小元素
        {
            return _selection(arr, p+1, r, k);
        }
    }
    
    
    //求數(shù)組中范圍內(nèi)第K(小)大的數(shù)
    void shuffleArray(int arr[],int n,int k)
    {
        int k1 =  _selection(arr, 0, n-1, k);
        printf("k的值 == %d",k1);
    }
    
    
    
    
    
    
    
    
    
    
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            int a[10]={ 8,3,2,1,6,5,4,7,10,9 };
            quickSort(a, 10);
            for(int i=0;i<10;i++)
            {
                printf("%d ",a[i]);
        }
    }
    return 0;
}