“Quicksort Java” Kod odpowiedzi

Jak wykonać szybki sort w Javie?


/*
	This is an implementation of the quick sort algorithm.

	Let n be the size of the list to sort
	Best: O(nlog2(n)) time | O(log2(n)) space
	Average: O(nlog2(n)) time | O(log2(n)) space
	Worst: O(n^2) time | O(log2(n)) space
*/
import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = { 1, 10, 5, 3, 6 };
		quickSort(arr);
		// Below prints: [1, 3, 5, 6, 10]
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] array) {
		// Sort array recursively
		quickSortUtil(array, 0, array.length - 1);
	}

	private static void quickSortUtil(int[] array, int startIdx, int endIdx) {
		// Base case: at this point array is sorted
		if (startIdx >= endIdx) {
			return;
		}
		// Let first value be pivot
		// Sort every other number wrt to pivot
		int pivotIdx = startIdx;
		int leftIdx = startIdx + 1;
		int rightIdx = endIdx;
		// Make sure that element at leftIdx <= to one at pivotIdx
		// and element at rightIdx is >= to one at pivotIdx
		while (leftIdx <= rightIdx) {
			if (array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx]) {
				swap(leftIdx, rightIdx, array);
			}
			if (array[leftIdx] <= array[pivotIdx]) {
				leftIdx++;
			}
			if (array[rightIdx] >= array[pivotIdx]) {
				rightIdx--;
			}
		}

		swap(pivotIdx, rightIdx, array);
		// At the end of current iteration, element at
		// pivot is in its final sorted position
		quickSortUtil(array, startIdx, rightIdx - 1);
		quickSortUtil(array, rightIdx + 1, endIdx);
	}

	private static void swap(int i, int j, int[] array) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
Wissam

Java Quick Sort

import java.util.Arrays;
//so fun to run//try it (;
//Illustrate array in size of 100 Million Integers 
//global arrays only!!
public class Quick {
    static int[] arr = new int[10000000];
    public static void main(String[] args) {//only use with global array!
       
        for(int i=0; i<arr.length;i++){
            arr[i]= (int)(Math.random()*1000);
        }
        quickSort(0, arr.length-1, arr[arr.length-1]);
       //(send 0 to lowi,
      //send the last index in the array to higi, 
      //send to pivot the last value in the array)
       System.out.println(Arrays.toString(arr));
         
    }
    public static void quickSort(int lowi,int higi,int pivot){
        if(higi<=lowi)
          return;
        if(higi - lowi <1)
           return;
        if(higi - lowi == 1){
            if(arr[lowi]>arr[higi])
               swap(lowi, higi);
                 return;
        }
        int temp, next = arr[lowi];
        int higiS = higi, lowiS = lowi,pos = lowi;
        
        while(higi-lowi >= 1){
            if(next<pivot){
                 temp = arr[higi];
                 if(higi == higiS)
                   temp = arr[++pos];
                 else
                   temp = arr[higi];
                
                arr[higi--] = next; 
                }
            else{
                if(lowi<=pos)
                  temp = arr[++pos];
                else
                  temp = arr[lowi];
                
                arr[lowi++] = next;
                }
                next = temp;
            }
            if(lowi<pos)
              lowi = pos-1;
      
        arr[lowi] = pivot;
        
        quickSort(lowi+1, higiS, arr[higiS]);
        if(lowi-1>=0)
        quickSort(lowiS, lowi-1, arr[lowi-1]);
 
        return;
    }
    public static void swap(int fI,int sI){
        int temp = arr[fI];
        arr[fI] = arr[sI];
        arr[sI] = temp;
    }
   
}
Elegant Elephant

Quicksort for ArrayList

public static ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
{
    if (list.isEmpty()) 
        return list; // start with recursion base case
    ArrayList<Vehicle> sorted;  // this shall be the sorted list to return, no needd to initialise
    ArrayList<Vehicle> smaller = new ArrayList<Vehicle>(); // Vehicles smaller than pivot
    ArrayList<Vehicle> greater = new ArrayList<Vehicle>(); // Vehicles greater than pivot
    Vehicle pivot = list.get(0);  // first Vehicle in list, used as pivot
    int i;
    Vehicle j;     // Variable used for Vehicles in the loop
    for (i=1;i<list.size();i++)
    {
        j=list.get(i);
        if (j.compareTo(pivot)<0)   // make sure Vehicle has proper compareTo method 
            smaller.add(j);
        else
            greater.add(j);
    }
    smaller=quickSort(smaller);  // capitalise 's'
    greater=quickSort(greater);  // sort both halfs recursively
    smaller.add(pivot);          // add initial pivot to the end of the (now sorted) smaller Vehicles
    smaller.addAll(greater);     // add the (now sorted) greater Vehicles to the smaller ones (now smaller is essentially your sorted list)
    sorted = smaller;            // assign it to sorted; one could just as well do: return smaller

    return sorted;
}
Worried Wasp

