快速排序(Quick Sort)
1. 基本思想:
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-
1]和R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置
上,即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划
分过程,直至所有无序子区中的数据元素均已排序为止。
2. 排序过程:
【示例】:
初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13]49 [76 97 65 49]
二趟排序之后 [13]27 [38]49 [49 65]76 [97]
三趟排序之后13 27 38 49 49 [65]76 97
最后的排序结果13 27 38 49 49 65 76 97
java代码实现:
package test.suanfa;
public class QuickSort {
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
QuickSort quicksort = new QuickSort();
quicksort.sort(intgArr, 0, intgArr.length - 1);
for (Integer intObj : intgArr) {
System.out.print(intObj + " ");
}
}
public void sort(Integer[] array, int from, int end) {
quickSort(array, from, end);
}
private void quickSort(Integer[] array, int low, int high) {
/*
*
* 如果分区中的低指针小于高指针时循环;如果low=higth说明数组只有一个元素,无需再处理;
*
* 如果low > higth,则说明上次枢纽元素的位置pivot就是low或者是higth,此种情况
*
* 下分区不存,也不需处理
*/
if (low < high) {
// 对分区进行排序整理
// int pivot = partition1(array, low, high);
int pivot = partition2(array, low, high);
// int pivot = partition3(array, low, high);
/*
*
* 以pivot为边界,把数组分成三部分[low, pivot - 1]、[pivot]、[pivot + 1, high]
*
* 其中[pivot]为枢纽元素,不需处理,再对[low, pivot - 1]与[pivot + 1, high]
*
* 各自进行分区排序整理与进一步分区
*/
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
private int partition1(Integer[] array, int low, int high) {
Integer pivotElem = array[low];// 以第一个元素为中枢元素
// 从前向后依次指向比中枢元素小的元素,刚开始时指向中枢,也是小于与大小中枢的元素的分界点
int border = low;
/*
*
* 在中枢元素后面的元素中查找小于中枢元素的所有元素,并依次从第二个位置从前往后存放
*
* 注,这里最好使用i来移动,如果直接移动low的话,最后不知道数组的边界了,但后面需要
*
* 知道数组的边界
*/
for (int i = low + 1; i <= high; i++) {
// 如果找到一个比中枢元素小的元素
if ((array[i].compareTo(pivotElem)) < 0) {
swap(array, ++border, i);// border前移,表示有小于中枢元素的元素
}
}
/*
*
* 如果border没有移动时说明说明后面的元素都比中枢元素要大,border与low相等,此时是
*
* 同一位置交换,是否交换都没关系;当border移到了high时说明所有元素都小于中枢元素,此
*
* 时将中枢元素与最后一个元素交换即可,即low与high进行交换,大的中枢元素移到了 序列最
*
* 后;如果low <minIndex< high,表 明中枢后面的元素前部分小于中枢元素,而后部分大于
*
* 中枢元素,此时中枢元素与前部分数组中最后一个小于它的元素交换位置,使得中枢元素放置在
*
* 正确的位置
*/
swap(array, border, low);
return border;
}
private int partition2(Integer[] array, int low, int high) {
int pivot = low;// 中枢元素位置,我们以第一个元素为中枢元素
// 退出条件这里只可能是low = high
while (true) {
if (pivot != high) {// 如果中枢元素在低指针位置时,我们移动高指针
// 如果高指针元素小于中枢元素时,则与中枢元素交换
if ((array[high].compareTo(array[pivot])) < 0) {
swap(array, high, pivot);
// 交换后中枢元素在高指针位置了
pivot = high;
} else {// 如果未找到小于中枢元素,则高指针前移继续找
high--;
}
} else {// 否则中枢元素在高指针位置
// 如果低指针元素大于中枢元素时,则与中枢元素交换
if ((array[low].compareTo(array[pivot])) > 0) {
swap(array, low, pivot);
// 交换后中枢元素在低指针位置了
pivot = low;
} else {// 如果未找到大于中枢元素,则低指针后移继续找
low++;
}
}
if (low == high) {
break;
}
}
// 返回中枢元素所在位置,以便下次分区
return pivot;
}
private int partition3(Integer[] array, int low, int high) {
int pivot = low;// 中枢元素位置,我们以第一个元素为中枢元素
low++;
// ----调整高低指针所指向的元素顺序,把小于中枢元素的移到前部分,大于中枢元素的移到后面部分
// 退出条件这里只可能是low = high
while (true) {
// 如果高指针未超出低指针
while (low < high) {
// 如果低指针指向的元素大于或等于中枢元素时表示找到了,退出,注:等于时也要后移
if ((array[low].compareTo(array[pivot])) >= 0) {
break;
} else {// 如果低指针指向的元素小于中枢元素时继续找
low++;
}
}
while (high > low) {
// 如果高指针指向的元素小于中枢元素时表示找到,退出
if ((array[high].compareTo(array[pivot])) < 0) {
break;
} else {// 如果高指针指向的元素大于中枢元素时继续找
high--;
}
}
// 退出上面循环时low = high
if (low == high) {
break;
}
swap(array, low, high);
}
// ----高低指针所指向的元素排序完成后,还得要把中枢元素放到适当的位置
if ((array[pivot].compareTo(array[low])) > 0) {
// 如果退出循环时中枢元素大于了低指针或高指针元素时,中枢元素需与low元素交换
swap(array, low, pivot);
pivot = low;
} else if ((array[pivot].compareTo(array[low])) <= 0) {
swap(array, low - 1, pivot);
pivot = low - 1;
}
// 返回中枢元素所在位置,以便下次分区
return pivot;
}
public void swap(Integer[] array, int i, int j) {
if (i != j) {// 只有不是同一位置时才需交换
Integer tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
分享到:
相关推荐
java十大排序算法实现 1. 冒泡排序(Bubble Sort) 2. 选择排序(Selection Sort) 3. 插入排序(Insertion Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6. 堆排序(Heap Sort) 7. 计数排序...
快速排序(Quick Sort):通过选取一个基准元素,将数组分为两部分,一部分小于基准元素,另一部分大于基准元素,然后递归地对这两部分进行排序。 归并排序(Merge Sort):将数组分成两半,分别对这两部分进行排序...
主要介绍了Java中实现quickSort快速排序算法的方法,文章最后还介绍了一种单向扫描的实现方法,需要的朋友可以参考下
快速排序算法图解,用图片的形式,清晰解构算法原理和实现过程,值得推荐。
//冒泡 Bubble bubble=new Bubble(); bubble.sort(arr); print(arr);//打印结果 //选择 Select select=new Select();... Quick qs=new Quick(); qs.sort(0,arr.length-1,arr); print(arr);//打印结果
使用插入排序优化快速排序的算法实现.java实现,编译环境MyEclipse
面试准备-Java-算法-数据结构 排序 Bubble Sort Selection Sort Insertion Sort Shell Sort Heap Sort Merge Sort Quick Sort Counting Sort Radix Sort MSD Vs LSD Bucket Sort ####快速排序 QuickSort...
使用单元测试功能的快速排序算法测试在这里,在这种快速排序算法中,正在创建几个测试用例以测试代码是否正常。 在此处查找错误以及实际功能的工作方式。
快速排序 7 20 10 合并排序 5 27 4 编译java部分 javac Main.java 编译scala部分 scalac Main.scala quicksort/Sort.scala mergesort/Sort.scala bubblesort/Sort.scala 回购的主要分支具有主要功能,该功能运行各种
快速排序 Heap Sort 堆排序 Merge Sort 归并排序 Topological-Sort-拓扑排序 Dynamic Programming 动态规划 Greedy 贪心算法 Back Track 回溯法 Sliding Window 滑动窗口 Depth First Search 深度优先搜索 Breadth ...