快速排序算法简介

sofia 3年前 (2021-12-29) 相关技术 | 抢沙发 236

文章评分 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; 
    } 
}