QuickSort算法–用C，Java，Python实现
介绍
Quicksort算法是最快的内部排序算法之一，今天我们将讨论这个主题。
它主要基于以下三个主要策略：
- 分割或者分区：从要排序的给定元素序列中选择一个随机元素，称为数据透视。
假设元素是X，其中X是任何数字。
现在将列表分成两个小数组或者列表Y和Z，这样，Y中的所有元素都小于X，而Z中的所有元素都大于X， - 排序子数组，
- 合并(加入或者连接)已排序的子数组。
拆分将数组分成两个较小的数组。
当最终使用快速排序对这些子数组进行递归排序时，这些子数组被称为征服。
因此，快速排序是基于分而治之的算法。
快速排序算法
假设有N个元素，分别为a [0]，a [1]，…，a [N-1]。
下面给出了使用快速排序算法的步骤，
#1：选择任何元素作为枢轴。
例如，我们在这里选择第一个元素。
这将有助于将阵列分为两部分。
PIVOT = a[ FIRST ] //pivot selected,FIRST=0 here
#2：将两个指针i和j初始化为
i = FIRST + 1 //First index of the array j = LAST //Last index of array
#3：现在，我们增加i的值，直到找到比支点元素大的元素为止，
WHILE i<=j and a[i]<= PIVOT i=i+1
#4：我们减小j的值，直到找到小于枢轴元素的值，
WHILE j<=j and a[j]>= PIVOT j=j-1
#5：如果i <j，则互换a [i]和a [j]。
#6：重复步骤2到4，直到i> j，
#7：将所选的枢轴和a [j]互换，
#8：最后为在枢轴元素两侧创建的两个子数组递归调用此Quicksort。
通过示例了解算法
现在，让我们使用一个简单的例子来了解算法的工作原理。
我们考虑了一个具有值50、30、10、90、80、20、40、60的数组，如图1所示。
首先，我们选择一个枢轴元素，在本例中为第一个元素50。
快速排序算法
然后我们初始化i和j指针，如图2所示，分别指向30和60。
因此，我们将i指针向右移动，直到元素大于枢轴元素。
在我们的例子中，我们得到的是索引3，即值90。
快速排序算法
同样，j向左移动，直到找到小于枢轴的值，该值在索引6处得到，该值是40。
在图6的这一点上，我们可以看到我们同时获得了i和j值。
最后，我们交换相应的值并到达图7所示的位置。
快速排序算法
然后，我们再次进行i和j索引搜索，因此转到图9，其中我们的指针i和j都位于第4和第5个索引。
与前面的情况类似，我们在ith和jth位置交换相应的值。
因此，在此之后，我们需要将指针i向右移动，将j向左移动。
由于20 <50，因此我们需要将i向右增加1。
随着80> 50，我们不再移动i。
如
和11所示。
快速排序算法
然后我们开始将j向左移动。
当20 <50时，j减小1，现在位于第4个索引，如
所示。
从上述条件可以清楚地看出，i越过j。
因此，我们在j <i处停止。
因此，j的位置是分割点。
因此，我们交换枢轴和索引j点处的值，得到如图13所示的数组。
快速排序算法
此后，我们必须对子元素在枢轴元素50的左侧和右侧应用相同的方法。
通过这种分而治之方法，最后将获得排序后的数组。
实现QuickSort算法
1. C语言中的QuickSort算法
#include<stdio.h>
void quicksort(int a[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(a[i]<=a[pivot] && i<last)
i++;
while(a[j]>a[pivot])
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
quicksort(a,first,j-1);
quicksort(a,j+1,last);
}
}
int main()
{
int i, n, a[25];
printf("Enter total no.of elements: ");
scanf("%d",&n);
printf("Enter the elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
printf("Sorted Array: ");
for(i=0;i<n;i++)
printf(" %d",a[i]);
return 0;
}
输出：
C中的Quicksort
2. Java中的QuickSort算法
public class Quicksort
{
int position(int a[], int first, int last)
{
int pivot = a[last];
int i = (first-1);
for (int j=first; j<last; j++)
{
if (a[j] <= pivot)
{
i++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i+1];
a[i+1] = a[last];
a[last] = temp;
return i+1;
}
void Qsort(int a[], int first, int last)
{
if (first < last)
{
int p = position(a, first, last);
Qsort(a, first, p-1);
Qsort(a, p+1, last);
}
}
public static void main(String args[])
{
int a[] = { 50, 30, 10, 90, 80, 20, 40, 60};
int n = a.length;
Quicksort ob = new Quicksort();
ob.Qsort(a, 0, n-1);
System.out.println("sorted array:");
for (int i=0; i<n; i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
3. Python中的QuickSort算法
def quicksort(Mylist):
n=len(Mylist)
Rec_quicksort(Mylist, 0, n-1)
def Rec_quicksort(Mylist, first, last):
if first<last:
pos=position(Mylist, first, last)
Rec_quicksort(Mylist, first, pos-1)
Rec_quicksort(Mylist, pos+1, last)
def position(Mylist, first, last):
pivot=Mylist[first]
i=first
j=last
while i<j:
while i<=j and Mylist[i]<=pivot:
i=i+1
while pivot<Mylist[j]:
j=j-1
if i<j:
temp=Mylist[i]
Mylist[i]=Mylist[j]
Mylist[j]=temp
temp=Mylist[first]
Mylist[first]=Mylist[j]
Mylist[j]=temp
return j
Mylist=[ 50, 30, 10, 90, 80, 20, 40, 60 ]
print("Given list:",Mylist)
quicksort(Mylist)
print("After sorting list is:",Mylist)
QuickSort算法的时空复杂度
空间复杂度
Quicksort算法的空间复杂度由O(log(n))给出。
时间复杂度
Quicksort算法的时间复杂度由下式给出：
- O(n log(n))为最佳情况，
- O(n log(n))平均情况
- 而O(n ^ 2)在最坏的情况下。
