排序

    #import <Foundation/Foundation.h>
    /*
      选择 插入 On2 时间复杂度
      插入排序 > 选择排序
     */
    /*
     1.选择排序
     
     选择排序算法分为已排区间和未排区间,但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排区间的末尾。
     选择排序算法空间复杂度为O(1)，是一种原地排序算法，选择排序最好的时间复杂度、最坏和平均都是O(n2)
     选择排序是一种不稳定的排序算法。(稍差)
     
     */
    
    
    /*
     2.插入排序
      1.首先将数组中的数据分为两个区间 已排区间和未排区间
      初始已排区间只有一个元素就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的
      插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空。算法结束。
      2.两种操作
             一种是元素的比较 一种是元素的移动
      3.移动操作次数总是固定的 等于逆序度
      4. 有序度和逆序度:
         有序度:是数组中具有有序关系的元素对的个数。
         满有序度: n*(n-1)/2
         逆序度: 满有序度 - 有序度
     */
    
    /*
     3.冒泡排序
      1.冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系，如果不满足
     就让他俩交换。一次冒泡会让至少一个元素移动到它应该在的位置。重复n次就完成了n个数据的排序工作。
     */
    
    /*
     分治算法
     分而治之，就是将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也得到解决。
     
     */
    
    
    /*
     4.归并排序
     自顶向下归并排序
     */
    void _merge(int arr[],int l,int mid,int r)
    {
        //将l和mid mid到r之间进行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);
        //优化部分 无序才需要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.选择一个标定点  分成两块
     最差的情况退化为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的数组大小
            }
        }
        //交换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;//提前退出冒泡排序的标志位
            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.确定一个最小的下标
            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);
        }
    }
    
    
    //求数组中范围内第K(小)大的数
    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;
}