快速排序法

/**
 * 快速排序实现
 * Created by John Kwok on 2018/2/2.
 */
import java.util.Arrays;
public class QuickSort {
    /**
     * 在待排序索引范围内随机选取一个数值,将小于等于该索引处值的数字放置在其左侧,大于的放在其右侧。
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array,int start,int end){
        if(array == null||array.length == 0|| start<0 || end >= array.length || start>end) return -1;
        if(start == end) return start;
        int index = (int)(start + Math.random()*(end - start + 1));
        swap(array,index,end);
        int smallNum = start - 1;//注意这里
        for(int i = start ; i <= end ; i++){
            if(array[i] <= array[end]){
                smallNum++;
                if(i > smallNum){
                    swap(array,i,smallNum);
                }
            }
        }
        return smallNum;
    }

    /**
     * 使用递归法进行快速排序
     * @param array
     * @param start
     * @param end
     */
    public static void quickSortFun(int[] array,int start,int end){
        if (array == null||array.length == 0||start <0||end >=array.length||start > end) return ;
        int index = partition(array,start,end);
        if(index > start)
            quickSortFun(array,start,index - 1);
        if(index < end)
            quickSortFun(array,index+1,end);
    }

    /**
     * 交换数组中两个索引处的值
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 主函数,验证方法
     * @param args
     */
    public static void main(String[] args){
        int[] array = new int[]{1,2,7,3,5,4,2,7,9,2,2,5,76,2,5,2,6,3};
//        int[] array = new int[]{1,2};
//        swap(array,0,1);
        quickSortFun(array,0,array.length-1);
        System.out.println("排序结果:"+Arrays.toString(array));
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码云1024

C# get 、set、索引器

31130
来自专栏WindCoder

Java中的域与变量

Java中的Field译为“字段”,也译为“域”,Field和成员变量(Member Variable)是相同的。所以域是变量中的一种。

60410
来自专栏Java技术栈

JDK8新特性之Lambda表达式

什么是Lambda表达式 Java 8的一个大亮点是引入Lambda表达式,使用它设计的代码会更加简洁。当开发者在编写Lambda表达式时,也会随之被编译成一个...

35250
来自专栏技术博客

C#委托四(匿名方法)

什么是匿名方法? 匿名方法是C#2.0引入的一个新特性,它允许开发者声明自己的函数代码而无须使用委托函数。 C#为委托提供一种机制,可以为委托定义匿名方...

13020
来自专栏林德熙的博客

C# 循环的判断会进来几次

最近有小伙伴告诉我,在循环的判断条件只会计算一次,本金鱼不相信,于是就做了测试,本文记录我做的测试。

13330
来自专栏老马说编程

(91) Lambda表达式 / 计算机程序的思维逻辑

在之前的章节中,我们的讨论基本都是基于Java 7的,从本节开始,我们探讨Java 8的一些特性,主要内容包括: 传递行为代码 - Lambda表达式 函数式...

20980
来自专栏cs

C#3.0面向对象程序设计一

文章首发 http://www.imooc.com/article/22105 我还在简书。。。。。。 面向对象三大特征,继承,封装,多态 1.0 封...

29660
来自专栏蘑菇先生的技术笔记

c#语言-高阶函数

34360
来自专栏me的随笔

.NET中可空值类型实现原理

为了让.Net中的值类型可以赋值为null,微软特地添加了Nullable<T>类型,也可简写为T?。但是Nullable<T>自身是结构体,也是值类型,那么它...

10120
来自专栏编程坑太多

Java 8 新特性 Lambda 表达式简单使用

18690

扫码关注云+社区

领取腾讯云代金券