C 使用 DSA - 快速排序

快速排序是一種高效的排序演算法，它基於將資料陣列劃分為較小陣列。將大型陣列劃分為兩個陣列，其中一個數組包含小於指定值的陣列，指定的這個值稱為樞軸，根據樞軸對陣列進行劃分；另一個數組包含大於樞軸的值。

快速排序對陣列進行劃分，然後遞迴呼叫自身兩次，對生成的兩個子陣列進行排序。此演算法對於大型資料集非常有效，因為其平均和最壞情況下的複雜度為 O(nlogn)，其中 n 是項數。

虛擬碼

A : array of items 

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

function partitionFunc(left, right, pivot)
   leftPointer = left -1
   rightPointer = right

   while True do
      while A[++leftPointer] < pivot do
         //donothing            
      end while
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //donothing         
      end while
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
   end while      
   swap leftPointer,right
   return leftPointer
end function

procedure swap (num1, num2)
   temp = A[num1]
   A[num1] = A[num2]
   A[num2] = temp;
end procedure

示例

#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);
   }      
}
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 ]
==================================================