java基础算法之快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。在大学学过之后现在基本忘了，最近在好多地方都看到说快速排序在面试会问到，于是自己也准备重新拾起以前忘记的东西来，慢慢的积累自己的基础知识。fighting

算法概念

快速排序由C. A. R. Hoare在1962（50多年了呢）年提出，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列（摘自百度百科）。

快速排序采用了一种分治的策略，所以有时候我们也称为分治算法。

算法思想

1．先从数列中取出一个数作为基准数，一般会取第一个数做为基准数。

2．然后对数列进行分区，首先将比这个基准数大的数全放到它的右边，小于或等于基准数的数全放到它的左边（一刀切，左边小于基准数，右边大于基准数）。

3．再对划分的左右区间重复第二步，直到各区间只剩一个数就完成了排序。

下面画一个详细的大图，只画了第一趟排序的过程，知道第一躺怎么排序，后面都是一样的。

算法代码

package com.roc.Quicksort;/** * 快速排序 * * @author liaowp * */public class Quicksort { static void sort(int value[], int left, int right) { if (left < right)="" {//="" 判断左边的下标是小于右="" int="" i="left," j="right;//" i为小值，j为大值="" int="" temp="value[left];//" 默认中间数为temp，即最左边的数="" while="" (i="">< j)="" {//="">< j="" &&="" value[j]="">= temp) {// 从右往左比较,如果i=temp j--; } if (i < j)="" {//="">< j="" &&="" value[i]="">< temp)="" {//="" 从左往右找="" i++;="" }="" if="" (i="">< j)="" {//="" 找到有比中间数小的，替换到右边="" value[j]="value[i];" j--;="" }="" }="" value[i]="temp;" for="" (int="" n="0;" n="">< value.length;="" n++)="" {="" system.out.print(value[n]="" +="" '="" ');="" }="" system.out.println;="" sort(value,="" left,="" i="" -="" 1);//="" 左边的重复="" sort(value,="" i="" +="" 1,="" right);//="" 右边的重复="" }="" }="" public="" static="" void="" main(string[]="" args)="" {="" int="" value="{" 5,="" 1,="" 8,="" 4,="" 15="" };="" system.out.print('原始数据：');="" for="" (int="" i="0;" i="">< value.length;="" i++)="" {="" system.out.print(value[i]="" +="" '="" ');="" }="" system.out.println;="" sort(value,="" 0,="" 4);="" system.out.print('排序结果：');="" for="" (int="" i="0;" i="">< value.length;="" i++)="" {="" system.out.print(value[i]="" +="" '="" ');="" }="">

代码结果如下：

原始数据：5 1 8 4 15 4 1 5 8 15 1 4 5 8 15 1 4 5 8 15 排序结果：1 4 5 8 15

注意：第一遍快速排序不会直接得到最终结果，只会把比基准数大和比基准数小的数分到基准数的两边。为了得到最后结果，需要再次对基准数两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。