无题

初始调用 MergeSort(A,1,n)
function MergeSort(A,l,r){
	if left<= right{
		return A[left...right]
	}
	mid<-(l+r)/2
	MergeSort(A,l,mid)
	MergeSort(A,mid+1,r)
	Merge(A,l,mid,r)
	return A[left...right]
}

function Merge(A,left,mid,right){
	A'[left...right]复制A[left...right]
	i<-left
	j<-mid+1
	k<-left
	while i<= mid and j<= right{
		if(A'[i]<=A'[j]){
			A[k]=A'[i]
			k++;i++;
		}else{
			A[k]=A'[j]
			k++;j++;
		}
	}
	//剩余元素按序添加
	while(i<=mid){
		A[k]=A'[i]
		k++
	}
	while(j<=right){
		A[k]=A'[j]
		k++
	}
	return A
}

function qsort(A,l,r){
	if l<r{
        q<-partion(A,l,r)
        qsort(A,l,q-1)
        qsort(A,q+1,r)
	}
}

function qartion(A,l,r){
	//我想要随机化
	s<-random(l,r)
	exchange A[s] with A[r]
	i<-l-1
	j<-l
	while j:l->r-1{
		if(A[j]<A[r]){
			exchange A[i+1] with A[j]
		}
	}
	exchange A[i+1] with A[r]
	return i+1
}

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap-szie = A.heap-size - 1
        MAX-HEAPIFY(A,1)
        
MAX-HEAPIFY(A,i)
    l = LEFT(i)    // 取该节点的左儿子节点
    r = RIGHT(i)    // 取该节点的右儿子节点
    if l<=A.heap-size and A[l] > A[i]
        largest = l
    else
        largest = i
    if r<=A.heap-size and A[r] > A[largest]
        largest = r
    if largest ! = i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A,largest)

function InsertSort(A,n){
	for i:2->n{
		key<-A[i]
		j=i-1
		while j>=1 and key<A[j]{
			A[j+1]=A[j]
			j--;
		}
		A[j+1]=hey;
	}
}

for i:1->n-1{
	key = A[i]
	index = i
	for j:i+1->n{
        if(key>A[j]){
			key = A[j]
			index = j
        }
	}
	exchange A[i] with A[index]
}

function maxSubArray(A,l,r){
    if l>=r{
		return A[l]
    }
    mid = [(l+r)/2]
    S1 = maxSubArray(A,l,mid)
    S2 = maxSubArray(A,mid+1,r)
    S3 = merge(A,l,mid,r)
    return max(S1,S2,S3)
}

function merge(A,l,mid,r){
	//计算跨越中点 mid 的子数组的最大和
	sumL = negative infinity
    sumR = negative infinity
    maxSum = negative infinity
    i = mid
    j = mid + 1
    totalSum = 0
    while i >= l
        totalSum = totalSum + A[i]
        if totalSum > sumL
            sumL = totalSum
        i = i - 1
    while j <= r
        totalSum = totalSum + A[j]
        if totalSum > sumR
            sumR = totalSum
        j = j + 1
    return sumL + sumR
}

function IntervalCount(A,l,r){
 	if l>=r{
		return 0
    }
    mid = [(l+r)/2]
    S1 = maxSubArray(A,l,mid)
    S2 = maxSubArray(A,mid+1,r)
    S3 = merge(A,l,mid,r)
    return S1+S2+S3
}

function merge(A,l,mid,r){
	A'[left...right]复制A[left...right]
	i<-left
	j<-mid+1
	k<-left
	sum <- 0;
	while i<= mid and j<= right{
		if(A'[i]<=A'[j]){
			A[k]=A'[i]
			k++;i++;
		}else{
			A[k]=A'[j]
			//j相对于前半部分的逆序对
			sum += mid-i-1
			k++;j++;
		}
	}
	//剩余元素按序添加
	while(i<=mid){
		A[k]=A'[i]
		k++
	}
	while(j<=right){
		A[k]=A'[j]
		k++
	}
	return sum

}

function mult(A[x],B[x]){
 	S1<-mult(A0[x],B0[x])
 	S2<-mult(A1[x],B1[x])
 	S3<-mult(A0[x]+B0[x],A1[x]+B1[x])
    return S1+(S3-S1-S2)X^n/2+S3x^n
}

function buildHeap(A,n){
	for i:n/2->1{
		max-heap(A,i)
	}
}
function max-heap(A,i){
	left<-left(i)
	right<-right(i)
	key<-i//最大值
	if l<n and A[l]>A[i]{
		key<- l
	}
	if right<n and A[r]>A[key]{
		key<- r
	}
	if key != i{
		exchange A[key] with A[i]
		max-heap(A,key)
	}
}

function HeapSort(A,n){
	 buildHeap(A,n)
	 for i:n->2{
	 	exchange A[1]->A[i]
	 	A.size --;
	 	max-heap(A,1)
	 }
}

function kselect(A,k){
	if |k| <5{
		升序排序后返回第五个
	} 
	
	5个一组分成m=[n/5]组
	每组的中位数加入到M中
	m*<-kselect(M,m)
	根据m*分成ABCD四组
	根据和中位数的大小关系 AD分别加入big,small
	big,small<-big并B,small并small
	if k<|small|{
		return kselect(small,k)
	}else{
		return kselect(big,k-1-|small|)
	}
}