快排算法之父Tony Hoare去世，从古典学文科生出身到图灵奖得主，他的人生比算法更传奇

Core Viewpoint - The article discusses the life and contributions of Tony Hoare, the father of the quicksort algorithm, who passed away at the age of 92. It highlights his significant impact on computer science, particularly through the development of quicksort, Hoare logic, and the CSP model, as well as his acknowledgment of the "billion-dollar mistake" of introducing the null reference concept [1][4][27][41]. Group 1: Quicksort Algorithm - Quicksort is one of the most widely used sorting algorithms, included in the standard libraries of major programming languages such as C, Java, and Python [2][3]. - The algorithm was conceived in 1959 when Hoare was a visiting student in Moscow, where he initially considered using bubble sort but found it inefficient with a time complexity of O(n²) [5][12]. - Hoare developed a new approach by selecting a "pivot" element and partitioning the array into elements less than and greater than the pivot, which is a divide-and-conquer strategy [13]. - Quicksort has an average time complexity of O(n log n) and requires O(log n) auxiliary space, making it more efficient than merge sort, which requires O(n) additional memory [19][20]. - The algorithm is particularly well-suited for modern computer cache mechanisms, leading to faster execution times compared to other algorithms with similar complexities [21][24]. Group 2: Contributions to Computer Science - In 1969, Hoare introduced Hoare logic, a formal system for verifying program correctness, which laid the theoretical foundation for software reliability and security research [28]. - He proposed the CSP model in 1978, which describes interactions between concurrent processes and influenced the design of concurrency in the Go programming language [30][31]. - Hoare received the Turing Award in 1980 for his fundamental contributions to programming language design, emphasizing the importance of language quality in software development [35][36]. Group 3: The Billion-Dollar Mistake - Hoare introduced the concept of the null reference in 1965 while designing the ALGOL W language, intending to represent a variable with "no value" [41][42]. - This design choice led to widespread adoption in languages like Java and C++, resulting in numerous NullPointerExceptions and system failures over the decades [43][44]. - Hoare later reflected on this decision as a significant error, estimating it caused billions in damages and frustrations in the software industry [45]. Group 4: Personal Background and Career - Born in 1934 in British Ceylon (now Sri Lanka), Hoare initially studied classical studies and philosophy at Oxford University before transitioning to computer science [49][50]. - His career spanned both industry and academia, where he contributed to the development of the ALGOL 60 compiler and later became a professor at Queen's University Belfast and Oxford University [60][68]. - Hoare's work has earned him numerous accolades, including being knighted by Queen Elizabeth II and receiving the Kyoto Prize in 2000 [74].