?博主：命運之光
?專欄：算法基礎(chǔ)學(xué)習(xí)

前言：算法學(xué)習(xí)筆記記錄日常分享，需要的看哈O(∩_∩)O，感謝大家的支持！

?快速排序——分治

因為x參與交換之后仍然會被留在左右區(qū)間中的一個里。

1.確定分界點:(這里的分界點不一定是x,可以隨意取值，常用取值方法如下)
q[l],q[(l+r)/2],q[r],隨機//這里隨機數(shù)的表示：q[rand() % (r - l) + l]
2.調(diào)整區(qū)間：

3.遞歸處理左右兩段(<=x和>=x這兩段）

如何實現(xiàn)2：
方法1.

方法2.

將兩個指針i,j從兩頭挪向分界點，直到有一個i>=x,此時這個i
需要放到右半邊，一個j<x，此時這個j需要放到左半邊，此時交
換i.j(swap），故此時i<=x,j>x,直到i,j相遇就可以把整個區(qū)間
一分為二

j的后面(不包括j)>=3，i的前面(不包括i)<=3(注意邊界）
??代碼實現(xiàn)


??快速排序模板：

void quick_sort(int q[], int l, int r)//簡單理解：這里的l一般0,r一般是個數(shù)-1（減去第0個數(shù)）
{
     if (l >= r) return;//排序首先看邊界，如果區(qū)間里沒有數(shù)或只有一個數(shù)則不用排序，否則如下進行上述的1，2，3點
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];//問：為什么不是i=l,j=r?答：因為是先移動完指針再進行判斷，因此指針要先放在兩個指針的左右兩側(cè)一格，這樣往中間移動一格后才能到正真的邊界，注意：這里的i,j,l,r都為下標(biāo)。
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);//指針移動的判斷不帶等號，因為如果選取的x是數(shù)組里最大的數(shù)，那么一直滿足q[i]<=x,i會一直++發(fā)生越界都不會停下，j同理。eg.123，選取3，i<=3,i++,i=3也會向后繼續(xù)移動，已越界，錯誤，故此不能加=
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);//如果這兩個指針還沒有相遇，則交換，如果不用swap可以寫：int t=q[i];q[i]=q[j];q[j]=t;
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);//eg.1 2排序:
}

??對以上快速排序代碼進行測試，模板可用(●’?’●)！

??測試代碼

#include<bits/stdc++.h> 
using namespace std;
void quick_sort(int q[], int l, int r)
{
     if (l >= r) return;
     int i = l - 1, j = r + 1 ,x = q[l + r >> 1];
     while (i < j) 
     {
         do i ++ ; while (q[i] < x);
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);
     }
     quick_sort(q, l, j);
     quick_sort(q, j + 1, r);
}
int main()
{
	int a[5]={5,3,2,8,6};//對5，3，2，8，6進行排序 
	quick_sort(a,0,4);//傳入數(shù)組，傳入l,r進行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序結(jié)果為：23568 
	}
	return 0;
}

?歸并排序——分治 O(nlogn)

1.確定分界點：mid=(l+r)/2

要格外注意分界點：歸并排序是下標(biāo)的中間值，快速排序是隨機一個數(shù)組里面的值

2.遞歸排序left,right
3.歸并——合二為一 //實際是一個雙指針?biāo)惴?

??歸并排序模板：

void merge_sort(int q[], int l, int r)
{
	int tmp[5];//可變
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);//l是左半邊起點
	merge_sort(q, mid + 1, r);//mid+1是右半邊起點
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)//i,j分別是左右兩邊的指針
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//tmp[k++]=q[i++]等價于tmp[k]=q[i],k++,i++
	   else tmp[k ++ ] = q[j ++ ];//比較q[i],q[j],哪個小就把哪個放到tmp里（最后tmp的順序就可以從小到大依次排）
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];//把左右兩邊沒有循環(huán)完的數(shù)放到最后（因為左右兩邊本身就已經(jīng)從小到大排好序故這些數(shù)一定從小到大）
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//將tmp里的數(shù)復(fù)制回q中
}

??對以上快速排序代碼進行測試，模板可用(●’?’●)！

??測試代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-469879.html

#include<bits/stdc++.h> 
using namespace std;
void merge_sort(int q[], int l, int r)
{
	int tmp[5];
	if (l >= r) return;
	int mid = l + r >> 1;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
	   else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main()
{
	int a[5]={8,3,2,7,6};//對5，3，2，8，6進行排序 
	merge_sort(a,0,4);//傳入數(shù)組，傳入l,r進行快速排序 
	for(int i;i<5;i++)
	{
		cout<<a[i]<<" ";	//快速排序結(jié)果為：23568 
	}
	return 0;
}

到了這里，關(guān)于算法基礎(chǔ)學(xué)習(xí)筆記——①排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！