`
chinagdvea
  • 浏览: 130511 次
  • 性别: Icon_minigender_1
  • 来自: 韶关
社区版块
存档分类
最新评论

快速排序的实现

J# 
阅读更多
先写代码,一会再总结

public class TestQuickSort {

  public static void main(String[] args) {
    int[] array = {6, 4, 5, 2, 3, 1};
    for (int x : array) {
      System.out.print(x + " ");
    }

    System.out.println();
    quickSort(array, 0, array.length - 1);
  
    for (int x : array) {
      System.out.print(x + " ");
    }
  }
    
  //  对分割元素左右段数组进行递归快排,直到左右数组只剩下1个元素为止,left代表数组的起始坐标,right代表数组的终点坐标
  public static void quickSort(Comparable[] array, int left, int right) {
    //  当left==right时,说明左边或右边的数组只剩下1个元素,跳出快排
    if (left < right) {
      int i = findPartition(array, left, right);
      quickSort(array, left, i - 1);
      quickSort(array, i + 1, right);
    }
  }

  //  寻找并返回分割元素坐标
  public static int findPartition(Comparable[] array, int left, int right) {
    int i = left;
    int j = right;

    //  用数组第一个元素做为分割元素
    Comparable partitionElement = array[left];
    Comparable temp;

    while (i < j) {
   
      //  从右向左搜索第一个小于分割元素的元素,找到后交换两者的位置
      //  容易知道j左移的时候 array[i]就是分割元素,同理 i 右移的时候,array[j]就是分割元素
      while (i < j && array[j].compareTo(partitionElement >= 0) {
        j--;
      }

      if (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }

      //  从左向右搜索第一个大于分割元素的元素,找到后交换两者的位置
      while (i < j && array[i].comparaTo(partitionElement <= 0) {
        i++;
      }
 
      if (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
  }
}
        
    

总结出的几个问题:
1.快排有两种实现方法:
  (1)第一种如我的代码所示,从右向左找(从右想做找)的跳出条件为(i < j),并且在找到元素后立即与分割元素交换位置.看这一步
  
//  从右向左搜索第一个小于分割元素的元素,找到后交换两者的位置
      while (i < j && array[j].compareTo(partitionElement >= 0) {
        j--;
      }

      if (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }


  (2)第二种是从右向左找(从右想做找)的跳出条件为(i < right) right为数组边界,并且找到元素后不和分割元素交换值,而是交换左右两个找到的值.具体实现略过

2.我这种方法只能先从右往左找第一个小于分割元素的元素
  不能先从左往右找第一个大于分割元素的元素
分享到:
评论

相关推荐

    C++归并排序与快速排序实现.zip

    本资料包“C++归并排序与快速排序实现.zip”主要关注两种经典的排序算法:归并排序(Merge Sort)和快速排序(Quick Sort)。下面我们将详细探讨这两种排序算法以及如何用C++实现它们。 **归并排序(Merge Sort)**...

    快速排序实现原理,及Java实现

    ### 快速排序实现原理及Java实现 #### 一、快速排序算法原理 快速排序是一种高效的排序算法,基于分治法的思想。它的工作原理可以概括为以下几个步骤: 1. **选择基准值**:从待排序的序列中选择一个元素作为基准...

    快速排序算法的简单实现

    快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...

    快速排序实现,实现时间性能分析(IDE:xcode)

    快速排序实现,实现时间性能分析(IDE:xcode)

    Python 算法 13快速排序实现.mp4

    Python 算法 13快速排序实现.mp4

    sort_快速排序的mips实现_

    6. **边界处理**:在实际的MIPS快速排序实现中,还需要考虑数组为空或只包含一个元素的情况,这些情况不需要排序,可以直接返回。 7. **优化**:为了提高效率,可以考虑使用尾递归优化,或者在划分过程中减少不必要...

    快速排序算法c++实现

    以下是一个简单的C++快速排序实现的步骤: 1. **选择基准**:可以从数组的任意位置选取一个元素作为基准,常见的做法是从第一个元素或者最后一个元素开始。 2. **分区**:从数组的第二个元素开始,遍历数组,如果...

    C语言实现快速排序

    C语言数据结构实现快速排序代码,已经过调试可以直接使用。

    快速排序 实现

    ### 快速排序的核心概念与实现 #### 一、快速排序简介 快速排序是一种非常高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)于1960年提出。它采用分治法策略来把一个序列分为较小和较大的两个子序列,...

    改进的快速排序

    在给出的C++代码中,可以看到改进的快速排序实现如下: - `improved_qsort`函数实现了改进后的快速排序算法。通过设置双指针`i`和`j`,并利用基准元素`pivot`来进行分割操作。 - `quick_sort`函数实现了原始的快速...

    快速排序的C语言实现

    用c++写的一个快速排序程序的实现,程序简洁,可以直接用在C语言上

    快速排序实现

    c++实现快速排序

    多线程实现冒泡,快速排序

    快速排序实现 快速排序是一种非常高效的排序算法,它的基本思想是选择一个基准值,通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有记录都比另一部分的所有记录都要小,然后分别对这两部分记录继续...

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

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

    c++实现快速排序源码.zip

    4. **myQuickSort.h**:这个名字可能表示这是一个自定义版本的快速排序实现,可能包含了一些特定的优化或者改进。例如,可能会包含针对已排序或接近排序情况的优化,或者处理小数组的特殊策略。 5. **print.h**:这...

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

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

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

    在C#中实现快速排序,我们通常会用到递归函数。首先,我们需要一个方法来选取枢轴,这可以是数组的第一个元素、最后一个元素,或者数组中间的元素,也可以是三数取中法,即取首、尾、中间三个元素的中位数作为枢轴,...

    数据结构排序里的快速排序

    在提供的代码片段中,可以看到一个简单的快速排序实现。具体步骤如下: 1. **定义函数**:`void QSort(ElemType R[], int n)`,其中`ElemType`表示数组元素的数据类型,`R`是待排序的数组,`n`是数组的长度。 2. **...

    算法领域,快速排序(Quicksort),用于排列数据

    Erlang 是一种面向并发的函数式编程语言,其快速排序实现也非常简洁。 ```erlang q_sort([]) -&gt; []; q_sort([H|R]) -&gt; q_sort([X||X,X]) ++ [H] ++ q_sort([X||X,X&gt;=H]). ``` #### 五、快速排序的应用场景 由于...

    数据结构线性表快速排序

    快速排序实现 - **快速排序函数** `void quick(Sqlist& L, int m, int n)`: - 功能:对线性表`L`在索引`m`至`n`之间的元素进行快速排序。 - 实现:首先检查边界条件,如果起始索引大于等于终止索引则返回;接着...

Global site tag (gtag.js) - Google Analytics