首页 > 代码库 > 快速排序算法--java
快速排序算法--java
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
举例说明一下吧，这个可能不是太好理解。假设要排序的序列为
2 2 4 9 3 6 7 1 5 首先用2当作基准，使用i j两个指针分别从两边进行扫描，把比2小的元素和比2大的元素分开。首先比较2和5，5比2大，j左移
2 2 4 9 3 6 7 1 5 比较2和1，1小于2，所以把1放在2的位置
2 1 4 9 3 6 7 1 5 比较2和4，4大于2，因此将4移动到后面
2 1 4 9 3 6 7 4 5 比较2和7，2和6，2和3，2和9，全部大于2，满足条件，因此不变
经过第一轮的快速排序，元素变为下面的样子
[1] 2 [4 9 3 6 7 5]
之后，在把2左边的元素进行快排，由于只有一个元素，因此快排结束。右边进行快排，递归进行，最终生成最后的结果。
1 package com.zc.manythread; 2 3 import java.util.Random; 4 5 /** 6 * 快速排序 7 * @author Administrator 8 * 9 */ 10 public class QSort { 11 int [] date; 12 13 public QSort(int[] date) { 14 15 this.date=date; 16 17 } 18 /** 19 * 交换函数 20 * @param a 21 * @param i 22 * @param j 23 */ 24 private void swap(int a[],int i,int j) { 25 int T; 26 T=a[i]; 27 a[i]=a[j]; 28 a[j]=T; 29 } 30 /******************* 31 * 排序函数 32 * @param a 33 * @param lo0 34 * @param hi0 35 * @return 36 */ 37 int[] QuickSort(int a[],int lo0,int hi0){//分治法，作用就是将数组分为A[lo0..q-1] 和A[q+1..hi0] 38 int lo=lo0; 39 int hi=hi0; 40 int mid; 41 if (hi0>lo0) { 42 mid=a[(hi0+lo0)/2]; 43 while(lo<=hi){ 44 while((lo<hi0)&&(a[lo]<mid)) ++lo; 45 46 while((hi>lo0)&&(a[hi]>mid)) --hi; 47 48 if (lo<=hi) { 49 swap(a,lo,hi); 50 ++lo; 51 --hi; 52 } 53 54 } 55 if (lo0<hi) { 56 QuickSort(a, lo0, hi); 57 } 58 if (lo<hi0) { 59 QuickSort(a, lo, hi0); 60 } 61 } 62 return a; 63 } 64 /************** 65 * 66 * 创建有重复数组数据 67 * *****************/ 68 private static int[] createDate(int count) { 69 int[] data=http://www.mamicode.com/new int[count]; 70 for (int i = 0; i < data.length; i++) { 71 data[i]=(int)(Math.random()*count); 72 } 73 return data; 74 } 75 /** 76 * 无重复数组数据 77 * @param count 78 * @return 79 */ 80 private static int[] createDate1(int count) { 81 82 int[] data=http://www.mamicode.com/new int[count]; 83 Random rand = new Random(); 84 boolean[] bool = new boolean[100]; 85 int num = 0; 86 for (int i = 0; i < count; i++) { 87 do { 88 // 如果产生的数相同继续循环 89 num = rand.nextInt(100); 90 } while (bool[num]); 91 bool[num] = true; 92 93 data[i]=num; 94 } 95 return data; 96 } 97 /**************主函数*****************/ 98 public static void main(String[] args) { 99 final int count=10;100 int[] data=http://www.mamicode.com/createDate1(count);101 for (int n:data) {102 System.out.print(n+"\t");103 }104 QSort data1=new QSort(data);105 System.out.println();106 int[] a=data1.QuickSort(data,0, count-1);107 for (int n:a) {108 System.out.print(n+"\t");109 }110 }111 }
结果如下：
快速排序算法--java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。