【排序算法】快速排序

losetowin 发布于:2017-2-5 10:41 分类:Java  有 2149 人浏览,获得评论 0 条 标签: 排序算法 快速排序 

本文地址:http://www.dutycode.com/paixusuanfa_kuaisupaixu_java_shixian.html
除非注明,文章均为 www.dutycode.com 原创,欢迎转载!转载请注明本文地址,谢谢。
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤为:
  1. 从数列中挑出一个元素,称为"基准"(pivot),
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

Java代码实现:


public class QuickSort {

	
	private static int[] arr;
	
	private static void quickSortRecursion(int start, int end){
		
		if (start >= end){
			return ;
		}
		int mid = arr[end];
		int left = start, right = end -1;
		
		while (left < right){
			while (arr[left] < mid && left < right){
				left ++;
			}
			while (arr[right] >= mid && left < right){
				right--;
			}
			swap(left, right);
		}
		
		if (arr[left] >= arr[end]){
			swap(left, end);
		}else {
			left ++;
		}
		
		
		quickSortRecursion(start, left -1);
		quickSortRecursion(left + 1, end);
		
	}
	
	/**
	 * 算法步骤
	 * 1、从数列中挑出一个元素,称为"基准"(pivot),
	 * 2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素
         * 比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后
         * 该基准就处于数列的中间位置。这个称为分区(partition)操作。
	 * 3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
	 * 
	 * @param numbers
	 */
	private static void quickSort(int[] numbers){
		arr = numbers;
		quickSortRecursion(0, arr.length-1);
	}
	
	private static void swap(int left, int right){
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
	}
	
	
	public static void main(String[] args) {
		int [] arr = {10,9,11,38,27,3,19,4};
		quickSort(arr);
		
		for (int t : arr){
			System.out.print(t + ",");
		}
	}
	
}



版权所有:《攀爬蜗牛》 => 《【排序算法】快速排序
本文地址:https://www.dutycode.com/paixusuanfa_kuaisupaixu_java_shixian.html
除非注明,文章均为 《攀爬蜗牛》 原创,欢迎转载!转载请注明本文地址,谢谢。