python快速排序_Python快速排序

电玩女神 2022-12-07 13:29 286阅读 0赞

![9132f6c40cfac296f5705ed5ab1e73dc.png][]

python快速排序

Here you get python quick sort program and algorithm.

在这里，您将获得python快速排序程序和算法。

Quick sort is based on divide and Conquer technique. We divide our array into sub-arrays and that sub-arrays divided into another sub-arrays and so on, until we get smaller arrays. Because it is easy to solve small arrays in compare to a large array.

快速分类是基于分而治之的技术。 我们将数组划分为子数组，然后将该子数组划分为另一个子数组，依此类推，直到得到更小的数组。 因为与大数组相比，解决小数组很容易。

Sorting smaller arrays will sort the entire array.

对较小的数组进行排序将对整个数组进行排序。

## Python快速排序 **(**Python Quick Sort**)** ##

To understand Quick Sort let’s  take an example:-

为了理解快速排序，让我们举个例子：

### 例 **(**Example**)** ###

We have an array \[48,44,19,59,72,80,42,65,82,8,95,68\]

我们有一个数组\[48,44,19,59,72,80,42,65,82,8,95,68\]

First of all we take first element and place it at its proper place. We call this element **Pivot** element.

首先，我们将第一个元素放在适当的位置。 我们称此元素为**Pivot**元素。

**Note: **We can take any element as **Pivot** element but for convenience the first element is taken as **Pivot.**

**注意：**我们可以将任何元素都用作**Pivot**元素，但为方便起见，将第一个元素视为**Pivot。**

There are two condition to place **Pivot** at its proper place.

将**Pivot**放置在适当位置有两个条件。

*  All the elements to the left of **Pivot** element should be smaller than
    
    **Pivot**元素左侧的所有元素都应小于
 *  All the elements to the right of **Pivot** element should be greater than
    
    **Pivot**元素右侧的所有元素都应大于

In given array, we’ll take first element as **Pivot** element which is 48. Now place it at its proper place according to first two conditions.

在给定的数组中，我们将第一个元素作为**Pivot**元素，即48。现在根据前两个条件将其放置在适当的位置。

![Python Quick Sort 1][]

Here all the elements to the left is smaller and to right are greater than **Pivot.**

在此，左侧的所有元素都比**Pivot**小，而右侧的元素都大于**Pivot。**

If you confused that how we placed **Pivot** at its proper place then wait we’ll discuss it later in **partition algorithm.**

如果您对如何将**Pivot**放置在适当位置感到困惑，那么请稍后再讨论**分区算法。**

Well, now we’ll take two sub-lists/sub-arrays left and right of our **Pivot** element (48).  Sub-lists will be

好了，现在我们将在**Pivot**元素的左侧和右侧获得两个子列表/子数组(48)。 子列表将是

\[42,44,19,8\] and \[80,72,65,82,59,95,68\]

\[42,44,19,8\]和\[80,72,65,82,59,95,68\]

and will also take first element as **Pivot** element in both and place the their **Pivot** elements at their proper places using **partition algorithm.** After this step each of the sub-lists will be divided into two parts then new sub-lists will be divided into another two parts and so on until we reached the end.

并且还将第一个元素都用作**Pivot**元素，并使用**分区算法**将其**Pivot**元素放置在适当的位置**。** 在此步骤之后，每个子列表将被分为两部分，然后新的子列表将被分为另外两个部分，依此类推，直到到达结尾为止。

Let’s see how it will look like.

让我们看看它的外观。

![Python Quick Sort 2][]

**Pivot element represented by Green color.**

**枢轴元素以绿色表示。**

We can write a recursive function for this procedure. There would be two terminating conditions. When the sub-list has only 1 element or when no sub-list is formed. If the value of **low** is equal to **up** then there will be only one element in the sub-list and if the value of **low** exceeds** up** then no sub-list is formed. So our algorithm will be.

我们可以为此过程编写一个递归函数。 将有两个终止条件。 当子列表只有1个元素时或没有子列表形成时。 如果**low**的值等于**up，**则子列表中将只有一个元素；如果**low**的值超过**up，**则不会形成子列表。 因此我们的算法将是。

### 算法 **(**Algorithm**)** ###

**Quick\[array, low,up\]**

**快速\[数组，低，上\]**

