使用 Java 的 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

演示程式

package com.tutorialspoint.advancedsort;

import java.util.Arrays;

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

   public static void main(String[] args){      
      QuickSortDemo quickSortDemo = new QuickSortDemo();
      System.out.println("Input Array: " +Arrays.toString(intArray));
      printline(50);   
      quickSortDemo.quickSort(0, intArray.length-1);
      System.out.println("Output Array: " + Arrays.toString(intArray));
      printline(50);        
   }    

   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
      System.out.println("=");
   }   

   private 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{
            System.out.println(" item swapped :" 
            + intArray[leftPointer]+","+intArray[rightPointer]);
            swap(leftPointer,rightPointer);
         }
      }
      System.out.println(" pivot swapped :" 
      + intArray[leftPointer]+","+intArray[right]);
      swap(leftPointer,right);
      System.out.println("Updated Array: " 
      + Arrays.toString(intArray));       
      return leftPointer;
   }

   private void swap(int num1, int num2){
      int temp = intArray[num1];
      intArray[num1] = intArray[num2];
      intArray[num2] = temp;
   }

   public void quickSort(int left, int right){        
      if(right-left <= 0){
         return;
      }else{
         int pivot = intArray[right];
         int partition = partition(left, right, pivot);
         quickSort(left,partition-1);
         quickSort(partition+1,right);
      }        
   }   
}

如果我們編譯並執行以上程式，它會生成以下結果 -

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]
==================================================