亚洲国产日韩欧美一区二区三区,精品亚洲国产成人av在线,国产99视频精品免视看7,99国产精品久久久久久久成人热,欧美日韩亚洲国产综合乱

Home Java javaTutorial Understanding Quick Sort Algorithm (with Examples in Java)

Understanding Quick Sort Algorithm (with Examples in Java)

Jan 18, 2025 am 02:05 AM

Detailed explanation of QuickSort algorithm: an efficient sorting tool

QuickSort is an efficient sorting algorithm based on the divide-and-conquer strategy. The divide-and-conquer method decomposes the problem into smaller sub-problems, solves these sub-problems separately, and then combines the solutions of the sub-problems to obtain the final solution. In quick sort, an array is divided by selecting a partition element, which determines the split point of the array. Before partitioning, the position of the partitioning element is rearranged so that it is before the element that is larger than it and after the element that is smaller than it. The left and right subarrays will be divided recursively in this manner until each subarray contains only one element, at which point the array is sorted.

How quick sort works

Let us sort the following array in ascending order as an example:

Understanding Quick Sort Algorithm (with Examples in Java)

Step 1: Select the pivot element

We choose the last element as the pivot:

Understanding Quick Sort Algorithm (with Examples in Java)

Step 2: Rearrange pivot elements

We place the pivot element before elements that are larger than it and after elements that are smaller than it. To do this, we will iterate through the array and compare the pivot to each element before it. If an element larger than the pivot is found, we create a second pointer for it:

Understanding Quick Sort Algorithm (with Examples in Java)

If an element smaller than the pivot is found, we swap it with the second pointer:

Understanding Quick Sort Algorithm (with Examples in Java)

Repeat this process, setting the next element larger than the pivot to the second pointer, swapping if an element smaller than the pivot is found:

Understanding Quick Sort Algorithm (with Examples in Java)

Continue this process until you reach the end of the array:

Understanding Quick Sort Algorithm (with Examples in Java)

After completing the element comparison, the element smaller than the pivot has been moved to the right, then we swap the pivot with the second pointer:

Understanding Quick Sort Algorithm (with Examples in Java)

Step 3: Divide the array

Divide the array according to the partition index. If we represent the array as arr[start..end], then by dividing the array by partition, we can get the left subarray arr[start..partitionIndex-1] and the right subarray arr[partitionIndex 1..end].

Understanding Quick Sort Algorithm (with Examples in Java)

Continue dividing the subarrays in this way until each subarray contains only one element:

Understanding Quick Sort Algorithm (with Examples in Java)

At this point, the array is sorted.

Understanding Quick Sort Algorithm (with Examples in Java)

Quick sort code implementation

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個(gè)元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個(gè)較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動(dòng)到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個(gè)指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

Code interpretation

quickSort method: First call the partition method to divide the array into two sub-arrays, and then call quickSort recursively to sort the left and right sub-arrays. This process continues until all subarrays contain exactly one element, at which point the array is sorted.

partition Method: Responsible for dividing the array into two sub-arrays. It first sets the pivot and the pointer to the next larger element, then iterates through the array, moving elements smaller than the pivot to the left. After that it swaps the pivot with the second pointer and returns the partition position.

Run the above code, the console will output the following:

Unsorted array: [8, 6, 2, 3, 9, 4] Sorted array: [2, 3, 4, 6, 8, 9]

Time complexity

Best case (O(n log n)): The best case occurs when the pivot splits the array into two nearly equal parts every time.

Average case (O(n log n)): In the average case, the pivot splits the array into two unequal parts, but the recursion depth and number of comparisons are still proportional to n log n.

Worst case (O(n2)): The worst case occurs when the pivot always splits the array into very unequal parts (e.g. one part has only one element and the other has n-1 elements) . This can happen, for example, when sorting an array in reverse order, and the pivot is chosen poorly.

Space complexity (O(log n)): Quick sort is usually implemented in-place and does not require additional arrays.

The above is the detailed content of Understanding Quick Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Differences Between Callable and Runnable in Java Differences Between Callable and Runnable in Java Jul 04, 2025 am 02:50 AM

There are three main differences between Callable and Runnable in Java. First, the callable method can return the result, suitable for tasks that need to return values, such as Callable; while the run() method of Runnable has no return value, suitable for tasks that do not need to return, such as logging. Second, Callable allows to throw checked exceptions to facilitate error transmission; while Runnable must handle exceptions internally. Third, Runnable can be directly passed to Thread or ExecutorService, while Callable can only be submitted to ExecutorService and returns the Future object to

Asynchronous Programming Techniques in Modern Java Asynchronous Programming Techniques in Modern Java Jul 07, 2025 am 02:24 AM

