快速排序及其改进算法_基排序及其算法

分手后的思念是犯贱 2023-03-05 12:40 6阅读 0赞

快速排序及其改进算法

## 基数排序 **(**Radix Sort**)** ##

**Radix sort or bucket sort** is a method that can be used to sort a list of a number by its base. If we want to sort the list of English words, where radix or base is 26 then 26 buckets are used to sort the words.

**基数排序或存储桶排序**是一种可用于按**基数对**列表进行排序的方法。 如果要对英语单词列表进行排序，其中基数或基数为26，则使用26个存储桶对单词进行排序。

To sort an array of decimal number where the radix or base is 10 we need 10 buckets and can be numbered as 0,1,2,3,4,5,6,7,8,9. A number of passes required to have a sorted array depend upon the number of digits in the largest element.

要对基数或基数为10的十进制数字数组进行排序，我们需要10个存储桶，并且可以将其编号为0、1、2、3、4、5、6、7、8、9。 具有排序数组所需的遍数取决于最大元素中的位数。

## 基数排序算法 **(**Algorithm for Radix sort**)** ##

Let **A** be a linear array of **n** elements **A\[1\], A\[2\], A\[3\]............A\[n\]**. Digit is the total number of digit in the largest element in array **A**.

设**A**为**n个**元素**A \[1\]，A \[2\]，A \[3\] ......... A \[n\]**的线性数组。 Digit是数组**A中**最大元素的位数。

1.  Input n number of elements in an array A.
    
    在数组A中输入n个元素。
2.  Find the total number of digits in the largest element in the array.
    
    查找数组中最大元素的总位数。
3.  Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
    
    初始化i = 1并重复步骤4和5，直到( i <= Digit )。
4.  Initialize the bucket j=0 and repeat the steps 5until (j<n).
    
    初始化存储桶j = 0，然后重复步骤5until( j <n )。
5.  Compare the ith position of each element of the array with bucket number and place it in the corresponding bucket.
    
    将数组中每个元素的第 i 个位置与存储区编号进行比较，并将其放置在相应的存储区中。
6.  Read the elements (S) of the bucket from 0th bucket to 9th bucket and from the first position to the higher one to generate new array A.
    
    从第 0 个存储桶到第 9 个存储桶以及从第一个位置到较高的存储桶中读取存储桶的元素( S )，以生成新的数组A。
7.  Display the sorted array A.
    
    显示排序后的数组A。
8.  Exit.
    
    出口。

**Time complexity**

**时间复杂度**

Time requirement for the **radix sorting method** depends on the number of digits and the elements in the array. Suppose **A** is an array of **n** elements **A1, A2...** An and let **r** denote the radix( for example **r=10** for decimal digits, **r=26** for English letters and **r=2** for hits). If **A1** is the largest number then **A!** Can be represented. Then **radix sort** require **s** passes. In passes, each element is compared with the bucket elements.

**基数排序方法的**时间要求取决于位数和数组中的元素。 假设**A**是**n个**元素**A1，A2 ...** An的数组，则**r**表示基数(例如**r = 10**代表小数位， **r = 26**代表英文字母， **r = 2**代表匹配)。 如果**A1**是最大的数字，则**A！** 可以代表。 然后**基数排序**需要**S**经过。 在通过中，将每个元素与铲斗元素进行比较。

So the **radix sort** requires the total comparison **f(n)** of: **F(n) < = r x s x n**

因此， **基数排序**要求总比较**f(n)**为： **F(n)<= rxsxn**

**Worst case**

**最糟糕的情况**

In the worst case **s = n** so **F(n) = O(n2)**

在最坏的情况下**s = n，**所以**F(n)= O(n2)**

**Best case**

**最好的情况**

In the best case **s = logn** so **f(n) = (nlogn)**

在最佳情况下**s = logn，**所以**f(n)=(nlogn)**

**Average case**

**平均情况**

It is very hard to define the time complexity. Because it will depend on the choice of the radix **r** and also the number of a digit on largest elements (i.e number of passes) but on an average (**log n**) comparison is required so **f(n) = O(nlogn)**

定义时间复杂度非常困难。 因为这将取决于基数**r**的选择以及最大元素上的位数(即通过次数)，但是需要进行平均( **对数n** )比较，因此**f(n)= O(nlogn)**

### 基数排序的优点 **(**Advantages of radix Sort**)** ###

1.  It is implemented in Java, it would be faster than quicksort or heap.
    
    它是用Java实现的，它比quicksort或heap更快。
2.  It is stable because it preserves existing order of equals keys.
    
    之所以稳定是因为它保留了等号的现有顺序。
3.  It is good on small keys.
    
    小键上很好。

### 基数排序的缺点 **(**Disadvantages of radix sort**)** ###

1.  It is not efficient on very long keys because the total sorting time is proportional to key length and to the number of items to sort.
    
    在很长的键上效率不高，因为总排序时间与键长和要排序的项数成正比。
2.  We have to write an unconventional compare routine.
    
    我们必须编写一个非常规的比较例程。
3.  It requires fixed size keys and some standard way of breaking the keys to pieces.
    
    它需要固定大小的键和一些将键分解成碎片的标准方法。

**Example:** To illustrate the radix sort consider the following array with 7 elements

**示例：**为了说明基数排序，请考虑以下包含7个元素的数组

42, 133, 7, 23, 74, 670, 49

In this array, the biggest elements are 670 and the number of digits is 3, so 3 passes are required to sort the array. Read the elements and compare the first position (2 is in the first position of 42) digits with the digits of the buckets and place it

在此数组中，最大元素为670，位数为3，因此需要3次通过才能对数组进行排序。 读取元素并将第一个位置(2在第一个位置42)与存储桶的数字进行比较并将其放置

![Radix sort example 1][]

Now read the elements from left to right and the bottom to the top of the bucket and place it in an array for the next pass. Read the array elements and compare the second position (4 is in the second position of the elements 042) digit with a number of the bucket and place it.

现在，从存储桶的左侧到右侧以及底部到顶部读取元素，并将其放置在数组中以进行下一个遍历。 读取数组元素，并将第二个位置(4在元素042的第二个位置)与多个存储桶进行比较，然后将其放置。

![Radix sort example 2][]

Again read the element from left to right and from bottom to top to get an array for the third pass. (0 is in the first position of 042) compare the third position digit in each element with the budget digit and place it wherever it matches.

再次从左到右，从下到上读取元素，以获取第三遍的数组。 (0在042的第一位置)将每个元素中的第三位置数字与预算数字进行比较，然后将其放置在匹配的位置。

![Radix sort example 3][]

**Now the sorted array is 7 , 23, 42, 49, 74, 133, 670.**

**现在排序后的数组是7，23，42，49，74，133，670。**

> 翻译自: [https://www.includehelp.com/algorithms/radix-sort-and-its-algorithm.aspx][https_www.includehelp.com_algorithms_radix-sort-and-its-algorithm.aspx]

快速排序及其改进算法

[Radix sort example 1]: /images/20230208/ca4ae8221b4142a88f56232249a5b16c.png
[Radix sort example 2]: /images/20230208/606d360e7edf4d9eb8785e64ce75743e.png
[Radix sort example 3]: /images/20230208/2c716af06bba43649e5969f3c63be7a7.png
[https_www.includehelp.com_algorithms_radix-sort-and-its-algorithm.aspx]: https://www.includehelp.com/algorithms/radix-sort-and-its-algorithm.aspx