数据结构&算法快速排序

快速排序

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

快速排序分区

下面的动画表示法说明了如何在数组中查找枢轴值。

枢轴值将列表分为两部分。递归地，我们找到每个子列表的枢纽，直到所有列表仅包含一个元素。

快速排序枢轴算法

基于对快速分区的理解，我们现在尝试为它编写一个算法，如下所示。


步骤 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);
}

尝试一下