int split(int low, int high, vector<int>&A)
{
int i = low, x = A[low]; //i总是指向小于A[low]的数的最后一个数
int tmp = 0;
for (int j = low + 1; j <= high; ++j)
{
if (A[j] <= x)
{
i++;
if (i != j) //如果i==j，说明不需要交换，该位置正好可以作为小于A[low]的最后一个位置
{
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
}
}
}
tmp = A[i];
A[i] = A[low];
A[low] = tmp;
return i;
}
void quick_sort(vector<int>&A, int low, int high)
{
if (low < high)
{
int w = split(low, high, A);
quick_sort(A, low, w - 1);
quick_sort(A, w + 1, high);
}
}
分治——快速排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 分治法，是算法思想里最基础的思想。这也和人的基本思维有关，当我们需要解决一个大的问题时，直觉的就会将这个大问题分成...
- Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和...
