首元素#xff0c;也就是arr[l]尾元素#xff0c;也就是arr[r]中间元素#xff0c;也就是ar…快速排序

快速排序关键在于确定一个中间值使得小于这个中间值的数在左边大于这个中间值的数在右边。

那么中间值该如何确定呢有以下几种做法

首元素也就是arr[l]尾元素也就是arr[r]中间元素也就是arr[(lr)1]这里是位运算等价于arr[(lr)/2^1]中间的一个随机元素

void

arr[(lr)1];//上面是位运算表示(lr)/2^1while(beginend){while(arr[begin]x)

end--;if(beginend)

swap(arr[begin],arr[end--]);}Qsort(arr,l,end);Qsort(arr,begin,r);

题目如下

求第k大小的数一种做法是堆排序把前k个数找出来就行另一种就是利用快速排序的思想去做。

现暂把中间的分界点称为pivot左边的数都小于pivot右边的数都大于pivot。

那么假如左边有m个数右边有n个数。

求第k大的数。

如果kn那么这个数肯定在右边反之这个数肯定在左边。

以此来缩小这个数所在的范围。

归并排序

归并排序的核心思想在于将两个有序的数组合并为一个全局有序的数组。

int

(beginend)1;merge_sort(arr,begin,mid);merge_sort(arr,mid1,end);int

l_begin

r_beginend){if(arr[l_begin]arr[r_begin])

tmp[tmp_index]

arr[r_begin];}while(l_beginmid)

tmp[tmp_index]