快排和堆排序

别看这个简单也基础,但是真的面试的时候会让你写,纸上手写,嗯

快排

private static void quickSort(int[] test, int start, int end) {
        //quick sort的主程序
        if(start < end){
            int q = partition(test, start, end);
            quickSort(test, start, q-1);
            quickSort(test, q+1, end);
        }

    }

    private static int partition(int[] test, int start, int end) {
        //完成一次划分
        //主元选择test[end]
        int pivot = test[end];
        int i = start - 1;
        for(int j = start; j < end; j++){
            if(test[j] <= pivot){
                i++;
                //交换test[i]和test[j]
                int t = test[i];
                test[i] = test[j];
                test[j] = t;
            }
        }
        //i+1的位置即是pivot的位置
        //交换test[i+1]和pivot
        int t1 = test[i+1];
        test[i+1] = test[end];
        test[end] = t1;
        return i+1;
    }

堆排序

public static void heapSort(int[] test){
         //建堆
         buildHeap(test);
         for(int heapSize = test.length - 1; heapSize >= 1; heapSize--){
             //交换test[heapSize]和test[0]的位置
             int t = test[0];
             test[0] = test[heapSize];
             test[heapSize] = t;
             //维护堆的性质
             maxHeapify(test, heapSize, 0);
         }
     }
    private static void maxHeapify(int[] test, int heapSize, int i) {
        //维护堆的性质
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //找出三者最大的
        int largest;
        if(left < heapSize && test[left] > test[i]){
            largest = left;
        }else{
            largest = i;
        }
        if(right < heapSize && test[right] > test[largest]){
            largest = right;
        }
        if(i != largest){
            //交换test[i]和test[largest]
            int t = test[i];
            test[i] = test[largest];
            test[largest] = t;
            //递归
            maxHeapify(test, heapSize, largest);
        }

    }
    private static void buildHeap(int[] test) {
        //建堆
        for(int i = test.length / 2; i >= 0; i--){
            maxHeapify(test, test.length, i);
        }

    }

main函数:

int test = {2,3,1,1,5,6,7,7,8,4,9,11};
//quickSort(test, 0, test.length-1);
heapSort(test);
for(int x : test){
    System.out.print(x+" ");
}     

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coding

python面向对象应用案例:烧鸡翅

1064
来自专栏一个会写诗的程序员的博客

java.sql.BatchUpdateException: Can not issue SELECT via executeUpdate() or executeLargeUpdate().

java.sql.BatchUpdateException: Can not issue SELECT via executeUpdate() or execu...

823
来自专栏微服务生态

JAVA并发全景图1.1版

如果大家看不清上述图片,可以点击如下URL查看大图: http://img.blog.csdn.net/20170524150154080?watermark...

643
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

341
来自专栏Data Analysis & Viz

手把手教你完成一个数据科学小项目(6):城市提取与可视化

请先阅读《“中国年轻人正带领国家走向危机”,这锅背是不背? 》 一文,以对“手把手教你完成一个数据科学小项目”系列有个全局性的了解。

852
来自专栏一个会写诗的程序员的博客

SQLNonTransientConnectionException: CLIENT_PLUGIN_AUTH is required

java.sql.SQLNonTransientConnectionException: CLIENT_PLUGIN_AUTH is required at ...

1952
来自专栏c#开发者

xmldocument内嵌入另一个xmldocument,xmlnode的方法

string xmlstr1 = @"<root><head>myHead</head><body></body></root>"; s...

2665
来自专栏别先生

java.net.UnknownHostException: master

1:如果你报这个错误,第一反应应该是本地的host文件没有配置服务器名称和对应的ip地址,这个反应就对了。贴一下错误和解决方法: 1 java.net.Unk...

2347
来自专栏后端之路

htmlunit 解决https证书不信任问题

代码如下 @Test public void testHtmlUnit() throws Exception { WebClient c...

3369
来自专栏行者常至

org.springframework.orm.hibernate3.HibernateQueryException: unexpected token: where near line 1, col

org.springframework.orm.hibernate3.HibernateQueryException: unexpected token: wh...

551

扫码关注云+社区