美文网首页
算法导论之快速排序实现

算法导论之快速排序实现

作者: ilkd | 来源:发表于2020-05-04 13:52 被阅读0次

实现该算法的背景

快速排序实现的方式有各种各样的,但是却很少看到算法导论中的实现。就是书上那个,我很是纳闷。所以在这里贴一份这样的实现,以便需要的人的用。

算法导论中的伪代码

这里先贴出伪代码,这个我觉得算是比较好理解快排的了,更重要的非常简洁。对于记性不好的我,非常友好。

QUICKSORT(A, p, r)
 if  p < r
       q = PARTITION(A,p,r)
      QUICKSORT(A,p,q-1)
       QUICKSORT(A,q+1,r)
PARTITION(A, p, r)
  x = A[r]
  i = p-1
  for j = p to r-1
          if A[j] <= x   //<=与书上有区别,符号的区别,不会打那个。。。。
               i = i + 1
               exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

理解的话,我用大白话叙述一下。目的将数组划分为 4 个部分,1:比 x 小的,2:为比 x 大,3:等于 x 的,4: 可能为空。粘一些书上的话。设任意p -> r,数组下标为k。

  1. 当 p ≤ k ≤ i , 则 A[k] ≤ x
  2. 当 i+1 ≤ k ≤ j-1,则 A[k] > x
  3. 当 k = r ,则 A[k] = x
    证明:第一轮迭代之前是成立的,每一轮迭代都成立。
    第一轮迭代之前:
    i = p-1 ,j = p,所以1,2 这两成立,因为没有值在 [p ,i] 和 [i+1,j-1]之间。k = r,A[k] = A[r] = x。
    每一轮迭代:
    存在两种情况:
    A[j] > x ,j=j+1,i不变,只有 j 变化了,所以只要条件2后半部分 k ≤ j-1,k=j,A[k] > x成立,条件1,2,3成立。
    A[j] ≤ x,i=i+1,交换 A[i=i+1] 和 A[j] , k=j,在[p,i],A[i=i+1]=A[j] ≤ x,条件1满足,我们知道在迭代前,A[i+1] > x ,因为 k ≥ i+1,A[k] > x。所以交换的结果为 A[j] > x,永远确保A[j-1] > x。
    如果不能理解的话,去看书本,或者其他博主的回答吧。就不粘图了。

基于java语言的代码实现

回到我们实现代码上来。用static 因为在main 中运行。

public class QuickSort {


    public static int partition(int[] Array, int start, int end){
        int x = Array[end];
        int i = start-1;
        for (int j = start; j <= end-1; j++) {
            if(Array[j] <= x){
                i = i + 1;
                exchange(Array,i,j);
            }
        }
        exchange(Array,i+1,end);
        return i+1;
    }

    public static void exchange(int[] Array, int i, int j){
        int temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
    }

    public static void quickSort(int [] Array, int start, int end){
        if(start < end){
            int mid = partition(Array,start,end);
            quickSort(Array,start, mid -1);
            quickSort(Array, mid+1, end);
        }
    }

    public static void main(String[] args) {
        int[] Array  = new int[]{2,8,7,1,3,5,6,4};
        arrayToString(Array);
        quickSort(Array,0,Array.length-1);
        arrayToString(Array);
        Array  = new int[]{10,1,6,9,4,9,18};
        arrayToString(Array);
        quickSort(Array,0,Array.length-1);
        arrayToString(Array);

    }

    public static void arrayToString(int [] Array){
        System.out.print("[");
        for (int i = 0; i < Array.length; i++) {
            if(i != Array.length -1){
                System.out.print(Array[i]+",");
            }else {
                System.out.print(Array[i]);
            }
        }
        System.out.print("]\n");
    }

}

这是运行结果:

[2,8,7,1,3,5,6,4]
[1,2,3,4,5,6,7,8]
[10,1,6,9,4,9,18]
[1,4,6,9,9,10,18]

总结

用这个去理解的话,只要设置好初始值以及结束值和一个比较条件即可。x = Array[end] , i = start -1 ,
j=start 且 j <= end-1, 用Array[j] 和 x 比较,返回 =x 的位置即 i+1。

相关文章

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 算法导论之快速排序实现

    实现该算法的背景 快速排序实现的方式有各种各样的,但是却很少看到算法导论中的实现。就是书上那个,我很是纳闷。所以在...

  • C++快速排序(算法),小白必备!拿走不谢!

    <算法导论>上面的算法逻辑 QUICKSORT(A, p, r)//快速排序算法 if (p < r ) { q ...

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • JS实现排序算法

    原文:常见排序算法之JavaScript实现 - 知乎 目录 冒泡排序 选择排序 插入排序 合并排序 快速排序 1...

  • 计数排序、基数排序和桶排序

    阅读经典——《算法导论》07 到目前为止,我们已经介绍了插入排序、归并排序、堆排序、快速排序这四种排序算法,他们的...

  • 手撕代码 之 快速排序

    1.实现快速排序算法 问题描述给定一个无序数组int[ ] a,使用快速排序算法进行排序。 解题思路对于快速排序,...

  • 算法导论:快速排序

    快速排序基本思想 输入代排数组——>选取基准元——>执行划分操作——>递归对两个数组进行快速排序1、比如这里输入序...

  • 三大排序算法

    归并排序[稳定的排序算法] 递归实现 非递归实现 快速排序[不稳定的排序算法] 堆排序[不稳定的排序算法]

  • 好文章索引

    算法 《算法导论》快速指南:我是如何10天入门算法导论的。 - 渗透之美 - 知乎专栏 推荐内容索引 - 老赵点滴...

网友评论

      本文标题:算法导论之快速排序实现

      本文链接:https://www.haomeiwen.com/subject/icpeghtx.html