在本博客，之前有一个版本的QuickSort，其实网友很早就提出了相关的BUG，但是我一直没有时间进行修正，今天又有朋友提出了这个BUG，我刚好抽空看了一下，看来自己是相当不严谨以至于犯下了如此大错。
原文链接：http://www.cppblog.com/mymsdn/archive/2009/03/06/quicksort.aspx （未修复）
关于修复BUG后的代码，将在本文中提供，原文中不进行修改，但会有提示指明是错误的，有兴趣的朋友也可以直接在原文的代码中寻找错误来锻炼自己排错的能力。
下面就是几段代码：
Algorithms.cpp
#include "StdAfx.h"
#include "Algorithms.h"
Algorithms::Algorithms(void)
{
}
Algorithms::~Algorithms(void)
{
}
Algorithms.h
#pragma once
#include <iostream>
class Algorithms
{
public:
Algorithms(void);
~Algorithms(void);
public:
template <typename T>
static void QuickSort(T* arr, size_t min, size_t max);
private:
template <typename T>
static size_t qsort_helper_partition(T* arr, size_t min, size_t max);
template <typename T>
static inline void swap(T* arr, size_t x, size_t y);
// helper
template <typename T>
static inline void helper_show_all(T* arr, size_t min, size_t max, char *msg);
};
template <typename T>
void Algorithms::QuickSort(T* arr, size_t min, size_t max)
{
if(min >= max || max == 0 - 1) return;
helper_show_all(arr, min, max, "before qsort_helper_partition");
size_t p = qsort_helper_partition(arr, min, max);
helper_show_all(arr, min, max, "after qsort_helper_partition");
QuickSort(arr, min, p - 1);
QuickSort(arr, p + 1, max);
}
/*
* @BUG: bug200910280001
* @DESC: 由于在循环while(true)中，假设原代码
01 while(true)
02 {
03 while(cmp < arr[i])
04 ++i;
05 while(arr[j] < cmp)
06 --j;
07 if(i >= j) break;
08
09 swap(arr, i, j);
10 }
中，前两段（行号，行号）中的代码均返回false，
则无法进入++i或者--j，那么在这个while(true)中，
i和j的值将无法发生变化，从而导致死循环。
@LINK:http://www.cppblog.com/mymsdn/archive/2009/03/06/quicksort.aspx#99606
*/
template <typename T>
size_t Algorithms::qsort_helper_partition(T* arr, size_t min, size_t max)
{
T cmp = arr[min];
int i = min, j = max; // bug200910280001:修正i = min+1，将+1的动作放在循环内。
while(true)
{
while(cmp < arr[++i]) // bug200910280001:将原本在循环外的min+1，移进循环内，并首先+1
; // bug200910280001:将++1移至while条件中。
while(arr[j] < cmp)
--j;
if(i >= j) break;
helper_show_all(arr, min, max, "before swap(arr, i, j)");
swap(arr, i, j);
helper_show_all(arr, min, max, "after swap(arr, i, j)");
}
swap(arr, min, j);
return j;
}
template <typename T>
void Algorithms::swap(T* arr, size_t x, size_t y)
{
T tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
template <typename T>
void Algorithms::helper_show_all(T* arr, size_t min, size_t max, char *msg)
{
std::cout << "current array :\t";
for(int i = min; i < max; ++i)
{
std::cout << arr[i] << " ";
}
std::cout<<"\t//"<<msg;
std::cout<<std::endl;
}
cpp_quickSort.cpp
// cpp_quickSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "Algorithms.h"
#include <iostream>
#include <vector>
#include <algorithm>
int _tmain(int argc, _TCHAR* argv[])
{
int arr_begin = 0;
int arr_length = 12; //The length will instead of the magic numbers
int arr[] = {8, 3, 7, 1, 5, 6, 2, 1, 9, 9, 1, 1};
// Test for : 20091028bug0001
// int arr[] = {1, 1, 1};
std::cout << "input array :\t";
for(size_t i = arr_begin; i != arr_length; ++i)
{
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
Algorithms::QuickSort(arr, arr_begin, arr_length);
std::cout << "result array :\t";
for(size_t i = arr_begin; i != arr_length; ++i)
{
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
std::cout << "--------------------" << std::endl;
std::cout << "input array :\t";
std::vector<int> vec;
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(1);
vec.push_back(7);
vec.push_back(6);
for(std::vector<int>::iterator iter = vec.begin();
iter != vec.end(); ++ iter)
{
std::cout<<*iter<<" ";
}
std::cout<<std::endl;
std::sort(vec.begin(), vec.end());
for(std::vector<int>::iterator iter = vec.begin();
iter != vec.end(); ++ iter)
{
std::cout<<*iter<<" ";
}
std::cout<<std::endl;
return 0;
}