在本博客，之前有一個(gè)版本的QuickSort，其實(shí)網(wǎng)友很早就提出了相關(guān)的BUG，但是我一直沒(méi)有時(shí)間進(jìn)行修正，今天又有朋友提出了這個(gè)BUG，我剛好抽空看了一下，看來(lái)自己是相當(dāng)不嚴(yán)謹(jǐn)以至于犯下了如此大錯(cuò)。
原文鏈接：http://m.shnenglu.com/mymsdn/archive/2009/03/06/quicksort.aspx （未修復(fù)）
關(guān)于修復(fù)BUG后的代碼，將在本文中提供，原文中不進(jìn)行修改，但會(huì)有提示指明是錯(cuò)誤的，有興趣的朋友也可以直接在原文的代碼中尋找錯(cuò)誤來(lái)鍛煉自己排錯(cuò)的能力。
下面就是幾段代碼：
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 }
中，前兩段（行號(hào)，行號(hào)）中的代碼均返回false，
則無(wú)法進(jìn)入++i或者--j，那么在這個(gè)while(true)中，
i和j的值將無(wú)法發(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的動(dòng)作放在循環(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 : 定義控制臺(tái)應(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;
}