Быстрая сортировка

qSort

////Скорость работы алгоритма не зависит от размерности массива, но очень зависит от расположения его элементов. Чем они более хаотично разбросаны
//тем больше нужно времени для его обработки. Обработка массива в тысячу элементов может быть быстрее его обработки из ста элементов.
import java.util.*;
public class QuickSort {
	static Scanner scan = new Scanner(System.in); 
		
public static void main(String[] args){
	    int arrayOfDouble[];        
	    System.out.print("Enter size of array: ");	  
	    int n = scan.nextInt();
	    arrayOfDouble = new int [n];
	    for (int i=0; i<arrayOfDouble.length; i++)
	    arrayOfDouble[i] = (int) ( Math.random() * n);
	    
	    System.out.print("Original array: ");
		 for (int i: arrayOfDouble)
			 System.out.print(i+" ");
		
     long startTime = System.nanoTime();	
     sort(arrayOfDouble, n);
     long estimatedTime = System.nanoTime() - startTime;   
     
     System.out.print(". New array: ");
	 for (int i: arrayOfDouble)
		 System.out.print(i+" ");
	 System.out.println(". Time of sort: " + (startTime-estimatedTime ) + " nanosec.");
	}

	private static void sort(int[] arrayOfDouble, int n){
	    int startIndex = 0;
        int endIndex = arrayOfDouble.length-1;
        swap(arrayOfDouble, startIndex, endIndex, n);
   }
	
	private static void swap(int [] arrayOfDouble, int start, int end, int n){
	 if (start >= end)
         return;
     int i = start, j = end;
     int p = i - (i - j) / 2;
     while (i < j) {
         while (i < p && (arrayOfDouble[i] <= arrayOfDouble[p])) {
             i++;
         }
         while (j > p && (arrayOfDouble[p] <= arrayOfDouble[j])) {
             j--;
         }
         if (i < j) {
             int temp = arrayOfDouble[i];
             arrayOfDouble[i] = arrayOfDouble[j];
             arrayOfDouble[j] = temp;
             if (i == p)
                 p = j;
             else if (j == p)
                 p = i;
		}
		swap(arrayOfDouble, start, p, n);
		swap(arrayOfDouble, p+1, end, n);	
     }
     } 
}