Java supports asynchronous programming including the use of CompletableFuture, responsive streams (such as ProjectReactor), and virtual threads in Java19. 1.CompletableFuture improves code readability and maintenance through chain calls, and supports task orchestration and exception handling; 2. ProjectReactor provides Mono and Flux types to implement responsive programming, with backpressure mechanism and rich operators; 3. Virtual threads reduce concurrency costs, are suitable for I/O-intensive tasks, and are lighter and easier to expand than traditional platform threads. Each method has applicable scenarios, and appropriate tools should be selected according to your needs and mixed models should be avoided to maintain simplicity

Understanding Java NIO and Its Advantages Understanding Java NIO and Its Advantages Jul 08, 2025 am 02:55 AM

JavaNIO is a new IOAPI introduced by Java 1.4. 1) is aimed at buffers and channels, 2) contains Buffer, Channel and Selector core components, 3) supports non-blocking mode, and 4) handles concurrent connections more efficiently than traditional IO. Its advantages are reflected in: 1) Non-blocking IO reduces thread overhead, 2) Buffer improves data transmission efficiency, 3) Selector realizes multiplexing, and 4) Memory mapping speeds up file reading and writing. Note when using: 1) The flip/clear operation of the Buffer is easy to be confused, 2) Incomplete data needs to be processed manually without blocking, 3) Selector registration must be canceled in time, 4) NIO is not suitable for all scenarios.

Best Practices for Using Enums in Java Best Practices for Using Enums in Java Jul 07, 2025 am 02:35 AM

In Java, enums are suitable for representing fixed constant sets. Best practices include: 1. Use enum to represent fixed state or options to improve type safety and readability; 2. Add properties and methods to enums to enhance flexibility, such as defining fields, constructors, helper methods, etc.; 3. Use EnumMap and EnumSet to improve performance and type safety because they are more efficient based on arrays; 4. Avoid abuse of enums, such as dynamic values, frequent changes or complex logic scenarios, which should be replaced by other methods. Correct use of enum can improve code quality and reduce errors, but you need to pay attention to its applicable boundaries.

How Java ClassLoaders Work Internally How Java ClassLoaders Work Internally Jul 06, 2025 am 02:53 AM

Java's class loading mechanism is implemented through ClassLoader, and its core workflow is divided into three stages: loading, linking and initialization. During the loading phase, ClassLoader dynamically reads the bytecode of the class and creates Class objects; links include verifying the correctness of the class, allocating memory to static variables, and parsing symbol references; initialization performs static code blocks and static variable assignments. Class loading adopts the parent delegation model, and prioritizes the parent class loader to find classes, and try Bootstrap, Extension, and ApplicationClassLoader in turn to ensure that the core class library is safe and avoids duplicate loading. Developers can customize ClassLoader, such as URLClassL

Exploring Different Synchronization Mechanisms in Java Exploring Different Synchronization Mechanisms in Java Jul 04, 2025 am 02:53 AM

Javaprovidesmultiplesynchronizationtoolsforthreadsafety.1.synchronizedblocksensuremutualexclusionbylockingmethodsorspecificcodesections.2.ReentrantLockoffersadvancedcontrol,includingtryLockandfairnesspolicies.3.Conditionvariablesallowthreadstowaitfor

Handling Common Java Exceptions Effectively Handling Common Java Exceptions Effectively Jul 05, 2025 am 02:35 AM

The key to Java exception handling is to distinguish between checked and unchecked exceptions and use try-catch, finally and logging reasonably. 1. Checked exceptions such as IOException need to be forced to handle, which is suitable for expected external problems; 2. Unchecked exceptions such as NullPointerException are usually caused by program logic errors and are runtime errors; 3. When catching exceptions, they should be specific and clear to avoid general capture of Exception; 4. It is recommended to use try-with-resources to automatically close resources to reduce manual cleaning of code; 5. In exception handling, detailed information should be recorded in combination with log frameworks to facilitate later

How does a HashMap work internally in Java? How does a HashMap work internally in Java? Jul 15, 2025 am 03:10 AM

HashMap implements key-value pair storage through hash tables in Java, and its core lies in quickly positioning data locations. 1. First use the hashCode() method of the key to generate a hash value and convert it into an array index through bit operations; 2. Different objects may generate the same hash value, resulting in conflicts. At this time, the node is mounted in the form of a linked list. After JDK8, the linked list is too long (default length 8) and it will be converted to a red and black tree to improve efficiency; 3. When using a custom class as a key, the equals() and hashCode() methods must be rewritten; 4. HashMap dynamically expands capacity. When the number of elements exceeds the capacity and multiplies by the load factor (default 0.75), expand and rehash; 5. HashMap is not thread-safe, and Concu should be used in multithreaded

See all articles