先写代码,一会再总结
public class TestQuickSort {
public static void main(String[] args) {
int[] array = {6, 4, 5, 2, 3, 1};
for (int x : array) {
System.out.print(x + " ");
}
System.out.println();
quickSort(array, 0, array.length - 1);
for (int x : array) {
System.out.print(x + " ");
}
}
// 对分割元素左右段数组进行递归快排,直到左右数组只剩下1个元素为止,left代表数组的起始坐标,right代表数组的终点坐标
public static void quickSort(Comparable[] array, int left, int right) {
// 当left==right时,说明左边或右边的数组只剩下1个元素,跳出快排
if (left < right) {
int i = findPartition(array, left, right);
quickSort(array, left, i - 1);
quickSort(array, i + 1, right);
}
}
// 寻找并返回分割元素坐标
public static int findPartition(Comparable[] array, int left, int right) {
int i = left;
int j = right;
// 用数组第一个元素做为分割元素
Comparable partitionElement = array[left];
Comparable temp;
while (i < j) {
// 从右向左搜索第一个小于分割元素的元素,找到后交换两者的位置
// 容易知道j左移的时候 array[i]就是分割元素,同理 i 右移的时候,array[j]就是分割元素
while (i < j && array[j].compareTo(partitionElement >= 0) {
j--;
}
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 从左向右搜索第一个大于分割元素的元素,找到后交换两者的位置
while (i < j && array[i].comparaTo(partitionElement <= 0) {
i++;
}
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
总结出的几个问题:
1.快排有两种实现方法:
(1)第一种如我的代码所示,从右向左找(从右想做找)的跳出条件为(i < j),并且在找到元素后立即与分割元素交换位置.看这一步
// 从右向左搜索第一个小于分割元素的元素,找到后交换两者的位置
while (i < j && array[j].compareTo(partitionElement >= 0) {
j--;
}
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
(2)第二种是从右向左找(从右想做找)的跳出条件为(i < right) right为数组边界,并且找到元素后不和分割元素交换值,而是交换左右两个找到的值.具体实现略过
2.我这种方法只能先从右往左找第一个小于分割元素的元素
不能先从左往右找第一个大于分割元素的元素
分享到:
相关推荐
本资料包“C++归并排序与快速排序实现.zip”主要关注两种经典的排序算法:归并排序(Merge Sort)和快速排序(Quick Sort)。下面我们将详细探讨这两种排序算法以及如何用C++实现它们。 **归并排序(Merge Sort)**...
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
快速排序实现,实现时间性能分析(IDE:xcode)
Python 算法 13快速排序实现.mp4
6. **边界处理**:在实际的MIPS快速排序实现中,还需要考虑数组为空或只包含一个元素的情况,这些情况不需要排序,可以直接返回。 7. **优化**:为了提高效率,可以考虑使用尾递归优化,或者在划分过程中减少不必要...
以下是一个简单的C++快速排序实现的步骤: 1. **选择基准**:可以从数组的任意位置选取一个元素作为基准,常见的做法是从第一个元素或者最后一个元素开始。 2. **分区**:从数组的第二个元素开始,遍历数组,如果...
C语言数据结构实现快速排序代码,已经过调试可以直接使用。
### 快速排序的核心概念与实现 #### 一、快速排序简介 快速排序是一种非常高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)于1960年提出。它采用分治法策略来把一个序列分为较小和较大的两个子序列,...
在给出的C++代码中,可以看到改进的快速排序实现如下: - `improved_qsort`函数实现了改进后的快速排序算法。通过设置双指针`i`和`j`,并利用基准元素`pivot`来进行分割操作。 - `quick_sort`函数实现了原始的快速...
用c++写的一个快速排序程序的实现,程序简洁,可以直接用在C语言上
c++实现快速排序
快速排序实现 快速排序是一种非常高效的排序算法,它的基本思想是选择一个基准值,通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有记录都比另一部分的所有记录都要小,然后分别对这两部分记录继续...
在C语言中实现链表快速排序,首先需要理解链表和快速排序的基本概念。链表不同于数组,它不连续存储数据,而是通过指针连接各个节点。每个节点包含数据元素和指向下一个节点的指针。快速排序的核心是“分区操作”和...
4. **myQuickSort.h**:这个名字可能表示这是一个自定义版本的快速排序实现,可能包含了一些特定的优化或者改进。例如,可能会包含针对已排序或接近排序情况的优化,或者处理小数组的特殊策略。 5. **print.h**:这...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R....总的来说,这个压缩包提供了一个非递归实现快速排序的完整示例,通过自定义栈的数据结构,实现了快速排序算法,适用于理解和学习快速排序的非递归实现方式。
在C#中实现快速排序,我们通常会用到递归函数。首先,我们需要一个方法来选取枢轴,这可以是数组的第一个元素、最后一个元素,或者数组中间的元素,也可以是三数取中法,即取首、尾、中间三个元素的中位数作为枢轴,...
在提供的代码片段中,可以看到一个简单的快速排序实现。具体步骤如下: 1. **定义函数**:`void QSort(ElemType R[], int n)`,其中`ElemType`表示数组元素的数据类型,`R`是待排序的数组,`n`是数组的长度。 2. **...
Erlang 是一种面向并发的函数式编程语言,其快速排序实现也非常简洁。 ```erlang q_sort([]) -> []; q_sort([H|R]) -> q_sort([X||X,X]) ++ [H] ++ q_sort([X||X,X>=H]). ``` #### 五、快速排序的应用场景 由于...
快速排序实现 - **快速排序函数** `void quick(Sqlist& L, int m, int n)`: - 功能:对线性表`L`在索引`m`至`n`之间的元素进行快速排序。 - 实现:首先检查边界条件,如果起始索引大于等于终止索引则返回;接着...
以下是对快速排序实现的详细解析: 1. **交换函数**(`swap()`):这是一个辅助函数,用于交换两个整数变量的值。在快速排序过程中,当需要调整元素的位置时,会用到这个函数。 2. **分区函数**(`partition()`)...