首页 > 代码库 > java基础算法之快速排序
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) {// 如果i<j while (i < j && value[j] >= temp) {// 从右往左比较,如果i<j且value[j]>=temp j--; } if (i < j) {// 如果i<j，找到有比中间数大的 value[i] = value[j];// 左边的数放右边的数 i++;// 左移一位 } while (i < 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 注意：第一遍快速排序不会直接得到最终结果，只会把比基准数大和比基准数小的数分到基准数的两边。为了得到最后结果，需要再次对基准数两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
java基础算法之快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。