一.
排序方法
- 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
- 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。原排序数组data[0...n]。
- 分解:在data[low..high]中任选一个记录作为基准(pivot),以此基准将当前无序区划分为左、右两个较小的子区间data[low..pivotpos-1]和data[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录pivot,右边的子区间中所有记录的关键字均大于等于pivot,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
- 递归:data[low..high]被划分为两个子区间data[low..pivotpos-1)和data[pivotpos+1..high],而每个子区间采用相同的方法再次划分为两个子区间...
- 组合:因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。
二.
动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/kuaisupaixu.htm
三.Java代码
/**
* 快速排序
* @param data
* @param low data最小下标
* @param high data最大下标
* @return
*/
public static int[] quickSort(int[] data, int low, int high) {
// 对data[low..high]快速排序
int pivotpos; // 划分后的基准记录的位置
if (low < high) {// 仅当区间长度大于1时才须排序
pivotpos = partition(data, low, high); // 对data[low..high]做划分
quickSort(data, low, pivotpos - 1); // 对左区间递归排序
quickSort(data, pivotpos + 1, high);// 对右区间递归排序
}
return data;
}
/**
* 划分算法,划分后
* 左边子区间中所有记录的关键字均小于等于基准记录pivot
* 右边的子区间中所有记录的关键字均大于等于pivot
* 基准记录pivot则位于正确的位置上
* @param data
* @param i
* @param j
* @return
*/
public static int partition(int[] data, int i, int j) {
// 并返回基准记录的位置
int pivot = data[i]; // 用区间的第1个记录作为基准 ,
while (i < j) { // 从区间两端交替向中间扫描,直至i=j为止
while (i < j && data[j] >= pivot) {
// pivot相当于在位置i上
j--; // 从右向左扫描,查找第1个关键字小于pivot的记录data[j]
}
if (i < j) // 表示找到的data[j]的关键字<pivot
data[i++] = data[j]; // 相当于交换data[i]和data[j],交换后i指针加1
while (i < j && data[i] <= pivot) {
// pivot相当于在位置j上
i++; // 从左向右扫描,查找第1个关键字大于pivot的记录data[i]
}
if (i < j) // 表示找到了R[i],使data[i]>pivot
data[j--] = data[i]; // 相当于交换data[i]和data[j],交换后j指针减1
} // endwhile
data[i] = pivot; // 基准记录已被最后定位
return i;
}
四.
时间复杂度和稳定性
- 最好时间复杂度
- 在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:
0(nlogn)
- 最坏时间复杂度
- 最坏情况是数组有序时,每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。
因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值:
Cmax
= n(n-1)/2=O(n2
)
- 平均时间复杂度
- 0(nlogn)
- 算法的空间复杂度:快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀,则其递归树的高度为O(lgn),故递归后需栈空间为O(lgn)。最坏情况下,递归树的高度为O(n),所需的栈空间为O(n)。
- 快速排序是非稳定的,例如[2,2
,1]。
分享到:
相关推荐
c语言版本的数据结构的快速排序算法,适用于新手学习
北京工业大学,电控学院,《数据结构与算法》。本资源是北工大电控学院大一下学期课程《数据结构与算法》的课程实验。 本资源为数据结构与算法第三章(排序)的实验程序代码。包含以下的三个程序:1.快速排序;2....
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。