快速排序法及优化

快速排序

快排是目前平均时间复杂度最小的排序法。体现了分治的思想。算法比较经典,因此在这里记录一下,加深印象。

快速排序中比较核心的是要寻找一个pivot值。即枢轴值。

核心思想就是,将需要排序的数列,以pivot值为中心,以大小左右分开。然后对左右两段数组再重新选取pivot值。以此递归。

下面我们来看一看代码。

public class QuickSortManager {
    int pivotloc;
    public void quickSort(int[] arr , int low , int high){
        if(low < high){
            pivotloc = partition(arr, low, high);
            quickSort(arr , low , pivotloc-1);
            quickSort(arr, pivotloc+1, high);   
        }
        
    }
    
    int partition(int[] arr  , int low , int high){
        int pivot = arr[low];
        while(low < high){
            while(low < high && arr[high] > pivot){
                high--;
            }
            swap(arr, low, high);
            while(low < high && arr[low] <= pivot){
                low++;
            }
            swap(arr, low, high);
        }
        
        return low;
    }
    
    void swap(int[] arr  , int a , int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

代码总共30行左右,非常简单。在这个方法中,我们将数组arr的第一个值作为pivot。然后以low,high作为数组开头和结尾的索引。一旦发现arr[high]<pivot或是arr[low]>pivot,即交换它与pivot的值,然后更换遍历方向。最后当low>=high时即完成一次分治。并返回此时pivot的索引值。 然后通过递归,我们再对pivot左边和右边分别进行分治,即可完成排序。

举个小例子

3  5  4  1  2  6 // pivot = 3
2  5  4  1  3  6
2  3  4  1  5  6
2  1  4  3  5  6
2  1  3  4  5  6  // low = 2
第一次排序结束
确定了 pivot 左边的一定比 3 小 ,右边的一定比 3 大 

2 1 // pivot = 2
1 2 // low = 0

4 5 6 // pivot = 4 low = 0
 
排序完成 

优化

简化swap

我们在分治的时候发现,其实pivot的值每次交换并没有太大的意义。每次我们只是需要当前pivot的索引值和大小,pivot本身在一次分治时不会变化。所以我们考虑将其取出。每次交换时,直接覆盖掉,需要交换的值,最后再将pivot值赋进数组。

进入之后的代码入下:

    int partition(int[] arr  , int low , int high){
        int pivot = arr[low];
        while(low < high){
            while(low < high && arr[high] > pivot){
                high--;
                calculationCount++;
            }
            arr[low] = arr[high];
            //swap(arr, low, high);
            while(low < high && arr[low] <= pivot){
                low++;
                calculationCount++;
            }
            arr[high] = arr[low];
            //swap(arr, low, high);
            
        }
        arr[low] = pivot;
        
        return low;
    }
3  5  4  1  2  6 // pivot = 3
2  5  4  1  2  6
2  5  4  1  5  6
2  1  4  1  5  6
2  1  4  4  5  6 
2  1  3  4  5  6 // low = 2
第一次排序结束
确定了 pivot 左边的一定比 3 小 ,右边的一定比 3 大 

2 1 // pivot = 2
1 2 // low = 0

4 5 6 // pivot = 4 low = 0
 
排序完成 

经过这样的简化,我们可以减少大量的赋值操作。

优选pivot值

原先的算法中,我们pivot值在每次分治时,都取的是arr[low]。我们知道,快速排序法中,任意选取pivot值,都能完成排序,但这有可能导致最坏情况。即,选到最大值或最小值,将其余的数据全部分治到了一边。这相当于浪费了一次分治。只是确定了一个值的位置。

所以我们考虑选一个更好的pivot。

为了避免最坏情况的出现。我们每次分治时,不再选择arr[low]作为pivot。而是采用arr[low]、arr[high]、arr[middle]的中位值来作为pivot。这样就避免了会选择最大值或最小值作为pivot的情况。程序比较简单,就不赘述了。

多种排序

并不是所有情况下,快速排序法都是最优选择。由于分治的思想,我们可以在分治后,所需处理的数据较少时。采用插值排序进行排序。 插入排序代码如下:

    void insertSort(int arr[] , int low , int high){
         int i, j;
            int tmp;
            for (i = low + 1; i <= high; i++) { 
                if (arr[i] < arr[i - 1]) {
                    
                    tmp = arr[i]; 
                    for (j = i - 1 ; j >= low && arr[j] > tmp ; j--) {
                        arr[j + 1] = arr[j]; 
                    }
                    arr[j + 1] = tmp; 
                }
            }
    }

在quickSort中进行判断和调用:

    private static final int INSERT_SORT_LENGTH = 7;
    int pivotloc;
    public void quickSort(int[] arr , int low , int high){
        if(low < high){
            if(high - low  + 1 > INSERT_SORT_LENGTH){
                pivotloc = partition(arr, low, high);           
                quickSort(arr , low , pivotloc-1);
                quickSort(arr, pivotloc+1, high);   
            }else{
                insertSort(arr, low, high);
                
            }
            
        }
        
    }

以上。 笔者初学,如有谬误,不吝赐教。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java学习网

Spark SQL中对Json支持的详细介绍

Spark SQL中对Json支持的详细介绍 在这篇文章中,我将介绍一下Spark SQL对Json的支持,这个特性是Databricks的开发者们的努力结果,...

3279
来自专栏云数据库

MySQL5.7 JSON实现简介

本文主要介绍在MySQL 5.7.7开始引入的非结构化数据类型JSON的特性以及具体的实现方式(包括存储方式)。首先介绍为什么要引入JSON的原生数据类型的支持...

1733
来自专栏Java架构沉思录

如何优雅地实现分页查询

分页功能是很常见的功能,特别是当数据量越来越大的时候,分页查询是必不可少的。实现分页功能有很多种方式,如果使用的ORM框架是mybatis的话,有开源的分页插件...

862
来自专栏Aloys的开发之路

Hibernate与autoCommit

JDBC 的autoCommit属性 对于每一个 JDBC connection,都有一个autoCommit属性,只有执行commit后,该connectio...

1738
来自专栏编程

《Python编程:从入门到实践》 第二章 笔记

孩子,无论你做什么爸爸妈妈都爱你 我想学Python 找个好人家 2.2.1  变量的命名和使用 变量名只能包含字母、数字和下划线。变量名可以字母或下划线打头,...

1710
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict、Set专栏-新排版)

在线预览:http://github.lesschina.com/python/base/pop/3.listtupledict_set.html

1595
来自专栏Golang语言社区

动手实现一个JSON验证器(上)

分析 既然要验证JSON的有效性,那么必然需要清楚的知道JSON格式,这个在JSON官网已经给我们画出来了: ? ? ? ? ? 从官方的图上面可以看出,JSO...

3687
来自专栏大内老A

在Entity Framework中使用存储过程(四):如何为Delete存储过程参数赋上Current值?

继续讨论EF中使用存储过程的问题,这回着重讨论的是为存储过程的参数进行赋值的问题。说得更加具体一点,是如何为实体映射的Delete存储过程参数进行赋值的问题。关...

1909
来自专栏封碎

Android获取外部和内部存储空间总大小和可用大小 博客分类: Android小技巧 AndroidLinuxOSCache

      android.os下的StatFs类主要用来获取文件系统的状态,能够获取sd卡的大小和剩余空间,获取系统内部空间也就是/system的大小和剩余空...

741
来自专栏坚毅的PHP

mysql数据迁移hbase问题

无法直接dump,写了java多线程程序做迁移 问题1:Operation not allowed after ResultSet closed 裸jdbc语句...

3525

扫码关注云+社区