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