设计与分析快速排序

快速排序是一种高效的排序算法，基于将数据数组划分为更小的数组。一个大数组被划分为两个数组，其中一个数组保存小于指定值（例如枢轴）的值，根据该值进行分区，另一个数组保存大于枢轴值的值。

快速排序对数组进行分区，然后递归调用自身两次以对两个结果子数组进行排序。该算法对于大型数据集非常有效，因为其平均复杂度和最坏情况复杂度分别为 O(n2)。

快速排序中的分区

以下动画演示解释了如何查找数组中的主元值。

快速排序

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

快速排序枢轴算法

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

步骤 1 - 选择具有枢轴的最高索引值

步骤 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 - 使用主元值对数组进行分区

步骤 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

分析

快速排序算法最坏情况的复杂度是O(n 2 )。然而，使用这种技术，在一般情况下，我们通常会在O(n log n)时间内获得输出。

执行

以下是快速排序算法在不同语言中的实现 -

C C++ Java Python 
#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);
}

输出

Input Array: [4 6 3 2 1 9 7 ]
==================================================
 pivot swapped :9,7
Updated Array: [4 6 3 2 1 7 9 ]
 pivot swapped :4,1
Updated Array: [1 6 3 2 4 7 9 ]
 item swapped :6,2
 pivot swapped :6,4
Updated Array: [1 2 3 4 6 7 9 ]
 pivot swapped :3,3
Updated Array: [1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

#include <iostream>
using namespace std;

#define MAX 7

int intArray[MAX] = {4,6,3,2,1,9,7};

void display() {
   int i;
   cout << "[";
	
   // navigate through all items 
   for(i = 0;i < MAX;i++) {
      cout << intArray[i] << " ";
   }
	
   cout << "]\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 {
            cout << "item swapped : " << intArray[leftPointer] << "," << intArray[rightPointer] << endl;
         swap(leftPointer, rightPointer);
      }
   }
	
   cout << "\npivot swapped : " << intArray[leftPointer] << "," << intArray[right] << endl;
   swap(leftPointer,right);
   cout << "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() {
   cout << "Input Array: ";
   display();
   quickSort(0, MAX-1);
   cout << "\nOutput Array: ";
   display();
}

输出

Input Array: [4 6 3 2 1 9 7 ]

pivot swapped : 9,7
Updated Array: [4 6 3 2 1 7 9 ]

pivot swapped : 4,1
Updated Array: [1 6 3 2 4 7 9 ]
item swapped : 6,2

pivot swapped : 6,4
Updated Array: [1 2 3 4 6 7 9 ]

pivot swapped : 3,3
Updated Array: [1 2 3 4 6 7 9 ]

Output Array: [1 2 3 4 6 7 9 ]

import java.util.Arrays;

public class QuickSortExample {
   int[] intArray = {
      4,
      6,
      3,
      2,
      1,
      9,
      7
   };

   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 {
            swap(leftPointer, rightPointer);
         }
      }
      swap(leftPointer, right);

      // System.out.println("Updated Array: "); 
      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);
      }
   }
   public static void main(String[] args) {
      QuickSortExample sort = new QuickSortExample();
      int max = sort.intArray.length;
      System.out.println("Contents of the array :");
      System.out.println(Arrays.toString(sort.intArray));

      sort.quickSort(0, max - 1);
      System.out.println("Contents of the array after sorting :");
      System.out.println(Arrays.toString(sort.intArray));
   }
}

输出

Contents of the array :
[4, 6, 3, 2, 1, 9, 7]
Contents of the array after sorting :
[1, 2, 3, 4, 6, 7, 9]

def partition(arr, low, high):
   i = low - 1
   pivot = arr[high]  # pivot element
   for j in range(low, high):
      if arr[j] <= pivot:
         # increment
         i = i + 1
         arr[i], arr[j] = arr[j], arr[i]
   arr[i + 1], arr[high] = arr[high], arr[i + 1]
   return i + 1

def quickSort(arr, low, high):
   if low < high:
      pi = partition(arr, low, high)
      quickSort(arr, low, pi - 1)
      quickSort(arr, pi + 1, high)

arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array is:")
for i in range(n):
   print(arr[i], end=" ")

输出

Sorted array is:
2 3 4 5 5 6 7 8