快速排序和堆排序

末蓝、 2022-08-07 13:43 189阅读 0赞

最近在看算法方面的知识，自己动手写了点代码。为了以后复习方便，主要是自己总是遗忘，所以把这些代码保留下来。

</pre><pre name="code" class="cpp">#include<iostream>
    using namespace std;
    
    void quickSort(int a[], int l, int r)
    {
    	if(l < r){
    		swap(a[l], a[(l+r)/2]);
    		int i = l, j = r, t = a[i];
    		while(i < j){
    			while(i < j && a[j] >= t)
    				j--;
    			if(i < j)
    				a[i++] = a[j];
    			while(i < j && a[i] <=t)
    				i++;
    			if(i < j)
    				a[j--] = a[i];
    		}
    		a[i] = t;
    		quickSort(a, l, i - 1);
    		quickSort(a, i + 1, r);
    	}
    }
    
    //k为数组中的前k个数，i为当前的数（位置非下标，下标为i-1）
    void maxHeap(int a[], int k, int i){
    	int max = i-1;
    	if(2*i < k)
    		if(a[2*i] > a[max])
    			max = 2*i;
    	if(2*i - 1 < k)
    		if(a[2*i - 1] > a[max])
    			max = 2*i - 1;
    	if(max != i-1){
    		swap(a[max], a[i-1]);
    		maxHeap(a, k, max + 1);
    	}
    }
    void buildHeap(int a[], int k){
    	for(int i = k/2 - 1; i >= 0; i--)
    	{
    		maxHeap(a, k, i+1);
    	}
    }
    void heapSort(int a[], int k){
    	buildHeap(a, k);
    	int t = k-1;
    	while(t>0)
    	{
    		swap(a[t], a[0]);
    		maxHeap(a, t, 1);
    		t--;
    	}
    }
    
    int main(){
    	int a[] = {1, 5, 2, 10, 3, 5, 4, 8, 9};
    	//quickSort(a, 0, 8);
    	//heapSort(a, 9);
    	buildHeap(a, 4);
    	for(int i = 0; i < 9; i++){
    		cout<<a[i]<<" ";
    	}
    	cout<<endl;
    	return 0;
    }

在写堆排序时，主要是参数k的设置，这个k为希望数组的前k个元素进行相关操作，因为在 寻找最小的k个数问题中，需要建立前k个数的最大堆，所以书写函数时，考虑了相关问题。