`
endual
  • 浏览: 3560998 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

快速排序算法(自己写)

 
阅读更多
  快速排序算法的伪代码。
package endual;

public class QuickSortClass {

/**
	public void recQuickSort(int left, int right) {
		
		if(right-left <= 0) {
			
			return ;
			
		}else {
		
			int partition = partitionIn(left,right) ; //返回的是关键词的key经过划分以后的位子
			recQuickSort(left,partition-1); //左边进行划分算法
			recQuickSort(partition+1,right) ; //右边进行划分算法
			
		}

	}
	
	1.把数组或者子数组划分为左边和右边的一组
	2.调用自身对左边的一组数组进行排序(划分排序)
	3.再次调用自身对右边的一组进行排序{划分排序)
	
	这里不需要调用数据项也就是我们说的那个key值。
	选择key值,或者叫做枢纽划分排序的key值
	
	选择枢纽(我喜欢叫做key值)
	partitionInt()方法应该使用什么样的枢纽
	1.应该选择具体的一个数据项的值来作为枢纽,称为数据数列的枢纽可以用单词pivot表示
	2.可以选择任意数据项作为枢纽。为了简便,我们假设总是选择待划分的子数组最右边的数据项作为枢纽的
	3.划分完成以后,如果枢纽被插入到左边和右边数据之间的划分处,那么枢纽就落在排序之后的最终位子了
	听起来虽然似乎不太可能。但是,正因为使用枢纽的关键词的值来划分数组,所以划分之后的左边子数组所包含的
	是所有小于枢纽的数据,右边是大于的。枢纽开始时在右边,但是如果以某种方式把它放在两个字数组之间,枢纽
	就会在正确的位子上了。也就是说,在它最终的位子上了。
	
		public void recQuickSort(int left, int right) {
		
		if(right-left <= 0) {
			
			return ;
			
		}else {
		    long provit = theArray[right] ;
			int partition = partitionIn(left,right,pivot) ; //返回的是关键词的key经过划分以后的位子
			recQuickSort(left,partition-1); //左边进行划分算法
			recQuickSort(partition+1,right) ; //右边进行划分算法
			
		}

	}
	
	当选择右边数组的最右边的数据项作为枢纽的方案的时候,需要修改partitionIntde 方法。从划分过程中,把最右端
	的数据项排除在外面。这个数据项在划分过程中完成之后应该在什么位子已经很清楚了的。
	
	**/
	
	
	
}

 

   划分算法---快速排序算法的核心

 

   快速排序

从划分开始

划分
划分是快速排序的根本机制,但是划分本身也是一个有用的操作,所以我们重点要介绍下划分。
   划分数据就是把数据分为两组,使所有关键词大于特定的数据项在一组,使所有关键词小于特定值的数据项在另一组。
   
 很容易想象划分数据的情况:
     比如现在有工人的信息。将工人的信息分为两组:家住距离工厂15公里以及15公里内的和家住距离工厂15公里以外的。
     比如学习管理者想把学生分成年级平均成绩分为及格和不及格,以此来判定哪些学生应该在主任掌握的名单上。
     
   那么我们来做一个例子吧:
   我们在成绩表上会这样的,按照学号排序着,但是现在要把成绩分为60分以上和60分一下吧,比如用60这个作为关键词(划分点,
   枢纽)。比关键词大的在右边,比关键字小的在左边(来来来,我们想想希尔排序,这个可比希尔排序的基本排序严格多了哦)。
  但是经过划分以后,左边的数据并没排序好的,右边的数据也没排序好的,举个划分好的例子吧:
  
  45,43,54,21,43,【60】,78,98,78,65,67
  
 划分之后的数据还不能称呼为有序的,这只是简单的把数据划分为两组。但是数据还是比没划分之前要更接近有序了。
 划分是不稳定的,也就是说,每一组中的数据项并不是按照它原来的顺序排序的。事实上,划分往往会颠倒组中一些数据的顺序。
 划分有单独的程序。
 划分算法由两个指针开始工作,两个指针分别指向数组的两头。(这里使用指针这个词是指示数组数据项的,而不是C++中所说的指针。
 在左边的指针,leftPtr,向右移动,而在右边的指针,rightPtr,向左边移动。
 
 
 划分算法的效率
 划分算法运算的时间复杂度是N
 

     划分算法的代码

 

   package endual;

//划分数据的程序
public class Partition {

	private long[] theArray ;
	private int nElems ;
	
	public Partition(long[] theArray, int nElems) {
		super();
		this.theArray = theArray;
		this.nElems = nElems;
	}
	
	public void dispay() {
		System.out.println("显示划分好以后的数据") ;
		for (long a : this.theArray) {
			
			System.out.println(a);
			
		}
	}// end dispay
	
	public int partitionIt(int left, int right, long pivot) {
		
		int leftPtr = left - 1 ;
		int rightPtr = right - 1 ;
		
		while (true) {
			
			while (leftPtr < right && theArray[++leftPtr] < pivot) {
				
			}
			
			while (rightPtr < left && theArray[--rightPtr] > pivot) {
				
			}
			
			if (leftPtr >= rightPtr) {
				break ;
			}else {
               
				swap(leftPtr, rightPtr) ;
				
			}	
		}	//end while
		
		return leftPtr ; //返回的是枢纽或者key关键词在数组中的位子
	}

	private void swap(int leftPtr, int rightPtr) {

       long temp ;
       temp = this.theArray[leftPtr] ;
       this.theArray[leftPtr] = this.theArray[rightPtr] ;
       this.theArray[rightPtr] = temp ;
		
	}

}

 

 

  快速排序算法理论

 快速排序的算法

毫无疑问快速排序是最流行的算法。因为有充足的理由,在大多数情况下,快速排序都是最快得。执行时间是NlogN.
这只是在内排序中或者说事在随机存储器而言的,对于在文件中的排序,可能其他的排序算法更加好。快速排序是1962年发现的。



为了理解快速排序算法,我们要非常理解划分算法。快速排序算法本质上通过把一个数组划分为两个数组,然后递归地调用自身为
每个子数组进行快速的排序来实现的。
但是,对于这个基本的设计还需要进行一些加工。算法还必须需要选择key值以及对于小的划分区域进行排序。看过这个主要算法的简化
代码以后。还需要对其进行求精。

   在理解快速排序的道理之前想知道快速排序干的是什么,我们先给出了快速排序的代码吧
   
   
 

代码






















 
分享到:
评论

相关推荐

    快速排序归并排序简单排序算法比较

    自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。

    实现(串行,openmp、mpi、openmp+mpi)快速排序算法,并作出时间对比图

    主要采用快速排序实现(串行,openmp、mpi、openmp+mpi)排序算法,所需环境为VS2019+openmp+mpi,cmd命令 (1)完成了CPU串行程序和三种并行程序在各种规模的运行,并作出时间对比图 (2)完成了串行,openmp使用...

    快速排序算法

    面试必考的排序算法!该算法是本人自己写的,符合面试的规则,而且是数据结构的重要算法!

    各种自己写的排序算法,做个备份

    本文将详细探讨标题为"各种自己写的排序算法,做个备份"的压缩包中可能包含的知识点,并对描述中提及的"略微做个备份"进行解析。 首先,我们关注到两个文件名:"拆分排序.cpp"和"SieveSort.cpp",它们分别代表两种...

    算法分析之排序算法 排序算法

    当然,为了学习和理解,我们也可以自己编写这些基本排序算法的C++代码。 例如,快速排序的C++实现可能如下: ```cpp void quickSort(int arr[], int left, int right) { if (left ) { int pivotIndex = ...

    自己写的排序算法,还有点小问题

    "自己写的排序算法,还有点小问题"这个标题表明作者已经尝试实现了一个排序算法,但可能遇到了一些挑战或bug。描述中提到的“只有个框架,递归计算”暗示了作者可能使用了递归的方式来实现排序,这是一种常见的编程...

    自己用C#写的六种排序算法实例

    本项目中,你提供了六种不同的排序算法的C#实现:冒泡排序、选择排序、快速排序、哈希排序、堆排序以及插入排序。下面将详细解释这些排序算法的原理和特点。 1. **冒泡排序**: 冒泡排序是最简单的排序算法之一,...

    【算法导论】排序算法源码

    自学算法导论中前几章,并自己写的排序算法源码包括gtest的测试用例。 详细介绍看我博客 http://blog.csdn.net/ceofit 一、选择法排序、冒泡排序、插入法排序 http://blog.csdn.net/ceofit/article/details/7397020 ...

    用python实现常见6种排序算法

    冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来...

    C/C++实现双路快速排序算法原理

    本文实例为大家分享了C/C++实现双路快速排序算法的具体代码,供大家参考,具体内容如下 看了刘宇波的视频,讲双路快速排序的,原理讲的很直观,程序讲解也一看就懂。这里写一下自己的理解过程,也加深一下自己的理解...

    设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

    内部排序算法是指在内存中进行排序的算法,常见的内部排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序等。 在JavaScript中,我们可以使用onsubmit事件和onblur事件来实现表单校验。在下面的例子中,...

    插入排序 C++实现 自己备忘

    - **作为其他排序算法的基础**:插入排序是其他更复杂排序算法(如希尔排序、快速排序的尾递归部分)的基础。 ### 总结 插入排序虽然在最坏情况下时间复杂度较高,但其简单性、稳定性和在特定条件下的高效性使其在...

    自己写的排序2.0版本

    总之,"自己写的排序2.0版本"是一个使用递归方法实现的排序算法,可能是基于快速排序的变体或者是受到埃拉托斯特尼筛法启发的原创算法。C++源代码和编译后的可执行文件为我们提供了实现细节和验证算法功能的可能性。...

    排序算法的代码

    自己写的排序代码,用c语言实现,包含:直接插入排序,希尔排序,快速排序, 简单选择排序,堆排序,归并排序。

    随手笔记--数据结构与算法(Java)排序

    内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...

    多进程多线程快速排序C++源码

    4. **快速排序算法**:理解快速排序的基本原理,如何选择基准元素,如何分割和合并子数组。 5. **并发控制**:考虑到多进程多线程环境,需要理解锁、信号量等并发控制机制,以防止数据竞争问题。 通过分析这个项目...

    算法导论 手册 作者自己写的

    快速排序是一种非常高效的排序算法,其基本思想是通过分治法将待排序数组分为较小和较大的两个子数组,然后递归地对这两个子数组进行排序。本章将深入探讨快速排序的细节。 #### 7. Sorting in Linear Time(线性...

    我是如何击败Java自带排序算法的

     首先,我编写了一个经典的快速排序算法。这个算法通过计算样本的平均值来估计整个数组的中心点,然后用作初始枢轴。  我借鉴了一些Java的思路来适当改进我的快速排序,修改后的算法在对小数组进行排序的时候...

    《夜深人静写算法(金牌版)》.rar

    排序算法包括快速排序、归并排序、堆排序等,这些是每个程序员必备的基础知识。搜索算法则可能包括二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),它们在处理大量数据时非常有效。 其次,书中可能深入到图论和树...

Global site tag (gtag.js) - Google Analytics