快排和堆排序

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

快排

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 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

[Silverlight动画]转向行为 - 对象回避

对象回避主题的完整意义是指,在机车行走的路线中存在一些障碍物,机车必须绕开、防止触碰到它们。听上去和碰撞检测有关,然而这仅仅是发生在预测阶段,也就是:“以我当前...

1965
来自专栏lonelydawn的前端猿区

Node.js力破江苏网警刑侦科推理试题

月前,江苏网警 在微博发布了一套《2018年刑侦科目推理试题》,可谓难倒了诸多英雄好汉,评论区内更是一片皮皮之音。 @二向箔icon: 高考前班主任教过我们,...

2807
来自专栏ACM算法日常

工人的请愿书(树形DP)- UVA 12186

A couple of years ago, a new world wide crisis started, leaving many people with...

1094
来自专栏小樱的经验随笔

Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力,B.优先队列,C.dp乱搞)

A. Carrot Cakes time limit per test:1 second memory limit per test:256 megabytes...

3257
来自专栏tkokof 的技术,小趣及杂念

侃侃哈希表

说到哈希表,相信初通数据结构的人士应该耳熟能详,其相关的结构细节虽然并不繁复,但就快速查找数据而言,该结构优异的性能表现绝对可算一枝独秀,平均情况下O(1)的时...

651
来自专栏HansBug's Lab

1708: [Usaco2007 Oct]Money奶牛的硬币

1708: [Usaco2007 Oct]Money奶牛的硬币 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 5...

2577
来自专栏ACM算法日常

HDU6370:Werewolf 推理+拓扑排序 2018第六场杭电多校

"The Werewolves" is a popular card game among young people.In the basic game, th...

652
来自专栏Fish

poj-3253 优先队列

大神指导说要弄个博客,写写题解。那我就听大神的话,写写题解吧。 这道题的题意就是FJ这个人有一块木板,长度是N(1 ≤ N ≤ 20,000),然后要切成好多块...

2247
来自专栏菩提树下的杨过

Flash/Flex学习笔记(39):弹性运动

动画中的弹性运动 从视觉效果上接近 物理经典力学中的单摆运动或弹簧(胡克定律F=Kx)振动 先看下面的模拟演示: 规律: 小球先从出发点(初始为最左侧)向目标点...

1965
来自专栏Java帮帮-微信公众号-技术文章全总结

【学习经验】Java中常用英文

【学习经验】Java中常用英文 第一章: public['pʌblik] 公共的,公用的 static['stætik] 静的;静态的...

35110

扫码关注云+社区