快速排序是对冒泡排序的一种改进。它和堆排法、希尔法一样效率较高，但稳定性稍差。
对于小的数组，常用的排序方法效率相差不大，但对于大的数组，用以上的方法进行排序对有好的效率。
最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlogn)。
它的基本思想是：
1、通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小
2、然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
另外 java没指针概念 可以认为是句柄
假设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它
的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一趟快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=0，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[0]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：升序（前小后大）
待排序的数组A的值分别是：（初始关键数据X：=49(将数组分为两部分之前，x值不变)）
A[0] A[1] A[2] A[3] A[4] A[5] A[6]：
49 38 65 97 76 13 27
开始：x = 49;
i = 0;从前往后搜索用变量i
n = 7;数组长度
j = n;从后往返前搜索用变量J
1、进行如上所说的第三步：由后向前搜索 j= j-1=6,也就是用x=49与A[6]比较，
A[0] A[1] A[2] A[3] A[4] A[5] A[6]：
49 38 65 97 76 13 27
X j=j-1=6
x大于A[6]，交换位置
进行第一次交换后： 27 38 65 97 76 13 49
2、进行如上所说的第四步：由前向后搜索 i=i+1=1,也就是用x=49与A[1]比较，
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
27 38 65 97 76 13 49
i=i+1 x
A[1]大于x,所以不变，所以继续由前向后搜索 i= i+1=2,也就是x=49与A[2]比较，
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
27 38 65 97 76 13 49
i=i+1 x
A[2]大于x，交换位置
进行第二次交换后： 27 38 49 97 76 13 65
3、进行如上所说的第三步：由后向前搜索 j= j-1=5,也就是用x=49与A[5]比较，
A[0] A[1] A[2] A[3] A[4] A[5] A[6]：
27 38 49 97 76 13 65
X j=j-1=5
x大于A[5]，交换
进行第三次交换后： 27 38 13 97 76 49 65
4、进行如上所说的第四步：由前向后搜索i=i+1=3,也就是用x=49与A[3]比较，
A[0] A[1] A[2] A[3] A[4] A[5] A[6]：
27 38 13 97 76 49 65
i=i+1=3 x
A[5]>x,交换
进行第四次交换后： 27 38 13 49 76 97 65
5、之后，i=j=4
此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：
27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似
的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述
数组A的快速排序的全过程如下所示：
初始状态 【49 38 65 97 76 13 27】
进行一次快速排序之后划分为 【27 38 13】 49 【76 97 65】
分别对前后两部分进行快速排序 【13】 27 【38】
【65】 76 【97】
结束
网上的示例代码：
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
//声明数组
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
//应用快速排序方法
quickSort(nums, 0, nums.length-1);
//显示排序后的数组
for(int i = 0; i < nums.length; ++i) {
System.out.print(nums[i] + ",");
}
System.out.println("");
}
/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0; //相当于i，左
int hi = hi0; //相当于j, 右
if (lo >= hi) // 判断是否到中间了
return;
//确定指针方向的逻辑变量，也就是从左搜索还是向右搜索
boolean transfer=true;
while (lo != hi) {
if (a[lo] > a[hi]) {
//交换数字
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
//决定下标移动，还是上标移动
transfer = (transfer == true) ? false : true;
}
//将指针向前或者向后移动
if(transfer)
hi--;
else
lo++;
//显示每一次指针移动的数组数字的变化
/*for(int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ",");
}
System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
System.out.println("");*/
}
//将数组分开两半，确定每个数字的正确位置
lo--;
hi++;
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
}
package com.sort;
public class TestSort {
//
/**
* 快速排序
*
* @param arr
* @param low
* @param high
* @return
*/
public int getMiddle(Integer[] arr, int low, int high) {
int tmp = arr[low]; // 数组的第一个作为中轴
while (low < high) {
// 从后向前搜素 找比中轴数 小的数(list[high]<=tmp)
while (low < high && arr[high] > tmp) {
high--;
}
arr[low] = arr[high]; // 比中轴小的记录移到低端
// 从前向后搜素 找比中轴数 大的数(list[low]=>tmp)
while (low < high && arr[low] < tmp) {
low++;
}
arr[high] = arr[low]; // 比中轴大的记录移到高端
}
arr[low] = tmp; // 中轴记录到尾
listArray(arr);
System.out.println("\r\n");
return low; // 返回中轴的位置
}
public void _quickSort(Integer[] list, int low, int high) {
if (low < high) {
int middle = getMiddle(list, low, high); // 将list数组进行一分为二
// System.out.println("middle index: "+middle +" data:"+list[middle]);
_quickSort(list, low, middle - 1); // 对低字表进行递归排序
_quickSort(list, middle + 1, high); // 对高字表进行递归排序
}
}
public void quick(Integer[] str) {
if (str.length > 0) { // 查看数组是否为空
_quickSort(str, 0, str.length - 1);
}
}
private void listArray(Integer[] arr) {
for (Integer i : arr) {
System.out.print(i+", ");
}
System.out.println();
}
public static void main(String[] args) {
TestSort qs = new TestSort();
Integer[] arr = { 34, 3, 53, 2, 23, 7, 14, 10 };
qs.listArray(arr);
System.out.println();
qs.quick(arr);
qs.listArray(arr);
}
}
相关推荐
### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录...
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
快速排序是一种高效的排序算法，在计算机科学和数学中被广泛研究。其基本原理是分治法策略，即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn)，但在最坏的情况下，它的时间复杂度可...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），即把一个大问题分解成若干个小问题来解决，最终将小问题的结果合并得到原问题的解。在这...
本主题将深入探讨四种常见的排序算法：堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先，让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法，利用了数据...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再...
快速排序算法是一种有效的排序算法，虽然算法在最坏的情况下运行时间为 O(n^2)，但由于平均运行时间为 O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在...
（1）用随机快速排序的方法，对输入的数值以从大到小的顺序进行快速排序。 （2）对随机快速排序和冒泡排序这两种排序方法进行比较，测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的...
冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法，它们的时间性能是开发者和研究人员所关心的热点话题。在本文中，我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...
快速排序是一种高效的排序算法，由英国计算机科学家托尼·霍尔于1960年提出。它采用分治策略来把一个序列分为较小的两个子序列，然后递归地对子序列进行排序，最终合并得到有序序列。快速排序在平均情况下的时间...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治法的策略，通过选取一个基准值并重新排列数组，将问题分解为较小的部分，然后递归地对这些部分进行排序，最终达到整个序列...
在本文中，我们将深入探讨基于FPGA的并行快速排序算法，特别关注“位宽可设”的特性。这种算法能够高效地处理大量数据，并且在硬件实现上具有很高的灵活性。我们将从以下几个方面来阐述这个主题： 一、快速排序算法...
快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它基于分治策略，通常比其他O(n^2)时间复杂度的排序算法更快，平均时间复杂度为O(n log n)。在本项目中，“快速排序演示程序/vc++/mfc...
（1） 完成5种常用内部排序算法的演示，5种排序算法为：快速排序，直接插入排序，选择排序，堆排序，希尔排序； （2） 待排序元素为整数，排序序列存储在数据文件中，要求排序元素不少于30个； （3） 演示程序开始，...
根据给定文件的信息，我们可以总结出以下关于“数据结构 快速排序 输出每一趟结果”的知识点： ### 一、快速排序的基本概念 快速排序是一种高效的排序算法，采用分治法策略来把一个序列分为较小和较大的两个子序列...