一種說(shuō)法，對(duì)極了---我覺(jué)得
快速排序和歸并排序其實(shí)是一種想法，都是用的分治的思路，只是分的key不同，快排是根據(jù)排序元素的值來(lái)分，分成比關(guān)鍵字大的，比關(guān)鍵字小的，確定自己的位子；而歸并是按序號(hào)(位置)來(lái)分，通常用的是二分，從中間均勻分開(kāi)，使分治后的子問(wèn)題達(dá)到一種平衡，降低復(fù)雜度。而快排在選取關(guān)鍵字的時(shí)候一般用開(kāi)頭第一個(gè)元素，隨機(jī)的，沒(méi)有更好的辦法可以使分治后的子問(wèn)題達(dá)到一種平衡。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100
int array[N];
int partition(int a[],int s,int e)//分治
{
int i=s,j=e;
while(i<j)
{
while(i<j&&a[j]>a[i]) j--;
if(i<j)
{
swap(a[j],a[i]);
i++;
}
while(i<j&&a[i]<a[j]) i++;
if(i<j)
{
swap(a[i],a[j]);
j--;
}
}
return i;
}
void qsort(int a[],int s,int e)
{
if(s<e)
{
int mid=partition(a,s,e);
//cout<<mid<<endl;
qsort(a,s,mid-1);
qsort(a,mid+1,e);
}
}
int main()
{
int i;
for(i=0;i<20;i++)
array[i]=rand()%100;
qsort(array,0,19);
for(i=0;i<20;i++)
printf("%d ",array[i]);
printf("\n");
return 0;
}
在寫(xiě)這個(gè)代碼的時(shí)候出了個(gè)問(wèn)題，在左右掃描數(shù)組的時(shí)候，沒(méi)有在交換以后改變指針i，j的值，而認(rèn)為在while中循環(huán)是改變是一樣的，但這會(huì)在某種情況下導(dǎo)致死循環(huán)。
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
Press any key to continue