在本博客，之前有一個版本的QuickSort，其實(shí)網(wǎng)友很早就提出了相關(guān)的BUG，但是我一直沒有時間進(jìn)行修正，今天又有朋友提出了這個BUG，我剛好抽空看了一下，看來自己是相當(dāng)不嚴(yán)謹(jǐn)以至于犯下了如此大錯。
原文鏈接：http://m.shnenglu.com/mymsdn/archive/2009/03/06/quicksort.aspx （未修復(fù)）
關(guān)于修復(fù)BUG后的代碼，將在本文中提供，原文中不進(jìn)行修改，但會有提示指明是錯誤的，有興趣的朋友也可以直接在原文的代碼中尋找錯誤來鍛煉自己排錯的能力。
下面就是幾段代碼：
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: 由于在循環(huán)while(true)中，假設(shè)原代碼
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，
則無法進(jìn)入++i或者--j，那么在這個while(true)中，
i和j的值將無法發(fā)生變化，從而導(dǎo)致死循環(huán)。
@LINK:http://m.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的動作放在循環(huán)內(nèi)。
while(true)
{
while(cmp < arr[++i]) // bug200910280001:將原本在循環(huán)外的min+1，移進(jìn)循環(huán)內(nèi)，并首先+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 : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//
#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;
}