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

对于快速排序的理解

阅读更多

 

这两天一直在看排序的算法,当看到快速排序的时候卡了,真是那个郁闷啊。之前几个排序(选择、冒泡......)很快就可以过了。

可是看到快速排序的时候就怎么的也不能理解。

然后就到网上去搜了下,搜到的也就这么几种解释,多数都是大同小异。

网上搜到的,解析得也有点官方,看了会觉得还是看不懂。

怎么的......只能自己慢慢理解吧!

最后......也算是有点小成就吧,自己能理解,不知道对还是不对。

 

费话就不多说了,以下上代码,和我自己对快速排序的理解!请指教!


 

public void quickSort(int[] array, int left, int right) { //array,要排序的数组;

                                                                       //left,从数组left位置开始排序;

                                                                       //right,排序到数组的right位置。 排序整个数组:left=0;right=array.length。

if (left < right) { //如果是一个正确的开始和结束的排序位置(开始位置肯定小于结束位置)

int mid = partition(array, left, right);  //通过partition方法得到排序的分隔点(关于partition方法原理可以往下看注解)

quickSort(array, left, mid - 1);  //递归分隔点以前部分的排序(以left为开始点,分隔点前一个元素为结束点)

quickSort(array, mid + 1, right); //递归分隔点以后部分的排序(以分隔点的后一个元素为开始点,以right为结束点)

}

}

 

//在不管partition方法的实现的情况下,以上方法相信大家都应该可以容易的理解吧!

//既:通过partition方法将数组array分成以分隔点为中心,左边是比其小的元素集,右边是比其大的元素集。

//       然后返回数组的分隔点,通过递归对分隔点左右两边再进行排序。


//下面来看partition方法的实现——->

 

public int partition(int[] array, int left, int right) { //排序数组array的left到right位置,并返回分隔点(分隔点左边是小元素,右边是大元素)

                                                                           //array:要分隔的数组

                                                                           //left:要分隔部分的开始位置

                                                                           //right:要分隔部分的结束位置

int pivot = array[left]; //设定第一个元素为基准元素(一般都以第一个元素为基准,本例也一样,不做特殊化)

int head = left; //这两个值(head/tail)的设定我觉得是挺重要的。

                                      //head:指向要分隔部分的(头)位置

                //从小到大排列 //head++,向右(tail)移动;tail——,向左(head)移动。

int tail = right + 1;//tail:指向要分隔部分的右(尾)位置 ,为什么要后移一位,请看后注。

 

//以下连起来为一句话:

while (head < tail) { //在head和tail碰到(==) 之前,

if (array[head] <= pivot) {   //如果在head位置找到了比基准元素大的元素,

head++;  //否则找下一个元素

} else if (array[tail - 1] > pivot) { //并且在(tail-1)位置找到了比基准元素小或等于的元素。

tail——; //否则找上一个元素

} else {

swap(array, head, tail - 1);//那么交换head和(tail-1)位置的元素。

                                                                    //来实现把大的元素放到基准元素后面,把小的元素放基准元素前面

head++; //并让head指向下一个元素

tail——;//让tail指向上一个元素                    注:“++“、”——”来分别指向下一个元素是因为这两个位置的元素已经比较过了,

                                                                                            //不需要再过它们比较,来提高效率

}

}

  //到这里已经结束上面的交换,既:head>=tail。

//下面将把基准元素放到"中间位置",并非真正的中间,只是它的左边是比基准元素小的元素,它的右边是比基准元素大的元素

//记:是本次比较的中间位置(left到right)

array[left] = array[head - 1];  //把第一个元素(left)赋值为head指针的上一个元素.

                                                         //为什么是上一个元素,而不是head指向位置的元素?

                                                         //因为head指向位置的元素,你不知道它的大小,

                                                         //把head指向的元素放到小元素集(基准元素的左边),将无法保证小元素集(可能head指向的元素比基准元素大)

                                                         //这样就破坏了排序(排列的目的:将基准的左边放比基准小的元素,将基准的右边放比基准大的元素)

                                                        //所以,把head的上一个元素和基准交换就能保证排列的目的。因为head的上一个元素一定是小元素

array[head - 1] = pivot;//把head指针的上一个元素赋值为基准元素 (完成交换)

return head - 1; //返回基准元素位置(通过上面的交换,这里基准元素的位置已经变成了head-1),作为排序的分隔点

}

 

private void swap(int[] array, int a, int b) { //交换数组array中的a和b位置的元素

                                                                    //该方法用异或"^"来完成交换,当然也可以简单的第三个临时元素来完成

array[a] = array[a] ^ array[b];

array[b] = array[a] ^ array[b];

array[a] = array[a] ^ array[b];

}


 

//注:为什么tail = right+1 ; head ≠left-1 ?

//left指向排列首 ,right指向排列尾。

//排列开始的指针head当然应该指向排列首(left)啊,结束tail当然指向排列尾(right)啦。可tail为什么要后移一位,这样不就会造成越界吗?

//我的理解是这样的:

//head++,向tail移动。为了能让head指针在最后能够指向最尾right ,如果在这里不加一,那么在下面while判断首尾相遇(head== tail)的时候,就要写成while(head<=tail)。

//这样感觉应该也可以......为什么不用while(head<=tail)

//因为,如果用“<=”的话,当head == tail的时候还要比较一次,这样不是多余,会降低效率

//所以在这里用后移一位来处理(tail = right+1).让在“while(head < tail)”的条件下,head可以指向最尾(right).

//相应的,在以下的计算中要用“tail-1”来计算,为的是不让数组下标越界。

