交换类排序的另一个方法,即快速排序。
快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进;实现了一次交换可消除多个逆序。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
步骤:
1、从数列中挑出一个元素,称为 "基准"(pivot);
2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
算法实现代码如下:
package exp_sort;
public class QuickSort {
public static void Qsort(int array[], int left, int right) {
int pos;
if (left < right) {
pos = quickSort(array, left, right);
//递归排序
Qsort(array, left, pos - 1);
Qsort(array, pos + 1, right);
}
}
/**
* 一趟快速排序
*
* @param array
* @param left
* @param right
* @return
*/
public static int quickSort(int array[], int left, int right) {
int low, high;
int temp = array[left]; // 选择基准记录(枢纽元)
low = left;
high = right;
while (low < high) {
// high从右到左找小于temp的记录
while (low < high && array[high] >= temp) {
high--;
}
// 找到小于temp的记录则交换
if (low < high) {
array[low] = array[high];
low++;
}
// low从左到右找到大于temp的记录
while (low < high && array[low] < temp) {
low++;
}
// 找到大于temp的记录,则交换
if (low < high) {
array[high] = array[low];
high--;
}
}
//将游标放在当前位置,此时low=high
array[low] = temp;
return low;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
Qsort(array, 0, 7);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}
枢纽元的选取:
1、基本的快速排序:选取地一个元素作为枢纽元。实际中应尽量避免将第一个元素作为枢纽元(极端情况是:初始状态是已排好序或者反序的)。
2、随机化快排序 : 随机的选取枢纽元。
3、平衡快排 : 三数中值分割法:枢纽元的最好选择是数组中的中值,该中值,即左端、右端和中心位置上的三个元素的中值(推荐)。
算法分析:该算法是在实践中最快的一种排序算法,它的平均运行时间是O(N log N),该算法之所以快,主要是由于非常精炼和高度优化的内部循环。它的最坏情况的性能是O(N^2),但是这种情况可以改变。快速排序是一种分治的递归算法。该算法比归并排序算法排序快。
1、最坏情况的分析
当枢纽元是最小元素时,此时就相当于是对整个数组进行递归排序,时间复杂度为:O(N^2)
2、最好情况的分析
枢纽元正好位于中间,此时是对两个子数组进行递归排序,时间复杂度是:O(N log N),这和归并排序的分析完全相同。
3、平均情况的分析
时间复杂度是:O( N log N)
分享到:
相关推荐
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
C语言数据结构 快速排序实例详解 一、快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序。 二、代码实现 #...
数据结构中个各种排序法,快速,直接插入,冒泡...
主要知识点 插入排序 直接插入排序 O(n2) 希尔排序 O(n(lbn)2) 选择排序 直接选择排序O(n2) 堆排序O(nlbn) 交换排序 冒泡排序O(n2) 快速排序O(nlbn) 二路归并排序O(nlbn) 基数排序O(mn)
数据结构中的快速排序实现,用递归实现的C语言快速排序程序。
主要介绍了java数据结构与算法之快速排序,结合实例形式详细分析了快速排序的原理、实现步骤、相关操作技巧与注意事项,需要的朋友可以参考下
8.3.2 快速排序 241 8.4 选择类排序 243 8.4.1 简单选择排序 243 8.4.2 堆排序 244 8.5 二路归并排序 247 8.6 基数排序 248 8.7 外部排序 252 8.7.1 概念与流程 252 8.7.2 置换-选择排序 253 8.7.3 佳归并树 254 ...
本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下: 一、概述 快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element,有时又称为...
然后分别对左、右两个子链表进行递归快速排序,以提高性能。但是,由于单链表不能像数组那样随机存储,和数组的快排序相比较,还是有一些需要注意的细节:1、支点的选取,由于不能随机访问第K个元素,因此每
主要介绍了JS中的算法与数据结构之常见排序(Sort)算法,结合实例形式详细分析了js常见排序算法中的冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等算法相关实现技巧与操作注意事项,需要的朋友可以...
wcf系列5天速成——第一天 binding的使用(1) wpf系列(8)8天入门wpf—— 第八天 最后的补充 8天入门wpf—— 第七天 画刷 8天入门wpf—— 第六天 细说控件 8天入门wpf—— 第五天 数据绑定 8天入门wpf—— 第四天 模板...
相信学过数据结构与算法的朋友对于快速排序应该并不陌生,本文就以实例讲述了C++快速排序的分析与优化,对于C++算法的设计有很好的借鉴价值。具体分析如下: 一、快速排序的介绍 快速排序是一种排序算法,对包含n个...
数据结构十大排序详解,插入,希尔,冒泡,快速,选择,堆,归并,桶,基数,二分十个排序的应用
计算机考研数据结构,含各种疑难点讲解,常见考点。 (当然应付数据机构的期末考试更是绰绰有余了。 严蔚敏老师讲的数据结构的课本,很经典的课程。) 帮助你快速的复习,更快的解决题目。总结均是刷了多年的题写...
* 数据结构中的所有排序算法(冒泡排序,堆排序,直接插入排序,二路归并排序,快速排序,基数排序,直接选择排序,希尔排序)的例子; * 丰富的数组,位,指针,枚举,结构体,联合体等操作的例子; * 一个...
TCP/IP详解 卷1:协议 译者序 前言 第1章 概述 1 1.1 引言 1 1.2 分层 1 1.3 TCP/IP的分层 4 1.4 互联网的地址 5 1.5 域名系统 6 1.6 封装 6 1.7 分用 8 1.8 客户-服务器模型 8 1.9 端口号 9 1.10 标准化过程 10 ...
* 数据结构中的所有排序算法(冒泡排序,堆排序,直接插入排序,二路归并排序,快速排序,基数排序,直接选择排序,希尔排序)的例子; * 丰富的数组,位,指针,枚举,结构体,联合体等操作的例子; * 一个...
非扫描版TCP/IP详解卷一,你值得拥有: 《TCP/IP详解,卷1:协议》是一本完整而详细的TCP/IP协议指南。描述了属于每一层的各个协议以及它们如何在不同操作系统中运行。作者用Lawrence Berkeley实验室的tcpdump程序...