Wdrożenie Java Szybkie sortowanie

// Java implementation of QuickSort
import java.io.*;
 
class GFG{
     
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
   array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
static int partition(int[] arr, int low, int high)
{
     
    // pivot
    int pivot = arr[high];
     
    // Index of smaller element and
    // indicates the right position
    // of pivot found so far
    int i = (low - 1);
 
    for(int j = low; j <= high - 1; j++)
    {
         
        // If current element is smaller
        // than the pivot
        if (arr[j] < pivot)
        {
             
            // Increment index of
            // smaller element
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return (i + 1);
}
 
/* The main function that implements QuickSort
          arr[] --> Array to be sorted,
          low --> Starting index,
          high --> Ending index
 */
static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
         
        // pi is partitioning index, arr[p]
        // is now at right place
        int pi = partition(arr, low, high);
 
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 
// Function to print an array
static void printArray(int[] arr, int size)
{
    for(int i = 0; i < size; i++)
        System.out.print(arr[i] + " ");
         
    System.out.println();
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 10, 7, 8, 9, 1, 5 };
    int n = arr.length;
     
    quickSort(arr, 0, n - 1);
    System.out.println("Sorted array: ");
    printArray(arr, n);
}
}
 
// This code is contributed by Ayush Choudhary
Stupid Scarab

Quicksort Java

//GOD's quicksort
public static <E extends Comparable<E>> List<E> sort(List<E> col) {
  if (col == null || col.isEmpty())
    return Collections.emptyList();
  else {
    E pivot = col.get(0);
    Map<Integer, List<E>> grouped = col.stream()
      .collect(Collectors.groupingBy(pivot::compareTo));
    return Stream.of(sort(grouped.get(1)), grouped.get(0), sort(grouped.get(-1)))
      .flatMap(Collection::stream).collect(Collectors.toList());
  }
}
Yellowed Yacare

Quicksort Java

import java.util.Random;

public class main{
public static void main(String[] args) {
    Random rand=new Random();
    int[]numbers=new int[60000000];
    for (int i = 0; i < numbers.length; i++) {
        numbers[i]=rand.nextInt(10000);
    }
    System.out.println("before");
    quickSort(numbers);
    System.out.println("after");
   // printArray(numbers);
    
}
static void printArray(int []numbers){
    for(int x:numbers){
        System.out.println(x);
    }
}
static void quickSort(int[]numbers){
    quickSort(numbers,0,numbers.length-1);
}
static void quickSort(int[]numbers,int lowIndex,int heighIndex){
if(lowIndex>=heighIndex)return;
int pivotIndex=new Random().nextInt(heighIndex-lowIndex)+lowIndex;
int pivot=numbers[pivotIndex];
int leftPointer=lowIndex;
int righPointer=heighIndex;
swap(numbers, pivotIndex, heighIndex);
while(leftPointer<righPointer){
    while(numbers[leftPointer]<=pivot&&leftPointer<righPointer){
        leftPointer++;
    }
    while(numbers[righPointer]>=pivot&&leftPointer<righPointer){
        righPointer--;
    }
    swap(numbers,leftPointer, righPointer);
}
swap(numbers, leftPointer,heighIndex);
quickSort(numbers,lowIndex,leftPointer-1);
quickSort(numbers, leftPointer+1, heighIndex);

}
static void swap(int[]numbers,int index1,int index2){
int  temp=numbers[index1];
numbers[index1]=numbers[index2];
numbers[index2]=temp;
}
    

 }
Itchy Iguana

Odpowiedzi podobne do “Quicksort Java”

Pytania podobne do “Quicksort Java”

Więcej pokrewnych odpowiedzi na “Quicksort Java” w Java

Przeglądaj popularne odpowiedzi na kod według języka

Przeglądaj inne języki kodu

Shell/Bash
C#
C++
C
CSS
HTML
Java
JavaScript
Objective-C
PHP
Python
Sql
Swift
Ruby
TypeScript
Go
Kotlin
Assembly
R
VBA
Scala
Rust
Dart
Elixir
Clojure
Haskell
Matlab
Erlang
Cobol
Fortran
Scheme
Perl
Groovy
Lua
Julia
Delphi
Abap
Lisp
Prolog
Pascal
ActionScript
Basic
Solidity
PowerShell
GDScript
Excel