//为什么head不用上移一位呢?

//因为在while循环中,head判断在前,基准是第一个位置元素array[left],而且找的是比基准元素大的元素,所以tail指针不可能也不需要指向第一个位置元素.顾不用做上移一位处理!



以上是本人对快速排序的一点点理解!

如果大家有什么更好的见解,可以分享一下哦!

当然以上如果哪里本人理解错了,也请及时提出,以便纠正!谢谢!

 

0
3
分享到:
评论
3 楼 Hxuejie 2011-11-22  
归并排序和快速排序是不是大同小异呢?
2 楼 Hxuejie 2011-11-22  
Technoboy 写道
看一下《Java数据结构和算法》

呵呵,嗯!
谢谢指点!
那问一下我对快速排序的理解对吗?其原理是这样的吗?
1 楼 Technoboy 2011-11-11  
看一下《Java数据结构和算法》

相关推荐

    排序算法编程 堆排序 快速排序

    本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...

    C语言实现多种链表快速排序

    在C语言中实现链表快速排序,首先需要理解链表和快速排序的基本概念。链表不同于数组,它不连续存储数据,而是通过指针连接各个节点。每个节点包含数据元素和指向下一个节点的指针。快速排序的核心是“分区操作”和...

    确定性快速排序与随机化快速排序的比较

    快速排序是一种高效的排序算法,在计算机科学和数学中被广泛研究。其基本原理是分治法策略,即将一组数据分为两个子序列并分别进行排序。快速排序期望的时间复杂度为O(nlogn),但在最坏的情况下,它的时间复杂度可...

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

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R....总的来说,这个压缩包提供了一个非递归实现快速排序的完整示例,通过自定义栈的数据结构,实现了快速排序算法,适用于理解和学习快速排序的非递归实现方式。

    快速排序算法和冒泡排序效率对比

    快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。本篇文章将深入探讨这两种排序算法的原理、效率以及它们在C#编程语言中的实现。 首先,让我们...

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

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治策略,通过一趟排序将待排序的...通过理解和实践这三种方法,可以深入理解快速排序的原理和优化技巧,提高编程能力。

    冒泡,快速排序的比较

    而优化的快速排序,如三向切分快速排序,能进一步提高效率,特别是对于含有大量重复元素的序列。 在实验中,我们应记录并分析比较次数和移动次数的变化,这有助于理解算法在不同数据结构上的表现。例如,如果某组...

    快速排序.pdf

    快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它采用了分治法的策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个...同时,正确理解和实现快速排序的关键在于掌握其划分操作和递归思想。

    快速排序算法matlab

    ### 快速排序算法在MATLAB中的应用与理解 #### 一、快速排序算法简介 快速排序是一种非常高效的...对于从事生物医学信号处理等领域的研究人员来说,掌握并灵活运用快速排序算法能够有效提高数据处理的效率和准确性。

    比较快速排序与起泡排序

    快速排序和起泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,尤其在数据处理和算法分析方面。接下来,我们将深入探讨这两种排序方法的原理、效率以及应用场景。 快速排序是一种由C.A.R. Hoare在...

    生成字典排序和快速排序源代码c++

    总结来说,这两个源代码文件为我们提供了学习和理解字典序排列和快速排序的实践机会。通过对这些代码的学习和分析,我们可以加深对排序算法的理解,提高编程技能,并且能够灵活地解决实际问题。在实际编程中,选择...

    c++ 选择排序 插入排序 快速排序

    选择排序、插入排序和快速排序都是经典的排序算法,各有其特点和适用场景。接下来,我们将详细探讨这三个排序算法。 1. **选择排序(Selection Sort)** 选择排序是一种简单直观的排序算法。它的基本思想是在未...

    快速排序演示程序/vc++/mfc

    快速排序是一种高效的排序...这个程序为学习和理解快速排序提供了一个直观的工具,同时也可以作为MFC应用开发的一个实例。通过运行和分析代码,开发者不仅可以深入理解快速排序的工作原理,还能掌握MFC库的使用方法。

    快速排序和直接插入排序的组合

    快速排序和直接插入排序是两种常见的排序算法,它们各自具有不同的特性和应用场景。在实际编程中,有时会根据数据特点和需求将这两种排序方法结合使用,以达到更高效的排序效果。 快速排序是一种由C.A.R. Hoare在...

    普林斯顿快速排序PPT

    - 对于小数组采用插入排序代替快速排序,因为插入排序对于小数组更加高效。 - 使用尾递归优化或者迭代方式代替递归调用,减少栈空间占用。 ### 五、总结 快速排序因其高效的性能以及相对简单的实现,在实际应用...

    快速排序、归并排序、堆排序 并比较排序时间

    而快速排序则适用于大多数情况,特别是对于大型数据集。 总的来说,快速排序、归并排序和堆排序各有优缺点,选择哪种取决于应用场景的具体需求,如数据规模、是否需要稳定性、可用内存等因素。理解和掌握这些排序...

    合并排序与快速排序

    但对于大规模数据,快速排序通常更快,但如果内存有限,合并排序可能是更好的选择,因为它可以使用外部排序。 4. **实现难度**:快速排序的实现相对简单,而合并排序需要更复杂的合并过程。 在实际应用中,根据具体...

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

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

    舍伍德——快速排序源码报告和算法分析

    7. **性能优化**:包括优化基准选取、使用插入排序处理小数组(因为快速排序对于小数组可能不如插入排序高效)、三向切分(处理含大量重复元素的数组)等。 8. **并行化**:舍伍德可能也研究了如何利用多核处理器...

Global site tag (gtag.js) - Google Analytics