Where **low** and **up** are lower and upper bound of the array.

其中**低**和**至多**是下限和上限的阵列构成。

**STEP 1:**    if low>=up then return

**步骤1：**如果从低到高则返回

**STEP 2**:    set piv\_loc = call partition(array,low,up)

**步骤2** ：设置piv\_loc =调用分区(array，low，up)

**                  ** \[calling partition to find the location of pivot\]

**                  **  \[调用分区以查找枢轴的位置\]

**STEP 3:   ** call Quick(array,low,piv\_loc-1)

**步骤3：**调用Quick(array，low，piv\_loc-1)

**                       ** \[Calling Quick for left sub-list\]

**                       **  \[为左侧子列表快速调用\]

**STEP 4:   ** call Quick(array,piv\_loc+1, up)

**步骤4：**呼叫Quick(array，piv\_loc + 1，向上)

**                       ** \[Calling Quick for right sub-list\]

**                       **  \[快速调用右侧子列表\]

**Partition \[array, low, up\]**

**分区\[数组，低，上\]**

This algorithm is to find the location of pivot element and return it.

该算法是找到枢轴元素的位置并将其返回。

**STEP 1:**  set i = low+1

**步骤1：**将i设为低+1

Set j = up

设置j =向上

Set pivot = array\[low\]

设置数据透视=数组\[低\]

**STEP 2: ** while(i <= j)

**步骤2：** while(i <= j)

While(( array\[i\] < pivot ) and ( i < up ))

While(((array \[i\] <枢轴)和(i <up))

Increase i by 1

使我增加1

While ( array\[j\] > pivot )

而(数组\[j\]>枢轴)

Decrease j by 1

将j减1

If ( i < j )

如果(i <j)

Swap the value of array\[i\] with array\[j\]

用array \[j\]交换array \[i\]的值

Increase i by 1

使我增加1

Decrease j by 1

将j减1

Else

其他

Increase i by 1

使我增加1

**STEP 3:** **   **set array\[low\] = array\[j\]

**步骤3：** **   ** 设置array \[low\] = array \[j\]

Set array\[j\] = pivot

设置数组\[j\] =枢轴

Return j

返回j

### 时间复杂度 **(**Time Complexity**)** ###

**Best Case:** O (n log2n)

**最佳情况：** O(n log 2 n)

**Average Case:** O (n log n)

**平均情况：** O(n log n)

**Worst Case:** O (n2)

**最坏的情况：** O(n2)

### Python快速排序程序 **(**Program for Quick Sort in Python**)** ###

Array = [48,44,19,59,72,80,42,65,82,8,95,68]
    low = 0
    up = len(Array) - 1
     
    def partition(Array,low,up):
    	i = low+1
    	j = up
    	pivot = Array[low]
    	while(i<=j):
    		while(Array[i]<pivot and i<up):
    			i = i+1
    		while(Array[j]>pivot):
    			j = j-1
    		if(i<j):
    			Array[i],Array[j] = Array[j],Array[i]
    			i = i+1
    			j = j-1
    		else:
    			i = i+1
    	Array[low] = Array[j]
    	Array[j] = pivot
    	return j
     
    def quick(Array,low,up):
    	if(low>=up):
    		return
    	piv_loc = partition(Array,low,up)
    	quick(Array,low,piv_loc-1)
    	quick(Array,piv_loc+1,up)
     
    quick(Array,low,up)
     
    for i in Array:
    	print i,

**Output**

**输出量**

*8 19 42 44 48 59 65 68 72 80 82 95*

Comment below if you have doubts related to above python quicksort tutorial.

如果您对以上python quicksort教程有疑问，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/12/python-quick-sort.html][https_www.thecrazyprogrammer.com_2017_12_python-quick-sort.html]

python快速排序

[9132f6c40cfac296f5705ed5ab1e73dc.png]: /images/20221123/876bba67a37741d0abd3361a79e454d3.png
[Python Quick Sort 1]: /images/20221123/78878d58aeb04cdea6fc1f57c967df30.png
[Python Quick Sort 2]: /images/20221123/1950661d59b54a1db5e363939a3220a4.png
[https_www.thecrazyprogrammer.com_2017_12_python-quick-sort.html]: https://www.thecrazyprogrammer.com/2017/12/python-quick-sort.html