Java算法(三)详细解析:快速排序
程序员文章站
2024-03-25 13:21:34
...
原理:
快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,都是采用不断的比较和移动来实现排序的。快速排序是一种非常高效的排序算法,它的实现减少了总的比较次数和移动次数。
选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素或者最后一个元素。
一次循环:先从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。接着分别比较左右两边的序列,重复上述的循环。
我今天写了两个方法,第一种是通过单下标方式,还有一种是双下标方式实现快速排序。
代码中注释都很齐全,这边就不在赘述。
单下标:
/**
* 递归调用
*
* @param array
* @param start
* @param end
*/
public static void quick(int array[], int start, int end) {
//当数组只有一个元素的时候结束
if (end - start < 1) {
return;
}
//获取基数
int part = quickSort(array, start, end);
//和基数相等的就下标加1,继续排序
if (part == start)
quick(array, part + 1, end);
else if (part == end)
quick(array, start, end - 1);
else {
quick(array, start, part - 1);
quick(array, part + 1, end);
}
}
/**
* 实现从小达到快速排序 单下标方式
*
* @param array [ 8 2 1 7 3 5 9 6 ]
* @param start
* @param end
*/
public static int quickSort(int array[], int start, int end) {
//选择一个基数,就用数组最后一个吧
int base = array[end];
//假设数组中所有的数都比基数小 num 代表该数组中一共有几个比他小的数,排序完的时候把基数换到num的位置
int num = start;
//开始比较
for (int i = start; i < end; i++) {
if (array[i] < base) {
//把小于基数的数放在左边
changePosition(array, i, num);
num++;
}
}
//比较完之后把基数放在num的位置上,
changePosition(array, num, end);
return num; //返回基数的位置
}
/**
* 改变两个数的位置
*
* @param array
* @param index1
* @param index2
*/
public static void changePosition(int array[], int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
双下标:
/**
* 快速排序 双下标
*
* @param array
* @param low
* @param high {6, 1, 8, 9, 5, 2, 3, 7, 10, 4}
*/
public static void quickS(int array[], int low, int high) {
int base = array[low]; //基准位数组第一个数
int start = low; //代表从前往后找到了比基准大的数的下标
int end = high; //代表从后往前找到了比基准小的数的下标
while (end > start) {//只有当数组两个数有可比性的时候再进入循环
//先从数组后面往前比较,如果找到了比基准小的,记录位置并和start交换位置
while (end > start && array[end] >= base) {
end--;
}
System.out.println("end= " + end);
//调换位置
if (array[end] <= base) {
changePosition(array, end, start);
System.out.println("从后面调换了一次位置后:" + Arrays.toString(array));
}
//从前往后比较,如果找到了比基准大的,记录位置并和end交换位置
while (end > start && array[start] <= base) {
start++;
}
System.out.println("start= " + start);
if (array[start] >= base) {
changePosition(array, start, end);
System.out.println("从前面调换了一次位置后:" + Arrays.toString(array));
}
}
System.out.println("循环结束后:start= " + start + " end= " + end);
//根据基准分成左右两边再递归
if (start > low)
quickS(array, low, start - 1);
if (end < high)
quickS(array, end + 1, high);
}
最后附上运行函数
public static void main(String[] args) {
int[] arr = {6, 1, 8, 9, 5, 2, 3, 7, 10, 4};
quickS(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。
推荐阅读
-
Java算法(三)详细解析:快速排序
-
Java实现快速排序详细代码
-
快速排序算法原理和Java实现。详细版
-
Java中的快速排序算法
-
Java排序算法之快速排序 博客分类: 数据结构commonjava算法more and more java算法快速排序
-
算法--排序(冒泡,选择,插入,快速) 博客分类: java知识总结 算法java
-
分治法在排序算法中的应用(JAVA)--快速排序(Lomuto划分、Hoare划分、随机化快排)
-
Java实现选择排序算法(含图,注释超详细)
-
【Java学习笔记】排序算法:冒泡排序、快速排序、选择排序、插入排序算法思想及其Java代码实现
-
深入解析堆排序的算法思想及Java代码的实现演示