数据结构&算法 快速排序

  • 快速排序

    快速排序是一种高效的排序算法,它基于将数据数组划分为较小的数组。将一个大数组分为两个数组,其中一个数组的值小于指定值(例如,枢轴),基于该数组进行分区,另一个数组的值大于该枢轴值。快速排序对数组进行分区,然后递归调用两次以对两个结果子数组进行排序。该算法对于大型数据集非常有效,因为其平均和最坏情况下的复杂度分别为O(nLogn)和O(logn2)。
  • 快速排序分区

    下面的动画表示法说明了如何在数组中查找枢轴值。
    quicksort
    枢轴值将列表分为两部分。递归地,我们找到每个子列表的枢纽,直到所有列表仅包含一个元素。
  • 快速排序枢轴算法

    基于对快速分区的理解,我们现在尝试为它编写一个算法,如下所示。
    
    步骤 1 − 选择指标值最高的pivot
    步骤 2 − 取两个变量指向列表的左边和右边,不包括主变量
    步骤 3 − 左边指向低指数
    步骤 4 − 右指向高处
    步骤 5 − 而左边的值小于右移
    步骤 6 − 而值在右边大于支点左移
    步骤 7 − 如果步骤5和步骤6都不匹配,则交换左右
    步骤 8 − 如果左≥右,则相交点为新支点
    
  • 伪码

    上面算法的伪代码可以推导为-
    
    function partitionFunc(left, right, pivot)
       leftPointer = left
       rightPointer = right - 1
    
       while True do
          while A[++leftPointer] < pivot do
             //do-nothing            
          end while
        
          while rightPointer > 0 && A[--rightPointer] > pivot do
             //do-nothing         
          end while
        
          if leftPointer >= rightPointer
             break
          else                
             swap leftPointer,rightPointer
          end if
        
       end while 
      
       swap leftPointer,right
       return leftPointer
      
    end function
    
  • 快速排序算法

    递归地使用数据透视算法,我们最终得到了较小的分区。然后处理每个分区以进行快速排序。我们为快速排序定义递归算法,如下所示:-
    
    步骤 1 − 使最右边的索引值为主
    步骤 2 − 使用pivot值对数组进行分区
    步骤 3 − 快速排序左分区递归
    步骤 4 − 快速排序递归右分区
    
  • 快速排序伪代码

    要了解更多信息,请参阅快速排序算法的伪代码--
    
    procedure quickSort(left, right)
    
       if right-left <= 0
          return
       else     
          pivot = A[right]
          partition = partitionFunc(left, right, pivot)
          quickSort(left,partition-1)
          quickSort(partition+1,right)    
       end if   
       
    end procedure
    
  • 实现

    以下是C语言的实现
    
    #include <stdio.h>
    #include <stdbool.h>
    
    #define MAX 7
    
    int intArray[MAX] = {4,6,3,2,1,9,7};
    
    void printline(int count) {
       int i;
      
       for(i = 0;i < count-1;i++) {
          printf("=");
       }
      
       printf("=\n");
    }
    
    void display() {
       int i;
       printf("[");
      
       // navigate through all items 
       for(i = 0;i < MAX;i++) {
          printf("%d ",intArray[i]);
       }
      
       printf("]\n");
    }
    
    void swap(int num1, int num2) {
       int temp = intArray[num1];
       intArray[num1] = intArray[num2];
       intArray[num2] = temp;
    }
    
    int partition(int left, int right, int pivot) {
       int leftPointer = left -1;
       int rightPointer = right;
    
       while(true) {
          while(intArray[++leftPointer] < pivot) {
             //do nothing
          }
        
          while(rightPointer > 0 && intArray[--rightPointer] > pivot) {
             //do nothing
          }
    
          if(leftPointer >= rightPointer) {
             break;
          } else {
             printf(" item swapped :%d,%d\n", intArray[leftPointer],intArray[rightPointer]);
             swap(leftPointer,rightPointer);
          }
       }
      
       printf(" pivot swapped :%d,%d\n", intArray[leftPointer],intArray[right]);
       swap(leftPointer,right);
       printf("Updated Array: "); 
       display();
       return leftPointer;
    }
    
    void quickSort(int left, int right) {
       if(right-left <= 0) {
          return;   
       } else {
          int pivot = intArray[right];
          int partitionPoint = partition(left, right, pivot);
          quickSort(left,partitionPoint-1);
          quickSort(partitionPoint+1,right);
       }        
    }
    
    int main() {
       printf("Input Array: ");
       display();
       printline(50);
       quickSort(0,MAX-1);
       printf("Output Array: ");
       display();
       printline(50);
    }
    
    尝试一下