快速排序

快速排序關(guān)鍵在于確定一個(gè)中間值，使得小于這個(gè)中間值的數(shù)在左邊，大于這個(gè)中間值的數(shù)在右邊。那么中間值該如何確定呢？有以下幾種做法

• 首元素，也就是arr[l]
• 尾元素，也就是arr[r]
• 中間元素，也就是arr[(l+r)>>1]這里是位運(yùn)算，等價(jià)于arr[(l+r)/2^1]
• 中間的一個(gè)隨機(jī)元素

void Qsort(int arr[],int l,int r){if(l>=r) return;int begin = l,end = r,x = arr[(l+r)>>1];//上面是位運(yùn)算，表示(l+r)/2^1while(begin<=end){while(arr[begin]<x) begin++;while(arr[end]>x) end--;if(begin<=end) swap(&arr[begin++],&arr[end--]);}Qsort(arr,l,end);Qsort(arr,begin,r);
}
//除了和x的比較不帶=，其他的都帶

快速排序相關(guān)變體

題目如下：

求第k大（小）的數(shù)，一種做法是堆排序把前k個(gè)數(shù)找出來就行，另一種就是利用快速排序的思想去做?，F(xiàn)暫把中間的分界點(diǎn)稱為pivot，左邊的數(shù)都小于pivot，右邊的數(shù)都大于pivot。那么假如左邊有m個(gè)數(shù)，右邊有n個(gè)數(shù)。求第k大的數(shù)。如果k<n，那么這個(gè)數(shù)肯定在右邊，反之這個(gè)數(shù)肯定在左邊。以此來縮小這個(gè)數(shù)所在的范圍。

歸并排序

歸并排序的核心思想在于將兩個(gè)有序的數(shù)組合并為一個(gè)全局有序的數(shù)組。

int tmp[100000];
void merge_sort(int arr[],int begin,int end){if(begin>=end) return;int mid = (begin+end)>>1;merge_sort(arr,begin,mid);merge_sort(arr,mid+1,end);int l_begin = begin,r_begin = mid+1,tmp_index = 0;while(l_begin<=mid && r_begin<=end){if(arr[l_begin]<=arr[r_begin]) tmp[tmp_index++] = arr[l_begin++];else tmp[tmp_index++] = arr[r_begin++];}while(l_begin<=mid) tmp[tmp_index++] = arr[l_begin++];while(r_begin<=end) tmp[tmp_index++] = arr[r_begin++];int k = 0;while(begin<=end){arr[begin++] = tmp[k++];}
}