解釋什么是快速排序算法?

Sorting algorithms are a set of instructions that take an array or list as an input and arrange the items into a particular order.

排序算法是一組指令，這些指令采用數組或列表作為輸入并將項目按特定順序排列。

Sorts are most commonly in numerical or a form of alphabetical (called lexicographical) order, and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0) order.

排序最常見的是數字形式或字母順序(稱為字典順序)，并且可以升序(AZ，0-9)或降序(ZA，9-0)順序。

為什么排序算法很重要 (Why Sorting Algorithms are Important)

Since sorting can often reduce the complexity of a problem, it is an important algorithm in Computer Science. These algorithms have direct applications in searching algorithms, database algorithms, divide and conquer methods, data structure algorithms, and many more.

由于排序通常可以降低問題的復雜性，因此它是計算機科學中的重要算法。 這些算法可直接應用于搜索算法，數據庫算法，分治法，數據結構算法等等。

一些常見的排序算法 (Some Common Sorting Algorithms)

Some of the most common sorting algorithms are:

一些最常見的排序算法是：

• Selection Sort
  選擇排序
• Bubble Sort
  氣泡排序
• Insertion Sort
  插入排序
• Merge Sort
  合并排序
• Quick Sort
  快速排序
• Heap Sort
  堆排序
• Counting Sort
  計數排序
• Radix Sort
  基數排序
• Bucket Sort
  桶分類

排序算法分類 (Classification of Sorting Algorithm)

Sorting algorithms can be categorized based on the following parameters:

可以根據以下參數對排序算法進行分類：

1. Based on Number of Swaps or Inversion This is the number of times the algorithm swaps elements to sort the input. Selection Sort requires the minimum number of swaps.

   基于交換次數或反轉次數這是算法交換元素以對輸入進行排序的次數。 Selection Sort要求最少數量的交換。

2. Based on Number of Comparisons This is the number of times the algorithm compares elements to sort the input. Using Big-O notation, the sorting algorithm examples listed above require at least O(nlogn) comparisons in the best case and O(n^2) comparisons in the worst case for most of the outputs.

   基于比較次數這是算法比較元素以對輸入進行排序的次數。 使用Big-O表示法 ，上面列出的排序算法示例在大多數情況下對于大多數輸出??至少需要O(nlogn)比較，而在最壞情況下至少需要O(n^2)比較。

3. Based on Recursion or Non-Recursion Some sorting algorithms, such as Quick Sort, use recursive techniques to sort the input. Other sorting algorithms, such as Selection Sort or Insertion Sort, use non-recursive techniques. Finally, some sorting algorithm, such as Merge Sort, make use of both recursive as well as non-recursive techniques to sort the input.

   基于遞歸或非遞歸一些排序算法(例如Quick Sort )使用遞歸技術對輸入進行排序。 其他排序算法(例如Selection Sort或Insertion Sort )使用非遞歸技術。 最后，一些排序算法(例如Merge Sort )利用遞歸和非遞歸技術對輸入進行排序。

4. Based on Stability Sorting algorithms are said to be stable if the algorithm maintains the relative order of elements with equal keys. In other words, two equivalent elements remain in the same order in the sorted output as they were in the input.

   基于穩定性的排序算法被認為是stable是該算法使用相同的鍵維持元素的相對順序。 換句話說，兩個等效元素在排序輸出中的順序與輸入中的順序相同。

5. Insertion sort, Merge Sort, and Bubble Sort are stable

   Insertion sort ， Merge Sort和Bubble Sort穩定

6. Heap Sort and Quick Sort are not stable

   Heap Sort和Quick Sort不穩定

7. Based on Extra Space Requirement Sorting algorithms are said to be in place if they require a constant O(1) extra space for sorting.

   基于額外空間要求，如果排序算法需要恒定的O(1)額外空間來進行排序，則可以說已經in place 。

8. Insertion sort and Quick-sort are in place sort as we move the elements about the pivot and do not actually use a separate array which is NOT the case in merge sort where the size of the input must be allocated beforehand to store the output during the sort.

   Insertion sort和Quick-sort是in place我們圍繞樞軸移動元素時in place排序，實際上并沒有使用單獨的數組，在合并排序中情況并非如此，在合并排序中，必須事先分配輸入的大小以在輸出期間存儲輸出分類。

9. Merge Sort is an example of out place sort as it require extra memory space for it’s operations.

   Merge Sort是一個例子out place的排序，因為它需要它的運營的額外存儲空間。

任何基于比較的排序的最佳時間復雜度 (Best possible time complexity for any comparison based sorting)

Any comparison based sorting algorithm must make at least nLog2n comparisons to sort the input array, and Heapsort and merge sort are asymptotically optimal comparison sorts.This can be easily proved by drawing the decision tree diagram.

任何基于比較的排序算法都必須至少進行nLog2n個比較才能對輸入數組進行排序，而Heapsort和merge排序是漸近最優的比較排序，這可以通過繪制決策樹圖輕松證明。

翻譯自: https://www.freecodecamp.org/news/sorting-algorithms-explained/

解釋什么是快速排序算法?