赞
踩
快速排序(英文名:Quicksort,有时候也叫做划分交换排序)是一个高效的排序算法,由Tony Hoare在1959年发明(1961年公布)。当情况良好时,它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这是一个分治算法,而且它就在原地排序。
所谓原地排序,就是指在原来的数据区域内进行重排,就像插入排序一般。而归并排序就不一样,它需要额外的空间来进行归并排序操作。为了在线性时间与空间内归并,它不能在线性时间内实现就地排序,原地排序对它来说并不足够。而快速排序的优点就在于它是原地的,也就是说,它很节省内存。由于快速排序采用了分治算法,所以:
一、分解:本质上快速排序把数据划分成几份,所以快速排序通过选取一个关键数据,再根据它的大小,把原数组分成两个子数组:第一个数组里的数都比这个主元数据小或等于,而另一个数组里的数都比这个主元数据要大或等于。
二、解决:用递归来处理两个子数组的排序。 (也就是说,递归地求上面图示中左半部分,以及递归地求上面图示中右半部分。)
三、合并:因为子数组都是原址排序,所以不需要合并操作,通过上面两步后数组已经排好序了。
所以快速排序的主要思想是递归与划分。- package com.lpj.algorithm;
-
- import java.util.Arrays;
-
- /**
- * @author LPJ
- * @version 1.0 创建时间:2018年3月3日 上午11:23:57
- * describe:原理:采用单轴双向比较方法,设置基准值,首次循环从后向前对比,当小于基准值时,交换,然后从开始
- * 位置与基准值进行比较,当大于基准值时,进行交换。全部结束后,元素分为两部分,右侧为大于基准值,左侧为小于基准值
- * 然后将两部分分别递归调用排序方法
- */
- public class QucikSort {
- public static void main(String[] args) {
- int [] aa = {3,2,45,21,5};
- System.out.println(Arrays.toString(aa));
- aa = quickSort1(aa);
- System.out.println(Arrays.toString(aa));
- }
-
-
- static int[] quickSort1(int [] a) {
- return quickSort(a, 0, a.length - 1);
- }
- //快速排序方法
- static int[] quickSort(int [] a,int low, int high) {
- int start = low;//记录起始位置
- int end = high;//记录终点位置
- int key = a[low];//记录分界点值,基准值
- //首次循环
- while(start < end) {
- //从后向前比较,如果大于基准值,继续向前
- while(start < end && a[end] >= key)
- end--;
- //如果小于基准值,进行交换
- a[start] = a[end] + (a[end] = a[start]) * 0;
- //从前向后比较,如果小于基准值,继续向后
- while(start < end && a[start] <= key)
- start++;
- //如果大于基准值,进行交换
- a[start] = a[end] + (a[end] = a[start]) * 0;
- }
- //递归,分成两部分,此时start = end
- //基准值以及以前的部分,重复递归end-1
- //基准值以及以后的部分,重复递归end+1
- if(start > low) quickSort(a, low, end - 1);
- if(end < high) quickSort(a, end + 1, high);
- return a;
- }
-
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。