快速排序

鸿蒙原生应用开发者激励计划发布！最高获百万现金！点击立即参与

package com.victor.sort.algorithms;

import java.util.ArrayList;

import com.victor.sort.seeds.*;

/**
 * 快速排序
 * @author 黑妹妹牙膏
 *
 */
public class Quick extends SortAlgorithms {
	/**
	Algorithm
	# choose pivot
	swap a[1,rand(1,n)]

	# 2-way partition
	k = 1
	for i = 2:n, if a[i] < a[1], swap a[++k,i]
	swap a[1,k]
	→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

	# recursive sorts
	sort a[1..k-1]
	sort a[k+1,n]
	Properties
	■Not stable 
	■O(lg(n)) extra space (see discussion) 
	■O(n2) time, but typically O(n·lg(n)) time 
	■Not adaptive 
	Discussion
	When carefully implemented, quick sort is robust and has low overhead. When a stable sort is not needed, quick sort is an excellent general-purpose sort -- although the 3-way partitioning version should always be used instead. 

	The 2-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, and, critically, exhibits O(n2) time when there are few unique keys. A more efficient and robust 2-way partitioning method is given in Quicksort is Optimal by Robert Sedgewick and Jon Bentley. The robust partitioning produces balanced recursion when there are many values equal to the pivot, yielding probabilistic guarantees of O(n·lg(n)) time and O(lg(n)) space for all inputs. 

	With both sub-sorts performed recursively, quick sort requires O(n) extra space for the recursion stack in the worst case when recursion is not balanced. This is exceedingly unlikely to occur, but it can be avoided by sorting the smaller sub-array recursively first; the second sub-array sort is a tail recursive call, which may be done with iteration instead. With this optimization, the algorithm uses O(lg(n)) extra space in the worst case. 
	*/
	@Override
	protected ArrayList<Integer> doSort(ArrayList<Integer> Alist) {
		return sort(Alist,0,Alist.size()-1);
	}
	
	private ArrayList<Integer> sort(ArrayList<Integer> Alist,int from,int end) {
		if(from >= end) return Alist;
		ArrayList<Integer> a = Alist;
		int n = end - from;
		//choose pivot
		java.util.Random rd = new java.util.Random();
		int pivot = rd.nextInt(n) + from;
		int temp = a.get(from);
		a.set(from, a.get(pivot));
		a.set(pivot, temp);
		moveMentIncrease();
		// 2-way partition
		int k = from;
		for(int i=from+1;i<end+1;i++)
		{
			if(a.get(i)<a.get(from))
			{
				k++;
				temp = a.get(k);
				a.set(k, a.get(i));
				a.set(i, temp);
				moveMentIncrease();
			}
		}
		temp = a.get(k);
		a.set(k, a.get(from));
		a.set(from, temp);
		moveMentIncrease();
//		print(a,k,from,end);
		int firstPartK = k;
		a = sort(a,from,firstPartK);
		a = sort(a,firstPartK+1,end);
		return a;
	}
	
	public void print(ArrayList<Integer> a,int k,int from,int end)
	{
		System.out.println("Items after sorted:");
		System.out.println("#######################################");
		for(int i=0;i<a.size();i++)
		{
			if(i==from)
			{
				System.out.println("[-"+i+"] : "+a.get(i));
			}
			else
			{
				if(i==end)
				{
					System.out.println("[+"+i+"] : "+a.get(i));
				}
				else
				{
					if(i==k)
					{
						System.out.println("["+i+"] : "+a.get(i));
					}
					else
					{
						System.out.println(i+": "+a.get(i));
					}
				}
			}
		}
		System.out.println("#######################################");
	}

	@Override
	public String getName() {
		return "Quick";
	}
	
	public static void main(String[] args)
	{
		Seeds seed1 = new Random();
		Seeds seed2 = new NearSorted();
		Seeds seed3 = new Reversed();
		Seeds seed4 = new FewUniqueKeys();
		SortAlgorithms SA = new Quick();
		SA.sort(seed1,100);
		//SA.print();
		SA.sort(seed2,100);
		SA.sort(seed3,100);
		SA.sort(seed4,100);
	}

}

询问AI