2年前 (2021-12-29)  相关技术 |   抢沙发  196 
文章评分 0 次,平均分 0.0

快速排序算法简介

快速排序是一种分而治之的算法。当数据集较小时,该算法提供更好的性能。

此算法通过选择轴来工作。此轴将数组分为两部分。

1. 第1部分在数组之前,数组中的所有元素都必须小于pivot。

2. 第2部分在数组之后,数组中的所有元素都必须大于pivot

如上所述排列数组的过程称为“分区”。此分区算法是快速排序的核心。

分区是如何工作的?

在任何时刻,阵列都将处于如下状态,如下所示。

快速排序算法简介

下面是上面显示的变量

  • p:枢轴元件
  • i:标记数组绿色部分的最后一个元素
  • j:标记数组红色部分的最后一个元素

我们所要做的就是检查A[j]是否小于枢轴。如果A[j]小于pivot,那么我们必须增加i,交换A[i]A[j]。当我们到达末尾(数组A的最后一个元素)时。我们必须增加i,交换A[i]A[p]

下面是伪代码:

partition(A[], int l, int r)
{
     // select a pivot element
     // right most element is selected as pivot
     pivot= A[r]
     // initially green and red part of arrays donot exist
     i = l-1
     for(j=l; j <= r; j++)
     {
          //comparing element with pivot
          if(A[j] < pivot)
          {
               i++
               swap A[i] and A[j]
          }
     }
     swap A[i+1] and A[j]
     return (i+1)
}

选择支点的策略

1. 拾取第一个元素作为轴

2. 选择最后一个元素作为轴

3. 选择随机元素作为轴心

4. 选择中间带元素作为轴

快速排序代码示例

public class QuickSort
{
    public static void main(String args[])
    {
        int arr[] = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length-1);
        for(int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+" ");
        }
        
    }
    
    static void quickSort(int arr[], int l, int r)
    {
        if(l<r) //check if length of subarray is greater than 1
        {
            // this will set pivot element in the correct position
            int pi=partition(arr, l, r);
            // elements before the pivot will be sorted now
            quickSort(arr, l, pi-1);
            // elements after the pivot will be sorted
            quickSort(arr, pi+1, r);
        }
    }
    
    //partition algorithm as already explained above
	static int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  
        int i = (low-1); // index will follow smaller element
        for (int j=low; j<high; j++) 
        { 
            // check if element at j smaller than pivot
            if (arr[j] < pivot) 
            { 
                i++; 
  
                // swap arr[i] and arr[j] 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
  
        // swap arr[i+1] and arr[high] (or pivot) 
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 
  
        return i+1; 
    } 
}

快速排序的复杂性

快速排序随机选取第k个元素作为轴心,并将数组分成两部分。该函数递归地求解它。

因此

F(n)=F(k)+F(n-k-1)+θ(n)

1. 最佳情况:当枢轴正好在数组的中间时。然后将数组分成两个相等的部分。

因此我们可以说

F(n)=2*F(n/2)+θ(n)

利用主定理我们可以说

复杂度为θ(n*logn)

2. 最坏情况:当枢轴位于阵列边缘时,即它是阵列中最大或最小的元素。

在这种情况下

F(n)=2*F(n-1)+θ(n)

对于这种关系,复杂性为θ(n2)

原文地址:https://technicalknowledgehub.com/quick-sort/

 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/2527.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册