黑马程序员技术交流社区
标题:
java实现的快速排序方法
[打印本页]
作者:
付维翔
时间:
2012-10-25 23:01
标题:
java实现的快速排序方法
本实现方法,不仅可能对一个数组进行排序,也可以指定数组中部分元素进行排序,代码如下:
public class QuicSort {
/**
* 一趟快速排序的方法
*
* @param array
* 所要排序的数组
* @param h
* 排序子列的开始位置
* @param p
* 排序子列的结束位置
* @return 返回当前一趟快速排序后,比较关键字所处于的位置
*/
private static int quickPass(int[] array, int h, int p) {
int i = h;
int j = p;
int x = array[i];// 比较所用的关键字
while (i < j) {
while ((array[j] >= x) && (i < j))
// 自尾端进行比较
j--;
if (i < j) {
array[i] = array[j];// 将小于关键字的记录移至i所指的位置,完成第一次交换
i++;
// 自首端进行比较
while ((array[i] <= x) && (i < j)) {
i++;
if (i < j) {
array[j] = array[i];// 将大于关键字的记录移到j所指的位置
j--;
}
}
}
}
array[i] = x;// 一趟快速排序完成,将x移至正确位置
return i;
}
/**
* 对一个数组的部分进行排序,
*
* @param array
* 排序的数组
* @param s
* 排序开始的位置
* @param t
* 所要排序结束的位置
*/
public static void quickSort(int[] array, int s, int t) {
int i = 0;
if (s < t) {// 未做数组越界检查的代码
i = quickPass(array, s, t);
quickSort(array, s, i - 1);
quickSort(array, i + 1, t);
}
}
/**
* 对一个数组进行快速排序
*
* @param array
* 排序的数组
*/
public static void quickSort(int[] array) {
int s = 0;
int t = array.length - 1;
int i = 0;
if (s < t) {
i = quickPass(array, s, t);
quickSort(array, s, i - 1);
quickSort(array, i + 1, t);
}
}
/**
* 输出排好序的数组
*
* @param array
*/
private static void printArray(int[] array) {
System.out.print("排过序的数组:");
for (int a : array) {
System.out.print(a + " ");
}
System.out.println("");
}
public static void main(String[] args) {
int[] array1 = { 4, 1, 6, 3, 2, 9, 7 };
quickSort(array1);// 此方法对一个数组使用快速排序法做升序排序
System.out.println("对整个数组排序");
printArray(array1);
int[] array2 = { 4, 1, 6, 3, 2, 9, 7 };
// 此方法,提供了对数组部分元素的进行排序的功能,比如,只排序数组中的前五位:
quickSort(array2, 0, 4);
System.out.println("仅对数组中前五位元素进行排序");
printArray(array2);
}
}
复制代码
作者:
许庭洲
时间:
2012-11-11 21:28
值得学习ing!
作者:
廖力
时间:
2012-11-11 21:53
本帖最后由 廖力 于 2012-11-11 21:57 编辑
感觉楼主写得快排不是那么简化啊
我也发个我写的吧 参照了《数据结构(C语言版) 》(严蔚敏 & 吴伟民)
现在看 依然觉得上面的算法最优 无论是占用空间还是运行时间
package com.Lland;
public class Sort {// 快速排序
public void quickSort(int[] array) {
subQuickSort(array, 0, array.length - 1);
}
private void subQuickSort(int[] array, int low, int high) {
if (low < high) {
int pivotTag = partitions(array, low, high);
subQuickSort(array, low, pivotTag - 1);
subQuickSort(array, pivotTag + 1, high);
}
}
private int partitions(int array[], int low, int high) {
int pivotKey = array[low];
while (low < high) {
while (low < high && array[high] >= pivotKey)
high--;
array[low] = array[high];
while (low < high && array[low] <= pivotKey)
low++;
array[high] = array[low];
}
array[low] = pivotKey;
return low;
}
}
复制代码
然后主方法:
package com.Lland;
import java.util.Random;
public class MainClass {
public static void main(String[] args) {
//申明要用的对象
Random r = new Random();
int[] i = new int[20];
Sort s = new Sort();
//随机化数组
for(int j = 0; j < i.length; j++){
i[j] = r.nextInt(100) + 1;
}
//打印数组
for(int j = 0; j < i.length; j++){
System.out.print(i[j]);
if(j < i.length){
System.out.print(", ");
}
}
System.out.println();
//快排
s.quickSort(i);
//打印数组
for(int j = 0; j < i.length; j++){
System.out.print(i[j]);
if(j < i.length){
System.out.print(", ");
}
}
System.out.println();
}
}
复制代码
但是这个也有缺点
是用最低位来做对比值所以还有平衡排序
思想是用最低位和最高位以及中间位3为数中 不大不小的那位来做关键值
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2