快速排序

枢纽元素为首位元素 时间:平均O(nlog(n)),最差:O(n^2),顺序的时候 空间:O(1)

int Partition(int A[],int L,int R) {
    int pivot=A[L];
    while(L<R) {
        while(L<R&&A[R]>=pivot) R--;
        A[L]=A[R];
        while(L<R&&A[L]<=pivot) L++;
        A[R]=A[L];
    }
    A[L]=pivot;
    return L;
}
void QuickSort(int A[],int L,int R) {
    if(L>=R) return ;
    int mid=Partition(A,L,R);
    QuickSort(A,L,mid-1);
    QuickSort(A,mid+1,R);
}

利用快速排序，找出数组中第k小的元素

时间:O(n) 空间:O(1)

int Partition(int A[],int L,int R) {
    int pivot=A[L];
    while(L<R) {
        while(L<R&&A[R]>=pivot) R--;
        A[L]=A[R];
        while(L<R&&A[L]<=pivot) L++;
        A[R]=A[L];
    }
    A[L]=pivot;
    return L;
}
int fun(int A[],int L,int R,int k) {
    while(1) {
        int M=Partition(A,L,R);
        if(M+1==k) break;
        else if(M+1>k) R=M-1;
        else if(M+1<k) L=M+1;
    }
    return A[k-1];
}

归并排序思想合并两个有序数组 时间:O(N+M) 空间:O(N+M)

void Merge(int A[],int N,int B[],int M,int C) {
    int i=0,j=0,k=0;
    while(i<N&&j<M) {
        if(A[i]<=B[j]) C[k++]=A[i++];
        else C[k++]=B[j++];
    }
    while(i<N) C[k++]=A[i++];
    while(j<M) C[k++]=B[j++];
}