在本博客，之前有一個版本的QuickSort，其實網友很早就提出了相關的BUG，但是我一直沒有時間進行修正，今天又有朋友提出了這個BUG，我剛好抽空看了一下，看來自己是相當不嚴謹以至于犯下了如此大錯。
原文鏈接：http://www.shnenglu.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.shnenglu.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;
}