python快速排序_Python快速排序
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。现在根据前两个条件将其放置在适当的位置。
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.
让我们看看它的外观。
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(n 2 )
Python快速排序程序 (Program for Quick Sort in Python)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
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,
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
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
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
python快速排序