`

快速排序(2个版本)

 
阅读更多

快速排序C.R.A.Hoare1962年提出的一种划分交换排序,是对冒泡排序的改进。平均情况下快速排序的时间复杂度为O(nlogn),虽然最坏情况时会达到O(n2),但在大多数情况下,快速排序要比其它O(nlogn)算法要快,被认为是目前最优秀的内部排序算法。快速排序是不稳定的。它采用分治(Divide and Conquer)的策略,把一个串行(list)分为两个子串行(sub-lists)。

步骤为:

  • 从数列中挑出一个元素,称为 "基准"pivot);
  • 分区(partition:将所有小于基准值的元素放在基准前面,所有大于基准值的元素放在基准的后面(相同的数可以到任一边)。分区结束之后,该基准就处于数列的中间位置
  • 分别对小于基准值元素的子数列和大于基准值元素的子数列进行递归排序。

递归的最底部情形,是数列的大小是零或一,在每次的迭代中,它至少会把一个元素摆到它最后的位置去。

 

1.快速排序算法一

这是在多数的教科书上所提及的版本,容易理解,选第一个元素为基准,*表示要交换的数,一趟排序的过程如下:

 

[41] 24 76* 11 45 64 21 69 19 36*  

[41] 24 36 11 45* 64 21 69 19* 76

[41] 24 36 11 19 64* 21* 69 45 76

[41] 24 36 11 19 21 64 69 45 76

21 24 36 11 19 [41] 64 69 45 76

 

代码实现:

 

public class QuickSort {
	public static void sort(int[] number) {
		sort(number, 0, number.length - 1);
	}
	
	public static void sort(int[] number, int left, int right) {
		if(left < right) {
			int s = number[left];
			int i = left;
			int j = right + 1;
			while(true) {
				while(i + 1 < number.length && number[++i] < s);//向右找
				while(j - 1 > -1 && number[--j] > s);           //向左找
				if(i >= j)
					break;
				swap(number, i, j);
			}
			number[left] = number[j];
			number[j] = s;
			sort(number, left, j -1);   //对左边进行递归
			sort(number, j + 1, right); //对右边进行递归
		}
	}
	
	public static void swap(int[] number, int i, int j) {
		int t = number[i];
		number[i] = number[j];
		number[j] = t;
		
	}
	
	public static void main(String[] args) {
		int[] number = {49,38,65,97,76,13,27,49};
		sort(number);
		for(int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
	}
}

 

2.快速排序算法二

基准的选择是快速排序法的效率关键之一,下面介绍的快速排序算法来自算法名著 Introduction to Algorithms,算法基本思想如下:

  • 它以最右边的值s作比较的标准,将整个数列分为三个部份,一个是小于s的部份,一个是大于s的部份,一个是未处理的部份,如下所示 :

快速排序

  • 在排序的过程中,i 与 j 都会不断的往右进行比较与交换,最后数列会变为以下的状态:

 

 

快速排序

  • 然后将s的值置于中间,接下来就以相同的步骤会左右两边的数列进行排序的动作,如下所示:

 快速排序

一个实际例子的演算如下所示:

快速排序

 

代码实现:

public class QuickSort {
	public static void sort(int[] number) {
		sort(number, 0, number.length - 1);
	}
	
	public static void sort(int[] number, int left, int right) {
		if(left <= right) {
			int q = partition(number, left, right);
			sort(number, left, q - 1);
			sort(number, q + 1, right);
		}
	}
	
	public static int partition(int[] number, int left, int right) {
		int s = number[right];
		int i = left - 1;
		for(int j = left; j < right; j++) {
			if(number[j] < s) {
				i++;
				swap(number, i, j);
			}
		}
		swap(number, i + 1, right);
		return i + 1;
	}
	
	public static void swap(int[] number, int i, int j) {
		int t = number[j];
		number[j] = number[i];
		number[i] = t;
	}
	
	public static void main(String[] args) {
		int[] number = {49,38,65,97,76,13,27,49};
		sort(number);
		for(int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
	}
}

 

0
0
分享到:
评论

相关推荐

    简单的快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer)...另外,对于具有大量重复元素的数组,可以使用三向切分的快速排序版本,以进一步优化性能。

    快速排序 --- 非递归实现

    但缺点是在最坏的情况下,如果输入数组已经排序或几乎排序,非递归版本的快速排序可能会比递归版本更慢,因为它必须处理更多的子数组。 总的来说,这个压缩包提供了一个非递归实现快速排序的完整示例,通过自定义栈...

    快速排序算法(c#实现)

    快速排序的平均时间复杂度为O(n log n),在最坏的情况下(输入数组已经完全有序或逆序),时间复杂度为O(n^2)。然而这种情况在实际应用中很少出现,因为快速排序通常能在实际数据集上表现出优秀的性能。同时,由于...

    快速排序迭代版本源代码

    迭代快速排序虽然在实现上相比递归版本稍复杂,但它的优势在于避免了递归带来的额外开销,适用于处理大规模数据,且在实际应用中,性能往往与递归版本相当。在实际编程时,应根据具体场景和需求来选择适合的实现方式...

    改进的快速排序

    快速排序是一种非常高效的排序算法,采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。该算法的基本思想是:选择一个基准元素(pivot),通过一趟排序将待排序的数据分割成独立的两...

    快速排序的三种写法及随机化快速排序

    在实际应用中,随机化快速排序通常优于非随机化的版本,因为它更稳定,对于各种输入都能保持良好的性能。随机化快速排序的具体步骤如下: 1. 选择数组中的一个随机元素作为主元。 2. 将数组分为两部分,一部分包含...

    合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现

    本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...

    算法实验1-快速排序

    在给出的"Lab 1"文件中,可能包含了实现快速排序的代码,包括普通快速排序和随机快速排序的版本,以及统计两种排序算法运行时间的代码。通过分析和运行这些代码,你可以更深入地理解快速排序的工作原理和性能特性。

    快速排序源码+排序原理说明

    下面是一个简化的C++版本快速排序的实现示例: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { int pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1);...

    快速排序标准代码

    在编程实现上,快速排序可以采用不同的编程语言来实现,例如`QuickSort.java`可能是Java版本的实现。在Java中,可以使用递归函数来实现快速排序,定义一个名为`quickSort`的方法,接收数组和两个索引参数,表示当前...

    排序算法C语言版:快速排序

    但在最坏的情况下,如果序列已经部分排序或完全排序,快速排序的时间复杂度会退化到O(n^2)。尽管如此,由于快速排序在实际应用中的优秀性能,它仍然是许多编程语言内置排序函数的首选算法。 快速排序的一个缺点是它...

    使用快速排序法对一维数组进行排序

    为了应对这种情况,可以采用随机化版本的快速排序,通过随机选取基准来减少最坏情况发生的概率。 在实际编程中,快速排序是常用的一种排序算法,尤其在大数据量的场景下,其高效性能使其成为首选。然而,需要注意的...

    C经典算法之快速排序法(二)

    ### C经典算法之快速排序法(二) #### 知识点概述 本篇文章将深入探讨快速排序算法的一个改进版本,并通过具体的代码实现来展现这一优化思路。在快速排序法(一)的基础上,本文重点关注轴的选择对算法性能的影响...

    易语言快速排序

    在实现快速排序时,你需要定义一个函数,如“快速排序(数组, 起始索引, 结束索引)”来处理数组的一部分,并在函数中进行上述的分区和递归调用。 6. **优化策略**:为了提高效率,还可以考虑以下优化策略: - 对于...

    快速排序图形界面演示程序

    "qucikSort2.5"这个文件可能是程序的主程序或版本号,表示这是一个快速排序的2.5版图形界面程序。用户可以通过运行这个程序来体验快速排序的全过程,加深对算法的理解。总的来说,这样的工具对于学习和教学快速排序...

    并行实验快速排序实验报告完整版

    3. 实现并行版本的快速排序算法,以提高排序速度。 实验环境要求使用单台或多台配备Linux操作系统的PC机,并安装MPI(Message Passing Interface)系统,用于进程间通信和协调。 实验内容涵盖了快速排序的基本思想...

    java实现快速排序小结

    为了避免这种情况,通常会采用随机化版本的快速排序,即随机选择基准元素,这样可以平均分布元素,降低最坏情况发生的概率。 了解快速排序的时间复杂度分析对于选择合适的排序算法至关重要。在实际应用中,如果预计...

    冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现

    源码实现的核心是“分区操作”,选取一个基准值,将序列分为两部分,使得一部分元素小于基准,另一部分大于基准,然后对这两部分分别进行快速排序。 这些排序算法各有优缺点,适用场景也不同。例如,冒泡排序和选择...

    快速排序算法通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    3. **内存管理**:虽然快速排序本身并不涉及大量的内存分配和释放,但在大规模数据处理时,递归深度过深可能导致栈溢出,需要考虑适当的优化,如尾递归或使用迭代版本的快速排序。 4. **枢轴选取**:不同的枢轴选取...

Global site tag (gtag.js) - Google Analytics